Эффективность сравнения двух словарей

Question

Следующая программа работает около ~ 22 часов на двух файлах (txt, ~ 10MB ea.). Каждый файл имеет около ~ 100 тыс. Строк. Может ли кто-нибудь дать мне указание на то, насколько неэффективен мой код и, возможно, более быстрый метод. Входные ДИКТ упорядочены и сохранение порядка необходимо:

import collections 

def uniq(input): 
    output = [] 
    for x in input: 
    if x not in output: 
     output.append(x) 
    return output 

Su = {} 
with open ('Sucrose_rivacombined.txt') as f: 
    for line in f: 
     (key, val) = line.split('\t') 
     Su[(key)] = val 
    Su_OD = collections.OrderedDict(Su) 

Su_keys = Su_OD.keys() 
Et = {} 

with open ('Ethanol_rivacombined.txt') as g: 
    for line in g: 
     (key, val) = line.split('\t') 
     Et[(key)] = val 
    Et_OD = collections.OrderedDict(Et) 

Et_keys = Et_OD.keys() 

merged_keys = Su_keys + Et_keys 
merged_keys = uniq(merged_keys) 

d3=collections.OrderedDict() 

output_doc = open("compare.txt","w+") 

for chr_local in merged_keys: 
    line_output = chr_local 
    if (Et.has_key(chr_local)): 
     line_output = line_output + "\t" + Et[chr_local] 
    else: 
     line_output = line_output + "\t" + "ND" 
    if (Su.has_key(chr_local)): 
     line_output = line_output + "\t" + Su[chr_local] 
    else: 
     line_output = line_output + "\t" + "ND" 

    output_doc.write(line_output + "\n") 

входных файлов следующим образом: не каждый ключ присутствует в обеих файлах

Su: 
chr1:3266359 80.64516129 
chr1:3409983 100 
chr1:3837894 75.70093458 
chr1:3967565 100 
chr1:3977957 100 


Et: 
chr1:3266359 95 
chr1:3456683 78 
chr1:3837894 54.93395855 
chr1:3967565 100 
chr1:3976722 23 

Я хотел бы выход выглядеть следующим образом:

chr1:3266359 80.645 95 
chr1:3456683 ND  78 

Answer 1

Вам не нужна ваша уникальная функция.

псевдокод как:

1. файла для чтения 2, как OrderedDict
2. процесса файл 1 выписывая это элемент (уже заказал правильно)
3. поп, с defalut из файла 2 для последней части выходная линия
4. после того, как один файл потребляется процесс Упорядоченный ДИКТ из файла 2

Аль так, список любви постижения ... вы можете прочитать файл с:

OrderedDict(line.strip().split('\t') for line in open('Ethanol_rivacombined.txt')) 

Только один упорядоченный Dict и «Sucrose_rivacombined.txt» никогда даже не делает его в память. должны быть супер быстро

EDIT полный код (не уверен, что выходной формат строки)

from collections import OrderedDict 

Et_OD = OrderedDict(line.strip().split('\t') for line in open('Ethanol_rivacombined.txt')) 

with open("compare.txt","w+") as output_doc: 
    for line in open('Sucrose_rivacombined.txt'): 
     key,val = line.strip().split('\t') 
     line_out = '\t'.join((key,val,Et_OD.pop(key,'ND'))) 
     output_doc.write(line_out+'\n') 

    for key,val in Et_OD.items(): 
     line_out = '\t'.join((key,'ND',val)) 
     output_doc.write(line_out+'\n') 

Answer 2

Заменить uniq с этим, как входы hashable:

def uniq(input): 
    output = [] 
    s = set() 
    for x in input: 
    if x not in s: 
     output.append(x) 
     s.add(x) 
    return output 

Это уменьшит почти O(n^2) процесс до почти O(n).

Answer 3

вашего output список, но ваш вклад словари: их ключи гарантированно уникальны, но ваш not in output будет необходимо сравнить с каждый элементом списка, который является комбинаторным. (Вы делаете п^2 сравнений из-за этого not проверки.)

Вы могли бы полностью заменить Uniq с:

Su_OD.update(Et_OD) 

Это работает для меня:

from collections import OrderedDict 

one = OrderedDict() 
two = OrderedDict() 

one['hello'] = 'one' 
one['world'] = 'one' 

two['world'] = 'two' 
two['cats'] = 'two' 

one.update(two) 

for k, v in one.iteritems(): 
    print k, v 

выход:

hello one 
    world two 
    cats two