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>Bill, I think this creates a more random mix.  Your combinations version steps systematically through the choices.  With small K the intersection size is close to <code>tupleSize</code>.</p>

<pre><code>choices = np.arange(minInt, maxInt)
for i in range(K):
    rows[i,:] = np.random.choice(choices, tupleSize, replace=False)
</code></pre>

<p>Using <code>sets</code> is about 4x faster than <code>np.intersect1d</code>.</p>

<pre><code>sets = [set(row) for row in rows]
dd = collections.defaultdict(int)
for i in range(K-1):
    for j in range(i+1,K):
        intrsect=sets[i].intersection(sets[j])
        dd[len(intrsect)] += 1
</code></pre>

<p>I switched to collecting the intersection size, as it is more interesting and less sensitive to iteration strategy. </p>

<p>With K=5000:</p>

<pre><code>K= 5000 221.06068444252014 seconds
{0: 77209, 1: 514568, 2: 1524564, 3: 2653485, 4: 3044429, 5: 2436717, 6: 1408293, 7: 596370, 8: 188707, 9: 44262, 10: 7783, 11: 1012, 12: 93, 13: 8}
</code></pre>

<p>The smaller time is just for the <code>sets</code> creation step; that's very fast.</p>

<pre><code>K= 5000 0.058181047439575195 46.79403018951416 seconds
{0: 77209, 1: 514568, 2: 1524564, 3: 2653485, 4: 3044429, 5: 2436717, 6: 1408293, 7: 596370, 8: 188707, 9: 44262, 10: 7783, 11: 1012, 12: 93, 13: 8}
</code></pre>

<p>for larger K</p>

<pre><code>K= 10000 818.3419544696808 seconds
{0: 309241, 1: 2058883, 2: 6096016, 3: 10625523, 4: 12184030, 5: 9749827, 6: 5620209, 7: 2386389, 8: 752233, 9: 176918, 10: 31168, 11: 4136, 12: 407, 13: 18, 14: 2}
K= 10000 0.09764814376831055 151.11484718322754 seconds
</code></pre>

python algorithm sqlite numpy