1
\$\begingroup\$

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)?

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. \$\endgroup\$ – Mathias Ettinger Apr 22 '16 at 22:20
  • \$\begingroup\$ Good point. I edited my answer to include explanations. \$\endgroup\$ – Brent Washburne Apr 22 '16 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.