[Python-Dev] Stable sort and partial order (original) (raw)
Antoine Pitrou solipsis at pitrou.net
Mon Nov 1 12:33:31 CET 2010
- Previous message: [Python-Dev] Cleaning-up the new unittest API
- Next message: [Python-Dev] Stable sort and partial order
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
On Mon, 01 Nov 2010 02:55:35 +0000 Michael Foord <fuzzyman at voidspace.org.uk> wrote:
Having a more efficient 'slow-path' and moving to that by default would fix it. The bug is only a duplicate of the bug in sorted - caused by the fact that sets / frozensets can't be sorted in the standard Python way (their less than comparison adheres to the set definition). This is something that will probably surprise many Python developers:
>>> a = [{2,4}, {1,2}] >>> b = a[::-1] >>> sorted(a) [set([2, 4]), set([1, 2])] >>> sorted(b) [set([1, 2]), set([2, 4])] (Fixing the bug in sorted would fix assertItemsEqual ;-)
How is this a bug? The sort algorithm is stable, which means the above behaviour is a feature. I see no easy way of eliminating the O(n*n) issue. Custom key functions can't work in all cases.
Regards
Antoine.
- Previous message: [Python-Dev] Cleaning-up the new unittest API
- Next message: [Python-Dev] Stable sort and partial order
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]