I need to sort a list of lists. The following is a compare function:

def compare(lhs, rhs): # lhs&rhs are lists
    delta = len(lhs) - len(rhs)
    if delta > 0:
        return 1
    elif delta < 0:
        return -1
    if lhs < rhs:
        return 1
    elif lhs > rhs:
        return -1
    return 0

It looks pretty wordy. Is there a way to rewrite the function without performance penalty?

If I understand correctly, you want to sort lists by their length first, and then by "whatever lists are otherwise sorted by". I also assume that you want to pass your function as the cmp argument to the list.sort or sorted function.

You can do this in both a more natural to read, and computationally more efficient way, by using the key argument instead:

In general, the key and reverse conversion processes are much faster than specifying an equivalent cmp function. This is because cmp is called multiple times for each list element while key and reverse touch each element only once.

(Source: https://docs.python.org/2/library/stdtypes.html#mutable-sequence-types)

This should be the appropriate key function for your case:

def length_first(lst):
    return len(lst), lst

Or simply:

lambda lst: len(lst), lst

Example:

>>> from random import randrange
>>> lists = [[randrange(5) for _ in range(randrange(3, 6))]
...          for _ in range(10)]
>>> print '\n'.join(map(str, sorted(lists, key=lambda lst: (len(lst), lst))))
[0, 0, 4]
[2, 3, 0]
[2, 4, 0]
[3, 4, 2]
[4, 1, 4]
[1, 0, 1, 0]
[2, 0, 1, 1]
[3, 1, 0, 4]
[0, 0, 0, 3, 2]
[4, 0, 1, 2, 1]
  • Thank you (+1). Actually, for my compare function sorted(lists, cmp=compare) matches to sorted(lists, key=lambda lst: (-len(lst), lst), reverse = True) – Loom May 2 '16 at 19:26

mkrieger1's answer is preferable. But Python2 has the cmp keyword which allows you to simplify your code. Ignoring the delta part of your function the last three returns would become one.

def compare(lhs, rhs):
    delta = len(lhs) - len(rhs)
    if delta > 0:
        return 1
    elif delta < 0:
        return -1
    return cmp(rhs, lhs)

You can actually simplify it even further. You don't need to return 1 or -1 you just have to return a non-zero that is either positive or negative. This means you can use:

def compare(lhs, rhs):
    delta = len(lhs) - len(rhs)
    if delta:
        return delta
    return cmp(rhs, lhs)

You can actually 'simplify' this further by using or, this is as or returns the lhs if it is true otherwise the rhs.

def compare(lhs, rhs):
    return (len(lhs) - len(rhs)) or cmp(rhs, lhs)

Just to note or is lazy and so cmp(rhs, lhs) will only run if (len(lhs) - len(rhs)) equals zero.

Again using key is preferable, the above is just ways you can improve your function.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.