On 7/21/2010 12:15 PM, Daniel Stutzbach wrote:
Here's a performance comparison of sorting with blist versus 3.1's list:
http://stutzbachenterprises.com/performance-blist/sort-random-list
Question related to possible addition of radix sort to lists:
These tests use random numbers with a constant, relatively high density
of 25%, which is favorable to radix sort. What if you do the same test
with a constant range of, say, 1000000000 (1 billion) or even a trillion
or quadrillion. Or how about sorting a thousand 128bit ip6 addresses?
Which wins for that?
list.sort is (near) linear for lists that are mostly ordered. I think
Tim's writeup about this in in the source. For instance, if one extends
a sorted with 1% random additions and resorts, list.sort will skip the
sorted part, sort the additions, and merge them back in. Radix sort
ignores pre-existing order. So either a lot of comparitive profiling
would be needed for auto-selection of sort method, or it should be user
selectable.
Does your radix sort meet the stability guarantee of list.sort?
If not, a separate .rsort method would be needed anyway.
--
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
