Choosing python data structures to speed up algorithm implementation
Question: So I'm given a large collection (roughly 200k) of lists. Each contains a
subset of the numbers 0 through 27. I want to return two of the lists where
the product of their lengths is greater than the product of the lengths of any
other pair of lists. There's another condition, namely that the lists have no
numbers in common.

There's an algorithm I found for this (can't remember the source, apologies
for non-specificity of props) which exploits the fact that there are fewer
total subsets of the numbers 0 through 27 than there are words in the
dictionary.

The first thing I've done is looped through all the lists, found the unique
subset of integers that comprise it and indexed it as a number between 0 and
1<<28\. As follows:

    
    
    def index_lists(lists):
        index_hash = {}
        for raw_list in lists:
            length = len(raw_list)
    
            if length > index_hash.get(index,{}).get("length"):
               index = find_index(raw_list)
               index_hash[index] = {"list": raw_list, "length": length}
    
        return index_hash
    

This gives me the longest list and the length of the that list for each subset
that's actually contained in the collection of lists given. Naturally, not all
subsets from 0 to (1<<28)-1 are necessarily included, since there's not
guarantee the supplied collection has a list containing each unique subset.

What I then want, for each subset 0 through 1<<28 (all of them this time) is
the longest list that contains at most that subset. This is the part that is
killing me. At a high level, it should, for each subset, first check to see if
that subset is contained in the index_hash. It should then compare the length
of that entry in the hash (if it exists there) to the lengths stored
previously in the current hash for the current subset minus one number (this
is an inner loop 27 strong). The greatest of these is stored in this new hash
for the current subset of the outer loop. The code right now looks like this:

    
    
    def at_most_hash(index_hash):
        most_hash = {}
        for i in xrange(1<<28):  # pretty sure this is a bad idea
            max_entry = index_hash.get(i)
            if max_entry:
               max_length = max_entry["length"]
               max_word = max_entry["list"]
            else:
               max_length = 0
               max_word = []
            for j in xrange(28):  #  again, probably not great
               subset_index = i & ~(1<<j) # gets us a pre-computed subset
               at_most_entry = most_hash.get(subset_index, {})
               at_most_length = at_most_entry.get("length",0)
               if at_most_length > max_length:
                  max_length = at_most_length
                  max_list = at_most_entry["list"]
            most_hash[i] = {"length": max_length, "list": max_list}
        return most_hash
    

This loop obviously takes several forevers to complete. I feel that I'm new
enough to python that my choice of how to iterate and what data structures to
use may have been completely disastrous. Not to mention the prospective memory
problems from attempting to fill the dictionary. Is there perhaps a better
structure or package to use as data structures? Or a better way to set up the
iteration? Or maybe I can do this more sparsely?

The next part of the algorithm just cycles through all the lists we were given
and takes the product of the subset's max_length and complementary subset's
max length by looking them up in at_most_hash, taking the max of those.

Any suggestions here? I appreciate the patience for wading through my long-
winded question and less than decent attempt at coding this up.

In theory, this is still a better approach than working with the collection of
lists alone since that approach is roughly o(200k^2) and this one is roughly
o(28*2^28 + 200k), yet my implementation is holding me back.


Answer: Given that your indexes are just ints, you could save some time and space by
using lists instead of dicts. I'd go further and bring in
[NumPy](http://www.numpy.org/) arrays. They offer compact storage
representation and efficient operations that let you implicitly perform
repetitive work in C, bypassing a ton of interpreter overhead.

Instead of `index_hash`, we start by building a NumPy array where
`index_array[i]` is the length of the longest list whose set of elements is
represented by `i`, or `0` if there is no such list:

    
    
    import numpy
    
    index_array = numpy.zeros(1<<28, dtype=int)  # We could probably get away with dtype=int8.
    for raw_list in lists:
        i = find_index(raw_list)
        index_array[i] = max(index_array[i], len(raw_list))
    

We then use NumPy operations to bubble up the lengths in C instead of
interpreted Python. Things might get confusing from here:

    
    
    for bit_index in xrange(28):
        index_array = index_array.reshape([1<<(28-bit_index), 1<<bit_index])
        numpy.maximum(index_array[::2], index_array[1::2], out=index_array[1::2])
    
    index_array = index_array.reshape([1<<28])
    

Each `reshape` call takes a new view of the array where data in even-numbered
rows corresponds to sets with the bit at `bit_index` clear, and data in odd-
numbered rows corresponds to sets with the bit at `bit_index` set. The
`numpy.maximum` call then performs the bubble-up operation for that bit. At
the end, each cell `index_array[i]` of `index_array` represents the length of
the longest list whose elements are a subset of set `i`.

We then compute the products of lengths at complementary indices:

    
    
    products = index_array * index_array[::-1]  # We'd probably have to adjust this part
                                                # if we picked dtype=int8 earlier.
    

find where the best product is:

    
    
    best_product_index = products.argmax()
    

and the longest lists whose elements are subsets of the set represented by
`best_product_index` and its complement are the lists we want.

