How are "key" functions more efficient than comparison functions in python's sorted?

user_2718864 0
Viewed 1646

In the Transforming Code into Beautiful, Idiomatic Python video (link starts at 10:07), the speaker says that using key instead of the cmp comparison function for sorting is more efficient. To paraphrase: he states that because there are O(nlog(n)) comparisons, a comparison function would be called 20m times for a 1m element list (log2(1m) ~ 20) while using key is better because it is called exactly once per key.

I understand his point about how using key is more readable, but I don't get how he determined that it's called once per key. I would have thought that under the hood, a sorting function that has a key parameter would look something like this:

def sort(sequence, key=None):
    if key is None:
        key = lambda x: x
    def compare(first, second):
        if key(first) < key(second): return -1
        if key(second) < key(first): return 1
        return 0
    # ... implement sorting algorithm

And so it would amount to the same time complexity whether we use a key function or a comparison function.

How is the key function only called once per element, if there are O(nlog(n)) comparisons? Is this a Timsort implementation detail?

Edit:

To address the comment asking for an example:

In python2, the sorted function accepted a cmp argument, something like this:

def compare(first, second):
    if len(first) < len(second): return -1
    if len(second) < len(first): return 1
    return 0

sorted(my_list, cmp=compare)

However, you could also pass a key function if you wanted. So, to achieve the same effect as above, you would do this:

sorted(my_list, key=len)

In the video, the author claims that the second option is more efficient than the first.

python-3.x sorting python performance
2 Answers

Before key was supported directly by sorted and list.sort, there was an idiom that allowed you to get its benefits anyway. The idiom was called Decorate-Sort-Undecorate (and it is apparently also known as a Schwartzian Transform).

Here's how it works:

def sort_with_key(data, keyfunc):
    decorated_data = [(keyfunc(x), i, x) for i, x in enumerate(data)]
    decorated_data.sort()
    return [x for key, i, x in decorated_data]

The three lines of the function correspond to the three parts of the idiom's name.

  1. The first line "decorates" the data by making a tuple combining a key value and an tiebreaker index with each item from the input. This is the only place the key function gets called, so there are only O(len(data)) calls.

  2. The second step is easy. We sort the decorated list of tuples using the default comparison method. Since tuples are compared lexicographically, for most pairs of items only the key values need to be compared to each other. If there are any ties between key values, the index value in the middle of the tuple will break it (always in such a way that the items remain in the same relative order that they were in in the input list, making it a stable sort). The items from data are never compared, since the tiebreaker values will always differ (since they're the indexes of the original list).

  3. The last steps is simple to understand as well. We just discard the key and tiebreaker values, producing a list that contains only the original items, in the newly sorted order.

When a key parameter was added to list.sort and sorted, it made the sort functions able to do the whole thing for you automatically. I'm not aware of the exact details of how the key value is stored (you can read the source if you really must know), but its effects are the same as the DSU idiom. The key function is called once on each value in the input list, and its results are saved to be compared multiple times later on, when the actual sorting is happening.

user_14050650

From documentation:

Starting with Python 2.4, both list.sort() and sorted() added a key parameter to specify a function to be called on each list element prior to making comparisons.

Note the word prior to: The keys are calculated not instead of calling cmp, but before it. Calculating the keys takes O(n), but the sorting takes O(n log(n)), so the overall complexity of sorting is still O(n log(n)).

Edited

The presenter suggests calculating the string lengths before sorting (via keys), which indeed requires n calls to len. If the same function is called during sorting (via cmp), the number of calls will be at least 2 n log(n).

In short, the number of comparisons is the same in both cases, but the number of calls to len differs.

user_44929320
Related