On 06/21/2010 05:30 PM, Eric Blake wrote: > starting with a comparison of x[0] and x[1]), we can instead start with > only reduced-length suffixes (that is, start with a comparison of x[1] > and x[2]), for one less comparison, and a slightly faster factorization > time.
Followup - the number of comparisons done while finding a maximal suffix is bounded by len(needle) + num_elements_in_alphabet, and my code is not always faster. That is, it is possible to require more than len(needle) comparisons for some needles, because of the /* Suffix is larger, start over from the current location */ branch of the conditional reducing k by more than it increases j, although that branch of the conditional can be reached at most as many times as you have letters in the alphabet, so you still have an O(m) bound on computing the factorization. More concretely, on the needle "ababcababcdababcababc" the existing two-way code takes: i=22 "ababcababc" "dababcababc" i=20 "" "ababcababcdababcababc" or 42 comparisons to find one of the two critical factorizations (and the reverse direction found nothing), while my proposed code takes: i=21 "ababcababc" "dababcababc" i=26 "ababcababcd" "ababcababc" or 47 comparisons to find both critical factorizations (5 comparisons worse). But overall, I think that the average effect on comparisons with my proposed patch will still be fewer comparisons, even with certain worst-case needles where it increases. -- Eric Blake ebl...@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature
