Double loop takes time
<p>I have a script which takes a lot of time and can't finish so far after 2 days...
I parsed 1 file into 2 dictionaries as the following:</p>

<pre><code>gfftree = {'chr1':[(gene_id, gstart, gend),...], 'chr2':[(gene_id, gstart, gend),...],...}
TElocation = {'chr1':[(TE_id, TEstart, TEend),...], 'chr2':[(TE_id, TEstart, TEend),...],...}
</code></pre>

<p>.</p>

<p>--The aim is to find TE_id whose TEstart or TEend or both are located between gene_id' gstart and gend in each chr(key).</p>

<h1>The above should be changed to "find TE_id whose range(TEstart, TEend) overlaps with any gene_id's range(gstart,gend)"</h1>

<p>Here is my code:</p>

<pre><code>TE_in_TSS = []
for TErange in TElocation[chromosome]:
    TE_id, TEstart, TEend = TErange
    for item in gfftree[chromosome]:
        gene, gstart, gend = item       
        if len(list(set(range(int(gstart),int(gend)+1)) &amp; set(range(int(TEstart),int(TEend)+1)))) &gt; 0:
            TE_in_TSS.append((gene, TE_id, TEstart, TEend))
        else:
            pass
</code></pre>

<p>So far I'm sure this loop is fine with small data, but when it comes to bigger one like 800,000 TE_id and 4,000 gene_id, it takes time...and I don't know if it could finish...</p>

<p>Here is a solution using multi-threading, comparing code used for nested loop methods.</p>

<p>I created two csv's, one with 8k rows and one 800 rows of (int, float1,float2) random generated numbers and import as below:</p>

<pre><code>import time
import itertools 

start = time.time()

def f((TE_id, TEstart, TEend)):
    a=[]
    for gene, gstart, gend in gfftree['chr1']:
        if (gstart &lt;= TEstart &lt;=gend) or (gstart&lt;=TEend &lt;=gend):
            a.append((gene,TE_id,TEstart,TEend))
    return a

'''
#slow
TEinTSS = []
for TE_id, TEstart, TEend in TElocation['chr1']:
    for gene, gstart, gend in gfftree['chr1']:
        if (gstart &lt;= TEstart &lt;=gend) or (gstart&lt;=TEend &lt;=gend):
            TEinTSS.append((gene,TE_id,TEstart,TEend))
print len(TEinTSS)
print time.time()-start

#faster
TEinTSS = []
for things in TElocation['chr1']:
    TEinTSS.extend(f(things))
print len(TEinTSS)
print time.time()-start
'''

#fastest (especially with multi-core, multithreading)
from multiprocessing import Pool

if __name__ == '__main__':
    p=Pool()
    TEinTSS = list(itertools.chain.from_iterable(p.imap_unordered(f, b)))   
    print len(TEinTSS)
    print time.time() - start
</code></pre>

python for-loop