Hello Bulat,
I'm not sure what your point is, let's try to enlighten me.
Am Mittwoch, 21. Dezember 2005 16:30 schrieben Sie:
Hello Daniel,
Wednesday, December 21, 2005, 5:20:18 PM, you wrote:
DF ordinarily, on my computer, your version of straightforward is 10-15%
faster DF than KMP
Am Mittwoch, 21. Dezember 2005 15:20 schrieb Daniel Fischer:
i'm 90% sure that straightforward method must be faster for one-time
searches.
I'm far less sure of that. If you have a really short search-pattern, I
think that probably straightforward search is indeed faster (at least, if
the
Am Mittwoch, 21. Dezember 2005 08:18 schrieb Branimir Maksimovic:
From: Bulat Ziganshin [EMAIL PROTECTED]
Reply-To: Bulat Ziganshin [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: haskell-cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Tue, 20 Dec
From: Daniel Fischer [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: Bulat Ziganshin [EMAIL PROTECTED], Haskell-Cafe@haskell.org
KMP is O(m) while straightforward is O(m*n).
Where m is the length of the input and n is the length of the searched-for
pattern, I think?
Yes.
From: Bulat Ziganshin [EMAIL PROTECTED]
Reply-To: Bulat Ziganshin [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: haskell-cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Tue, 20 Dec 2005 23:55:22 +0300
Hello Branimir,
Tuesday, December 20, 2005, 9
Am Freitag, 16. Dezember 2005 03:36 schrieben Sie:
From: Daniel Fischer [EMAIL PROTECTED]
Any improvements are welcome, certainly some of you can do much better.
It is fast on my machine except that you are using Map to lookup
for badChar which is O(log n).
I;ve placed this instead:
| s == s' = srch str str' (l-1)
| otherwise = l
Greetings, Bane.
From: Branimir Maksimovic [EMAIL PROTECTED]
To: [EMAIL PROTECTED], [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Thu, 15 Dec
Am Donnerstag, 15. Dezember 2005 02:39 schrieben Sie:
From: Branimir Maksimovic [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Thu, 15 Dec 2005 00:55:02 +
From: Daniel Fischer [EMAIL PROTECTED
From: Daniel Fischer [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Thu, 15 Dec 2005 21:07:11 +0100
Am Donnerstag, 15. Dezember 2005 02:39 schrieben Sie:
From: Branimir Maksimovic [EMAIL
From: Daniel Fischer [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Tue, 13 Dec 2005 11:23:29 +0100
After seeing that your program is fastest (I've also tried one from
http://haskell.org
Hi, Bane and all,
Am Dienstag, 13. Dezember 2005 14:22 schrieben Sie:
In real world situation your KMP will always be fastest on average.
I like that we are not using C arrays as then we have advantage
of lazyness and save on memory usage. C++ program will be faster
on shorter strings
]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Tue, 13 Dec 2005 11:23:29 +0100
After seeing that your program is fastest (I've also tried one from
http://haskell.org/hawiki/RunTimeCompilation but perhaps I'm not
that good in converting to search
From: Daniel Fischer [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Wed, 14 Dec 2005 17:10:20 +0100
I think that's because on your machine Bulat's version have better
perfromance
From: Daniel Fischer [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Wed, 14 Dec 2005 20:40:06 +0100
Hi Bane,
nice algorithm. Since comparing chars _is_ cheap, it is to be expected that
all
From: Branimir Maksimovic [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Thu, 15 Dec 2005 00:55:02 +
From: Daniel Fischer [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: Haskell-Cafe
G'day all.
Quoting Branimir Maksimovic [EMAIL PROTECTED]:
After seeing that your program is fastest (I've also tried one from
http://haskell.org/hawiki/RunTimeCompilation but perhaps I'm not
that good in converting to search replace?)
You probably did it right, but you could post your
From: [EMAIL PROTECTED]
To: haskell-cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Thu, 15 Dec 2005 00:25:19 -0500
G'day all.
Quoting Branimir Maksimovic [EMAIL PROTECTED]:
After seeing that your program is fastest (I've also tried one from
http://haskell.org
Am Montag, 12. Dezember 2005 16:28 schrieben Sie:
From: Daniel Fischer [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Mon, 12 Dec 2005 16:15:46 +0100
Earlier today:
Sorry, but
Prelude
From: Daniel Fischer [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Tue, 13 Dec 2005 11:23:29 +0100
Am Montag, 12. Dezember 2005 16:28 schrieben Sie:
From: Daniel Fischer [EMAIL PROTECTED
Am Montag, 12. Dezember 2005 01:34 schrieben Sie:
On 12/12/05, Daniel Fischer [EMAIL PROTECTED] wrote:
Okay, I have looked up KMP and implemented it.
Seems to work -- my first use of QuickCheck, too.
It's slower than Bulat's and Tomasz' for Branimir's test :-(,
but really fast for my
From: Daniel Fischer [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Mon, 12 Dec 2005 10:31:49 +0100
Am Montag, 12. Dezember 2005 01:34 schrieben Sie:
On 12/12/05, Daniel Fischer [EMAIL PROTECTED] wrote:
Okay, I
Earlier today:
Sorry, but
Prelude SearchRep searchReplace abaaba ## abababaaba
abababaaba
I haven't analyzed the algorithm, so I don't know why exactly this fails.
I'll take a look sometime soon.
I found the problem (one at least).
Say the pattern to be replaced begins with 'a' and we have
From: Daniel Fischer [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Mon, 12 Dec 2005 13:07:29 +0100
Sorry, but
Prelude SearchRep searchReplace abaaba ## abababaaba
abababaaba
I haven't
From: Daniel Fischer [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Mon, 12 Dec 2005 16:15:46 +0100
Earlier today:
Sorry, but
Prelude SearchRep searchReplace abaaba ## abababaaba
abababaaba
From: Daniel Fischer [EMAIL PROTECTED]
To: Branimir Maksimovic [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Mon, 12 Dec 2005 16:15:46 +0100
Earlier today:
Sorry, but
Prelude SearchRep searchReplace abaaba ## abababaaba
abababaaba
On 12/12/05, Daniel Fischer [EMAIL PROTECTED] wrote:
Okay, I have looked up KMP and implemented it.
Seems to work -- my first use of QuickCheck, too.
It's slower than Bulat's and Tomasz' for Branimir's test :-(,
but really fast for my test.
Undoubtedly, one can still tune it.
Perhaps by
From: Daniel Fischer [EMAIL PROTECTED]
To: Haskell-Cafe@haskell.org
Subject: [Haskell-cafe] Substring replacements
Date: Mon, 12 Dec 2005 01:14:37 +0100
Okay, I have looked up KMP and implemented it.
Seems to work -- my first use of QuickCheck, too.
It's slower than Bulat's and Tomasz' for
27 matches
Mail list logo
