比較兩個字典的效率

Question

以下程序在兩個文件（txt，〜10MBa）上運行約22小時。每個文件都有大約100K行。有人能給我一個關於我的代碼效率低下的指示，也許是一種更快的方法。輸入字典是有序的，維護秩序是必要的：

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

只有一個有序字典和「Sucrose_rivacombined.txt」。應該是超級快

編輯完整的代碼（不知道你的輸出線格式）

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與此作爲輸入是可哈希：

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將會需要比較反對名單，這是組合的每一個元素。 （你做的，因爲這not檢查N^2間的比較。）

你也許可以完全取代的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