[220.127.116.11/dictionary] Change sorting order?
steve at REMOVE-THIS-cybersource.com.au
Fri Jan 22 17:27:21 CET 2010
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>
>> 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)?
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.
More information about the Python-list