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,
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?
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
&
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 Bra
Hello Branimir,
Tuesday, December 20, 2005, 9:48:48 PM, you wrote:
BM> I've finally performed test on amd64 and result is a same as on intel.
BM> KMP always wins. So KMP is best suited for non indexed strings
BM> and I guess should be used in library as prefered search/replace method.
BM> This te
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:
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:
> F
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
ic" <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED], [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Thu, 15 Dec 2005 01:39:57 +
From: "Branimir Maksimovic" <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED]
CC: Haskell-Cafe@ha
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 tr
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 ve
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"
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
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'
quot;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
> htt
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 shor
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'
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:
> Fro
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:
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 Sear
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 Sear
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"
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
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 PROTE
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.
As for times: a complete stat is attached, all compiled with -O2, as well as
the modified KMP-version and
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 f
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
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 b
29 matches
Mail list logo
