Медлительность при итерации над namedtuple и dicts для определенных пар

Question

Этот код быстро запускается на образцах данных, но при итерации по большому файлу он работает медленно, возможно, из-за вложенных циклов. Есть ли другая причина, почему повторение элементов в defaultdict происходит медленно?

import itertools 

sample_genes1={"0002":["GENE1", "GENE2", "GENE3", "GENE4"], 
       "0003":["GENE1", "GENE2", "GENE3", "GENE6"], 
       "0202":["GENE4", "GENE2", "GENE1", "GENE7"]} 

def get_common_gene_pairs(genelist): 
    genedict={} 
    for k,v in sample_genes1.items(): 
     listofpairs=[] 
     for i in itertools.combinations(v,2): 
      listofpairs.append(i) 
      genedict[k]=listofpairs 
    return genedict 

from collections import namedtuple,defaultdict 
def get_gene_pair_pids(genelist): 
    i=defaultdict(list) 
    d=get_common_gene_pairs(sample_genes1) 
    Pub_genes=namedtuple("pair", ["gene1", "gene2"]) 
    for p_id,genepairs in d.iteritems(): 
     for p in genepairs: 
      thispair=Pub_genes(p[0], p[1]) 
      if thispair in i.keys(): 
       i[thispair].append(p_id) 
      else: 
       i[thispair]=[p_id,] 
    return i 

if __name__=="__main__": 
    get_gene_pair_pids(sample_genes1) 

Answer 1

Одна большая проблема: эта линия:

if thispair in i.keys(): 

не воспользоваться словарем, это линейный поиск. Бросьте вызов keys(), пусть словарь сделать его быстрый поиск:

if thispair in i: 

НО поскольку i является ДИКТ по ​​умолчанию, которое создает list когда ключ не существует, просто замените:

if thispair in i.keys(): 
    i[thispair].append(p_id) # i is defaultdict: even if thispair isn't in the dict, it will create a list and append p_id. 
else: 
    i[thispair]=[p_id,] 

этим простое утверждение:

i[thispair].append(p_id) 

(это даже быстрее, потому что есть только один хеширование p_id)

подвести итог:

• не делают thispair in i.keys(): это медленно, в Python 2, или 3, defaultdict или не
• вы определили defaultdict, но ваш код просто приняло dict , который работает, но медленнее.

Примечание: без defaultdict вы могли бы просто удалили .keys() или сделать это с помощью простого dict:

i.setdefault(thispair,list) 
i[thispair].append(p_id) 

(здесь пункт по умолчанию, зависит от ключа)

Помимо:

def get_common_gene_pairs(genelist): 
    genedict={} 
    for k,v in sample_genes1.items(): # should be genelist, not the global variable, you're not using the genelist parameter at all 

И вы не используете val ues образца_genes1 вообще в вашем коде.

Answer 2

Добавление к Jean's answer, ваша get_common_gene_pairs функция может быть оптимизирована с помощью Dict понимания как:

def get_common_gene_pairs(genelist): 
    return {k : list(itertools.combinations(v,2)) for k,v in genelist.items()} 

list.append() гораздо больше времени по сравнению с его список comprhension счетчик часть , Кроме того, вам не нужно перебирать itertools.combinations(v,2), чтобы преобразовать его в список. Тип-литье до list делает это.

Вот сравнение я между список понимания и list.append() в ответ на Comparing list comprehensions and explicit loops, в случае, если вы заинтересованы в принятии смотреть.