Permute and count between nested dictionaries

Question

Goal:

1. Permute inner values between two dictionaries with matching outer key,
2. Save permuatations in counter,
3. Move to next outer key, update counter with new permutations.

Problem:

Many lookups on large dictionary (60 outer keys x 18000 inner key:value pairs) make existing code correct but slowwwww.

import collections

cnv = {'x': {'a':0, 'b':1, 'c':-1}, 'y': {'a':1, 'b':1, 'c':1}, 'z': {'a':-1, 'b':-1, 'c':-1}} 
rna = {'x': {'A':1, 'B':3, 'C':5}, 'y': {'A':1, 'B':3, 'C':5}, 'z': {'A':1, 'B':3, 'C':5}} 

cnv_loss_total = {}
for cell in cnv:
    cnv_gene_loss = set()
    for gene in cnv[cell]:
        if cnv[cell][gene] < 0:
            cnv_gene_loss.add(gene)
    cnv_loss_total[cell] = cnv_gene_loss

total_link_counter = collections.Counter()
for cell in rna:
    rna_gene_gain = set()
    for gene in rna[cell]:
            rna_gene_gain.add(gene)
    cell_combo = itertools.product(cnv_loss_total[cell], rna_gene_gain)
    for comboC, comboR in cell_combo:
        total_link_counter[comboC+'+'+comboR]+=rna[cell][comboR]

print (total_link_counter)
print(total_link_counter.values())

The code provides the desired output:

Counter({'c+C': 10, 'c+B': 6, 'b+C': 5, 'a+C': 5, 'a+B': 3, 'b+B': 3, 'c+A': 2, 'b+A': 1, 'a+A': 1})

There is also a memory bottleneck here:

--> 23         total_link_counter[comboC+'+'+comboR]+=rna[cell][comboR]
     24 
     25 print (total_link_counter)

MemoryError: 

But I intend on using much larger data (although similarly formatted data: either as a dict as dict or pandas dataframe). How can I optimize the above code to deal with the MemorError (and hopefully shorten runtime)?

Answer 1

You are building a lot of intermediate sorage that you don't really need, as you could simply iterate over both dictionaries simultaneously. Using the .items() method of dictionaries (or .iteritems() if you are using Python 2.x will also save you a bunch of dictionary look-ups:

total_link_counter = collections.Counter()

for cell, cgenes in cnv.items():
    rgenes = rna[cell]  # This will raise if cell not in rna!
    for cgene, cval in cgenes.items():
        if cval >= 0:
            continue
        for rgene, rval in rgenes.items():
            total_link_counter['+'.join((cgene, rgene))] += rval

You still have three nested loops, so this is unlikely to be very fast, but it should improve over your code, both in performance and memory use.

Answer 2

Here's a first pass at compacting your code, it should provide some speed improvements too:

cnv_loss_total = {cell: set(gene for gene in genes if genes[gene] < 0) for cell,genes in cnv.iteritems()}

total_link_counter = collections.Counter()
for cell,genes in rna.iteritems():
    cell_combo = itertools.product(cnv_loss_total[cell], set(genes.keys()))
    for comboC, comboR in cell_combo:
        total_link_counter[comboC+'+'+comboR] += genes[comboR]

By turning the first loop into a list comprehension, it avoids temporary variables and is more efficient in creating a set. Also, using iteritems() avoids generating the entire list of dictionary items and yields one pair at a time.

In the second loop, the rna_gene_gain variable is eliminated by using set(genes.keys), which is again more efficient in building the set.