Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)
От | David Rowley |
---|---|
Тема | Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker) |
Дата | |
Msg-id | 9CD35557A45746D183E72D71802749D4@amd64 обсуждение исходный текст |
Ответ на | Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker) (Tom Lane <tgl@sss.pgh.pa.us>) |
Список | pgsql-patches |
Tom Lane 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? Yes Bug. That's what I get for making last minute changes. It didn't affect the benchmark, that was done before moving the code into postgresql for testing. The function I tested with had an extra parameter to set the skip table size. Each possible size was tested and the best time was saved along with the best size. > BTW, to the extent that you feel like testing a different idea, > I would suggest: > * don't bother initializing the skiptable when len1 < len2 Good plan. > * 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. That seems like a better idea. I had considered len1 * len2, giving that's the worst case for BMH. Of course the lengths would need to be raised quite a bit. I'll go with len1 - len2 I'll make the above changes and then run my benchmark again to see if the skip table size logic should be updated. I'll also benchmark and update the benchmark spreadsheet to see what's changed. David.
В списке pgsql-patches по дате отправления: