Finding the top K items in a list efficiently

Ten million items is a lot for real-time on-demand code. I rarely deal with more than a few hundred items. Let's compare:

    dataset_1mil = range(1000000)
    dataset_1k = range(1000)
    dataset_100 = range(100)

    [random.shuffle(d) for d in (dataset_1mil, dataset_1k, dataset_100)]


    %timeit sorted(dataset_1mil, reverse=True)[:10]
    # 1 loops, best of 3: 1.12 s per loop

    %timeit heapq.nlargest(10, dataset_1mil)
    # 1 loops, best of 3: 330 ms per loop

    %timeit heapSearch(dataset_1mil, 10)
    # 1 loops, best of 3: 268 ms per loop


    %timeit sorted(dataset_1k, reverse=True)[:10]
    # 1000 loops, best of 3: 302 us per loop

    %timeit heapq.nlargest(10, dataset_1k)
    # 1000 loops, best of 3: 248 us per loop

    %timeit heapSearch(dataset_1k, 10)
    # 1000 loops, best of 3: 346 us per loop


    %timeit sorted(dataset_100, reverse=True)[:10]
    # 10000 loops, best of 3: 22 us per loop

    %timeit heapq.nlargest(10, dataset_100)
    # 10000 loops, best of 3: 46.9 us per loop

    %timeit heapSearch(dataset_100, 10)
    # 10000 loops, best of 3: 128 us per loop

There you have it. Sorted is best for small datasets in the hundreds, break-even is in the thousands, heapSearch wins in the millions.

Datastructures are great, but be aware of the strengths and weaknesses of their implementations. Most recently I discovered that checking collisions in many small sets is faster with tuples (creating sets is rather slow). Test things with your data, not just "big data".

Bonus tip: Amortize when you can. If you're sorting your data anyways, then even the cleverest heap won't undo work already done.

Earlier this year I visited U of Illinois and sat in with a group of seniors who were working on a homework problem. I printed off the homework problem for myself but was not able to solve it since I had just learned about Big O notation in my high school Calculus class. I think this algorithm, if modified to select by rank instead of just top k items, might be the solution.

The problem in question is 2B:

    2. (30 pts.) You are given an array A with n distinct
    numbers in it, and another array B of 
    ranks i1 < i2 < : : : < ik. An element x of A has rank u
    if there are exactly u  1 numbers in
    A smaller than it. Design an algorithm that outputs the 
    k elements in A that have the ranks
    i1; i2; : : : ; ik.
    (B) (20 pts.) Describe a O(n log k) recursive algorithm  
    for this problem. Prove the bound
    on the running time of the algorithm

Source: http://www.cs.illinois.edu/class/sp11/cs473/hw/hw_03.pdf

Is that possible?

This can be further optimized with a custom heap implementation. Once there are k elements in the heap, we know that whenever we remove an element from the heap, we will immediately be adding a new one.

In a traditional heap implementation, popping is performed by replacing the root with the bottom-right-most element and heapifying down. This is potentially 2 * log(k) comparisons. Pushing is performed by adding the new element to the bottom-right and heapifying up, which is up to log(k) comparisons. We can combine the pop and push into a single operation and reduce the 3 * log(k) comparisons to just the 2 * log(k) comparisons. Instead of replacing the root with the bottom-right-most element, just replace it with the new element and heapify down. This not only reduces the worst-case number of comparison; it improves the expected number of comparisons since the bottom-right element is likely to still belong at the bottom and will be pushed down the entire tree, while the new element is more likely to belong somewhere shallower.

fun fact: mysql did not do this up to v5.6, afaict. This means a query like

    select * from ... order by non-index-column-or-calculated limit k

it would dump all the results into a temp table (possibly on disk) and then sort them, instead of keeping a current top-k buffer.

if K is fixed, as in the example from the article, this can be done in O(N) ...

I love discovering all these new python data structures. Last week, I realized how handy namedtuples are, and I will definitely use this.

When you have lazy evaluation in your tools, finding K extremal elements in list will be one-liner:

   getKSmallest k list = take k (sort list)

or even shorter in point-free notation:

   getKSmallest k = take k . sort

http://en.wikipedia.org/wiki/Selection_algorithm#Language_su...

for more flexibility, like taking arbitrary ranges of elements, it is possible to use partial qsort, that is pretty easy to implement (just don't recurse for ranges that are outside the range you want to sort).