[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Eric Blake
Subject: Re: Question about critical_factorization() in the Two-Way algorithm
Date: Mon, 21 Jun 2010 17:44:10 -0600
User-agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv: Gecko/20100430 Fedora/3.0.4-3.fc13 Lightning/1.0b2pre Mnenhy/0.8.2 Thunderbird/3.0.4

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

Attachment: signature.asc
Description: OpenPGP digital signature

reply via email to

[Prev in Thread] Current Thread [Next in Thread]