[2.5.1.1/dictionary] Change sorting order?

[Steven D'Aprano]

On Fri, 22 Jan 2010 15:57:07 +0000, Neil Cerutti wrote:

> On 2010-01-22, Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au>
> wrote:
>> Unless you can predict what index to use for (say) names starting with
>> "B", then your scheme doesn't work. In order to find that index, you
>> have to do a linear search of the list after every sort, turning
>> sorting into O(N**2) instead of O(N*log N).
> 
> O(N*Log N) + O(N) == O(N**2)?

Oops!  :(

Of course, the sort is in fast C, and the linear search is in relatively 
slow Python, so it is quite conceivable that for realistic amounts of 
data, the time could be dominated by the searching.

Or the OP might just change his requirements and allow starting the 
display in the middle of the letter.


> Besides, the idea was to avoid sorting altogether.

I don't see why you think that's necessary. Python's sort is very fast 
when the list is nearly sorted, so if you re-sort after any addition of a 
username, it might even be faster than trying to keep the list sorted all 
the time. That's the sort of thing that we'd need to do some timing tests 
to see which was faster.



-- 
Steven