[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: Sorted output from Subversion commands

From: Branko Čibej <brane_at_xbc.nu>
Date: 2005-02-23 00:34:40 CET

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

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.