Compare function for lists

Question

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?

Answer 1

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]

• Loom: Thank you (+1). Actually, for my compare function sorted(lists, cmp=compare) matches to sorted(lists, key=lambda lst: (-len(lst), lst), reverse = True)

Answer 2

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.