| From: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
|---|---|
| To: | "David Rowley" <dgrowley(at)gmail(dot)com>, "'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-06 22:50:47 |
| Message-ID: | 26522.1220741447@sss.pgh.pa.us |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers pgsql-patches |
I wrote:
> I looked this over a bit and was immediately confused by one thing:
> the introductory comment says that the skip table size ought to be based
> on the length of the haystack, which makes sense to me, but the code is
> actually initializing it on the basis of len2, ie, the length of the
> needle. Isn't that a bug? Was the same bug present in the tests you
> made to determine the best table sizes?
BTW, to the extent that you feel like testing a different idea,
I would suggest:
* don't bother initializing the skiptable when len1 < len2
* otherwise, choose its size based on len1 - len2, not just len1 or
len2. This is (one less than) the maximum number of search loop
consultations of the skip table that can happen, so it seems like a
plausible number, and better than either length alone.
regards, tom lane
| From | Date | Subject | |
|---|---|---|---|
| Next Message | David Rowley | 2008-09-06 23:25:07 | Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker) |
| Previous Message | Tom Lane | 2008-09-06 22:45:33 | Re: reducing statistics write overhead |
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Jaime Casanova | 2008-09-06 23:10:25 | Re: [PgFoundry] Unsigned Data Types [1 of 2] |
| Previous Message | Tom Lane | 2008-09-06 22:21:01 | Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker) |