5
\$\begingroup\$

Given an dictionary with lists as values this piece of code is dedicated to find the n keys with the longest lists as values. It works, but there has to be a more elegant solution.

def get_n_longest_values(dictionary, n):
    result = []

    for key, value in dictionary.items():
        if len(result) < n:
            result.append((key, len(value)))
        else:
            # (index, length) of smallest element
            smallest = (10e10, 10e10)
            for index in range(0, n):
                if result[index][1] < smallest[1]:
                    smallest = (index, result[index][1])

            if len(value) > smallest[1]:
                result[smallest[0]] = (key, len(value))

    return result
\$\endgroup\$
0

1 Answer 1

5
\$\begingroup\$

Using the following test case, your code takes about 1 ms on my machine:

In [1]: import itertools
In [2]: import string

In [3]: d = dict(zip(itertools.product(string.ascii_lowercase, repeat=10),
             ([0] * i for i in range(1000))))
In [4]: %timeit get_n_longest_values(d, 3))
1000 loops, best of 3: 1.06 ms per loop

First, a short style comment: In Python, range has an implicit 0 as its first argument, so range(0, n) is the same as range(n).

You are doing this very manually, while it can be a bit faster when using built-in functions. I would first sort the items of the dictionary by the length of the values. (You cannot avoid going over the dictionary once. However this wastes some cycles, because it is a full sort, instead of a partial sort). Then you can just slice the sorted list and return the length of the values:

def get_n_longest_values_g(dictionary, n):
    longest_entries = sorted(
        dictionary.items(), key=lambda t: len(t[1]), reverse=True)[:n]
    return [(key, len(value)) for key, value in longest_entries]

This is much more readable and for the given test case performs better than your code by about a factor of 2:

In [5]: %timeit get_n_longest_values_g(d, 3)
1000 loops, best of 3: 514 µs per loop

Note that for this function, the output is actually sorted (descending), whereas yours is not.

Even for larger dictionaries, my function outperforms yours:

In [12]: import random
In [13]: d = dict(zip(itertools.product(string.ascii_lowercase, repeat=10), ([0] * random.randrange(10000) for i in range(10000))))
In [14]: %timeit get_n_longest_values(d, 3)
100 loops, best of 3: 10.2 ms per loop

In [15]: %timeit get_n_longest_values_g(d, 3)
100 loops, best of 3: 6.61 ms per loop

When n grows, your code becomes ever slower, because you iterate over the whole result in the worst case, whereas my code always sorts the whole dictionary anyways (same d as in the previous case):

In [18]: %timeit get_n_longest_values(d, 100)
10 loops, best of 3: 109 ms per loop

In [19]: %timeit get_n_longest_values_g(d, 100)
100 loops, best of 3: 6.27 ms per loop

There are a few possible routes of improvements left for this code. One could already at the beginning generate pairs of len(values), key, which can then be naturally sorted by Python, which should be slightly faster, as noted by @Peilonrayz in the comments. So, something like this:

def get_n_longest_values_g2(dictionary, n):
    return sorted([(len(value), key) for key, value in dictionary.items()],
                  reverse=True)[:n]

It is slightly slower than my previous function:

In [32]: %timeit get_n_longest_values_g2(d, 100)
100 loops, best of 3: 11.7 ms per loop

It has also a changed output (len(values), key, instead of key, len(values)).

Another possibility is to use your basic code and maintain a sorted result, so we can use binary search to insert the newest value and pop the smallest pair if needed, using the bisect module:

import bisect


def get_n_longest_values_gb(dictionary, n):
    result = []

    for key, value in dictionary.items():
        bisect.insort(result, (len(value), key))
        if len(result) > n:
            result.pop(0)

    return result

This performs somewhere between the other two approaches:

In [42]: %timeit get_n_longest_values_gb(d, 100)
100 loops, best of 3: 9.42 ms per loop

Note that its output is also reversed. It is limited by list.insert (which bisect.insort calls internally) being \$\mathcal{O}(n)\$ (as is list.pop(0), which we could get around by using a collections.deque, but a deque also has \$\mathcal{O}(n)\$ insert).

Lastly, one could use the heapq module, which has a nlargest function:

import heapq

def get_n_longest_values_gh(dictionary, n):
    return heapq.nlargest(n, ((len(value), key) for key, value in dictionary.items()))

This is the fastest for this particular test case, outperforming the sorted approach:

In [32]: %timeit get_n_longest_values_gh(d, 100)
100 loops, best of 3: 3.16 ms per loop

Note that its output is also reversed.

As stated in an answer to a similar question:

The latter two functions perform best for smaller values of n. For larger values, it is more efficient to use the sorted() function. Also, when n==1, it is more efficient to use the built-in min() and max() functions. If repeated usage of these functions is required, consider turning the iterable into an actual heap.

\$\endgroup\$
2
  • \$\begingroup\$ @Peilonrayz Added heapq, for the fun of it. It is actually the fastest for this particular test case :) \$\endgroup\$
    – Graipher
    Jun 6, 2017 at 10:49
  • 1
    \$\begingroup\$ Damn, that's cool. I can't think of any other way to do this problem with the built-in Python modules. So one of these has to be the best at some point :) \$\endgroup\$
    – Peilonrayz
    Jun 6, 2017 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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