Julian Foad wrote:
> Branko Čibej wrote:
>
>> Julian Foad wrote:
>
>>> I found that there were barely enough uses of those functions to
>>> make it worthwhile creating new, sorted versions of them, but I
>>> would not object to doing so.
>>
>>
>> Apart from the fact that we'd have to uses sorted tables in the FS,
>> too, not just in the WC, you have to maintain the sorted list every
>> time you change the entries, and entries modification becomes quadratic.
>
> I'm not sure, but it sounds like you are focussing on a particular
> implementation method again. Changing entries in a sorted list
> doesn't require quadratic time, even though a simple implementation of
> it does.
You can modify the sorted list in O(log N) time, but you can't cache the
result. So every time some function reads the entries, it has to spend
O(N*log N) time to sort the list before doing a traversal. This is not
quadratic, but you have to multiply it by the number of times you have
to repeat the sort.
-- Brane
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Wed Feb 23 00:37:03 2005