| From: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
|---|---|
| To: | "David Rowley" <dgrowley(at)gmail(dot)com> |
| Cc: | "'Heikki Linnakangas'" <heikki(dot)linnakangas(at)enterprisedb(dot)com>, "'Peter Eisentraut'" <peter_e(at)gmx(dot)net>, pgsql-patches(at)postgresql(dot)org |
| Subject: | Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker) |
| Date: | 2008-09-05 17:12:17 |
| Message-ID: | 27136.1220634737@sss.pgh.pa.us |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers pgsql-patches |
"David Rowley" <dgrowley(at)gmail(dot)com> writes:
> Tom Lane wrote:
>> Hmm. B-M-H has worst case search speed O(M*N) (where M = length of
>> pattern, N = length of search string); whereas full B-M is O(N). Maybe we
>> should build the second table when M is large?
> I'll look into this. If it pays off for longer searches I'll submit a patch.
> I won't have the time until after the 15th, so perhaps that's in November's
> commit fest?
Yes. Let's get B-M-H in during this fest and then you can look into
whether a follow-on patch is worthwhile.
regards, tom lane
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Zdenek Kotala | 2008-09-05 17:12:35 | Re: Prototype: In-place upgrade v02 |
| Previous Message | Tom Lane | 2008-09-05 17:09:50 | Re: plpgsql is not translate-aware |
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Heikki Linnakangas | 2008-09-05 17:25:56 | Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker) |
| Previous Message | David Rowley | 2008-09-05 17:02:54 | Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker) |