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 1

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 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.

Answer 2

This is a bit too long for a comment so I will post it as an answer. One more direct way to index your subsets as integers is to use "bitsets" with each bit in the binary representation corresponding to one of the numbers.

For example, the set {0,2,3} would be represented by 2⁰ + 2² + 2³ = 13 and {4,5} would be represented by 2⁴ + 2⁵ = 48

This would allow you to use simple lists instead of dictionaries and Python's generic hashing function.