[Top][All Lists]

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

[bug #17560] merge code in rcs.c is O(n^2)

From: Derek Robert Price
Subject: [bug #17560] merge code in rcs.c is O(n^2)
Date: Wed, 6 Sep 2006 18:29:02 +0000
User-agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv: Gecko/20060728 Firefox/

Follow-up Comment #16, bug #17560 (project cvs):

Probably a longish file could help show the differences too, since part of
what the improved algorithm was doing was shifting portions of an array
forward and backwards (using memcpy) as sections were deleted and other
sections were inserted into the array (once per RCS change text chunk).  The
more lines in the file, the more lines would need to be shifted in memory for
each RCS change chunk.

The new algorithm is simply careful to build a second array in order rather
than shifting the first in place.

So really, I think the new algorithm is more exactly O(C + L), where C is the
number of RCS change chunks to be processed and L is the total number of lines
in the head revision, whereas it was previously approximately O(C * L / 2).


Reply to this item at:


  Message sent via/by Savannah

reply via email to

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