Find all common N-sized tuples in list of tuples
<p>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):</p>

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

<pre><code>(UUID, (tuple of N integers))
</code></pre>

<p>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:</p>

<ol>
<li>_id, UUID, tuple.as_a_string()</li>
<li>_id, UUID, 1st_elem, 2nd_elem, 3rd_3lem, ... 20th_elem</li>
</ol>

<p>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.**</p>

<p>For example, if we are given the two following 20-sized tuples:</p>

<pre><code>(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))
</code></pre>

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

<p>which is a 10-sized tuple, so the result is something like the following:</p>

<pre><code>(1, 2, (1,3,5,7,9,11,13,15,17,19))
</code></pre>

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

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

<p>But this procedure is <strong>very slow</strong>. 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%.</p>

<p>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?</p>

<p>Thanks in advance.</p>

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

<pre><code>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&gt;=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')
</code></pre>

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

<p>rows uses 200 bytes
K= 10 0.0009770393371582031 seconds</p>

<p>rows uses 1000 bytes
K= 50 0.0410161018371582 seconds</p>

<p>rows uses 2000 bytes
K= 100 0.15625 seconds</p>

<p>rows uses 10000 bytes
K= 500 3.610351085662842 seconds</p>

<p>rows uses 20000 bytes
K= 1000 14.931640863418579 seconds</p>

<p>rows uses 100000 bytes
K= 5000 379.5498049259186 seconds</p>

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

<p>Maybe I'll just get a bunch of negative votes!</p>

python algorithm sqlite numpy