Python 3.0 - is this true?

"Martin v. Löwis" martin at
Sun Nov 9 19:46:51 CET 2008

Hallvard B Furuseth wrote:
> Terry Reedy writes:
>> If you want to duplicate 2.x behavior, which does *not* work for all
>> types...
>> def py2key(item): return (str(type(item)), item)
> Nope.
>   sorted((-1, 2, True, False))             == [-1, False, True, 2]
>   sorted((-1, 2, True, False), key=py2key) == [False, True, -1, 2]
> Might often be good enough though.  But uses more memory.

Compared to what? To the current 2.x default implementation? Or compared
to an emulation of that, in 2.x, in a pure-Python function, passed
as a cmp= argument?

I think this one is *more* memory-efficient than a cmp function. Calling
a cmp function will always allocate a frame object, for each comparison,
giving you O(n log n) frame objects being created. OTOH, the key
function will only be called O(n) times, causing the allocation of only
O(n) objects. Of course, the peak memory usage is higher with the key
function (O(n), compared to O(1) for the cmp= function, assuming the
frame objects get deallocated and reused immediately).


More information about the Python-list mailing list