[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:1.8.0.6) Gecko/20060728 Firefox/1.5.0.6 |
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:
<http://savannah.nongnu.org/bugs/?17560>
_______________________________________________
Message sent via/by Savannah
http://savannah.nongnu.org/
- [bug #17560] merge code in rcs.c is O(n^2), Derek Robert Price, 2006/09/04
- [bug #17560] merge code in rcs.c is O(n^2), anonymous, 2006/09/05
- [bug #17560] merge code in rcs.c is O(n^2), Peter Toft, 2006/09/05
- [bug #17560] merge code in rcs.c is O(n^2), Mark D. Baushke, 2006/09/06
- [bug #17560] merge code in rcs.c is O(n^2), anonymous, 2006/09/06
- [bug #17560] merge code in rcs.c is O(n^2), Peter Toft, 2006/09/06
- [bug #17560] merge code in rcs.c is O(n^2), Derek Robert Price, 2006/09/06
- [bug #17560] merge code in rcs.c is O(n^2), Derek Robert Price, 2006/09/06
- [bug #17560] merge code in rcs.c is O(n^2), Mark D. Baushke, 2006/09/06
- [bug #17560] merge code in rcs.c is O(n^2),
Derek Robert Price <=
- [bug #17560] merge code in rcs.c is O(n^2), Derek Robert Price, 2006/09/06
- [bug #17560] merge code in rcs.c is O(n^2), Derek Robert Price, 2006/09/08