Find all common N-sized tuples in list of tuples
Question: I have to create an an application that does the following (I have to parse
the data only once and store them in a database):

I am given K tuples (with K over 1000000) and each tuple is in the form of

    
    
    (UUID, (tuple of N integers))
    

Lets assume that N equals 20 for every k-tuple and that every 20-sized tuple
is sorted. I have saved all my data in a database in the following two forms
(2 different tables), so that I can process them more easily:

  1. _id, UUID, tuple.as_a_string()
  2. _id, UUID, 1st_elem, 2nd_elem, 3rd_3lem, ... 20th_elem

The goal is to find all 10-sized tuples from the list of tuples, such that
every one of those tuples to exist in more than one 20-sized tuple.**

For example, if we are given the two following 20-sized tuples:

    
    
    (1, (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,161,17,18,19,20))
    (2, (1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39))
    

the common tuple is: (1,3,5,7,9,11,13,15,17,19)

which is a 10-sized tuple, so the result is something like the following:

    
    
    (1, 2, (1,3,5,7,9,11,13,15,17,19))
    

In order to accomplish this, what I am currently doing is (in Python 3):

  * Create a set with the elements of the 20-sized tuple of the 1st row in the database.
  * Create a set for each row with the elements of the 20-sized tuple of the rest rows in the database.
  * For each set in the second list of sets, I do the intersection with the first set.
  * Then I create the combination of the intersection with 10 elements _(in Python it is itertools.combinations(new_set, 10) )_ , which gives me the result that I want.

But this procedure is **very slow**. Even using multiprocessing to utilize my
8 CPU cores fully, each computing for a different number, it takes forever. I
have the program running for 2 days now and it is only in 20%.

Do you have any ideas on how to optimize the process? Would NumPy arrays help
with the speed of execution? Is there any way in SQL to calculate what I want
for each row, even one row at a time?

Thanks in advance.


Answer: It appears that you could put the tuples into the rows of a matrix and make a
map from row numbers to UUIDs. Then it's feasible to store all of the tuples
in a numpy array since the elements of the tuples are small. numpy has code
capable of computing the intersections between rows of such an array. This
code generates combinations to process as tuples first, then it makes the
comparisons.

    
    
    from itertools import combinations
    import numpy as np
    from time import time
    
    minInt=1
    maxInt=100
    tupleSize=20
    intersectionSize=10
    
    K=100
    rows=np.zeros((K,tupleSize),dtype=np.int8)
    print ('rows uses', rows.nbytes, 'bytes')
    
    for i,c in enumerate(combinations(range(minInt,maxInt),tupleSize)):
        if i>=K:
            break
        for j,_ in enumerate(c):
            rows[i,j]=_
    
    t_begin=time()
    for i in range(K-1):
        for j in range(i+1,K):
            intrsect=np.intersect1d(rows[i],rows[j],True)
            if intrsect.shape[0]==intersectionSize:
                print (i,j,intrsect)
    t_finish=time()
    
    print ('K=', K, t_finish-t_begin, 'seconds')
    

Here are some sample measurements made on my old two-core P4 clunker at home.

rows uses 200 bytes K= 10 0.0009770393371582031 seconds

rows uses 1000 bytes K= 50 0.0410161018371582 seconds

rows uses 2000 bytes K= 100 0.15625 seconds

rows uses 10000 bytes K= 500 3.610351085662842 seconds

rows uses 20000 bytes K= 1000 14.931640863418579 seconds

rows uses 100000 bytes K= 5000 379.5498049259186 seconds

If you run the code on your machine you can extrapolate. I don't know if it
would make your calculation feasible or not.

Maybe I'll just get a bunch of negative votes!

