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>There doesn't appear to be much hope for this:  forgetting the <code>combinations()</code> part, you need to check the intersection of every pair of <code>K</code> tuples.  There are <code>choose(K, 2) = K*(K-1)/2</code> pairs, so with a million tuples there are nearly 500 billion pairs.</p>

<p>One low-level trick you can play is to represent a tuple as an integer instead of as a set, where bit <code>2**i</code> is set in the integer when and only when <code>i</code> is in the tuple.  Since you said in comments that a tuple contains no duplicates, and each tuple element is in <code>range(1, 100)</code>, 100-bit integers are sufficient (it could be cut to 99 bits, but not worth the bother).</p>

<p>The point is that bitwise "&amp;" of integers goes a lot faster than set intersection.  On my box, about 7 times faster.  Here's some code to illustrate the concept, and some sloppy timing results (run on a machine doing lots of other stuff simultaneously):</p>

<pre><code>def build(K, values, N):
    from random import sample
    sets = []
    ints = []
    for i in range(K):
        t = sample(values, N)
        sets.append(set(t))
        ints.append(sum(1 &lt;&lt; i for i in t))
    return sets, ints

def run(K, values, N):
    from time import time
    as_sets, as_ints = build(K, values, N)
    for meth, collection in [("sets", as_sets),
                             ("ints", as_ints)]:
        s = time()
        for i in range(K-1):
            base = collection[i]
            for j in range(i+1, K):
                x = base &amp; collection[j]
        t = time()
        print("K", K, meth, t-s)

for K in 5000, 10000, 20000:
    run(K, range(1, 100), 20)
</code></pre>

<p>And output:</p>

<pre><code>K 5000 sets 7.322501182556152
K 5000 ints 1.0357279777526855
K 10000 sets 30.60071086883545
K 10000 ints 4.150524377822876
K 20000 sets 128.24610686302185
K 20000 ints 15.933331727981567
</code></pre>

<p>Note that, as expected, runtime for either approach is quadratic in K (so doubling K takes about 4 times as long; and making K 10 times larger would increase runtime by a factor of about 10**2 = 100).</p>

<p>While intersection is much faster with ints, determining the cardinality of the result is slower.  There are many ways to do that, but "the best" depends on the expected distribution and your tolerance for coding pain ;-)  Here's an overview of the <a href="https://en.wikipedia.org/wiki/Hamming_weight" rel="nofollow">major methods</a>.</p>

python algorithm sqlite numpy