Re: Question about critical_factorization() in the Two-Way algorithm

[Eric Blake]

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   address@hidden    +1-801-349-2682
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature