蟒蛇字典時間謎

Question

我正在做序列比對，並遇到了一個相當神祕的與我的字典數據結構的起源相關的時間問題。 基本上，我有功能alignment(s1, s2, scores) 它需要兩個字符串s1和s2，併爲每個可能的20個氨基酸對和一個缺口' - '得分矩陣（作爲蟒蛇字典）。所以scores有440個鍵（char1，char2），帶有整數值。

這裏是謎：如果我從一個文本文件中讀取scores（稱之爲scores1）和一些1000上下的長串S1運行 alignment(s1, s2, scores1) ，S2，我得到以下計時（使用CPROFILE而不是氨基酸顯示功能輸出）：

2537776 function calls in 11.796 seconds

現在，如果我在文件中創建完全相同的字典（稱之爲scores2）並運行 alignment(s1, s2, scores2) 我得到的結果相同的結果，但在3倍的時間少：

2537776 function calls in 4.263 seconds

兩種情況下的輸出都是相同的，只是時間不同而已。 運行print scores1 == scores2結果爲True，因此它們包含相同的信息。 我驗證了使用訪問字典 的任意函數（而不是對齊）在兩種情況下多次產生相同的因子3的時間差異。

必須有一些元數據與源自哪裏的字典相關，這會減慢我的函數（當來自文件時），即使在這兩種情況下我實際上都是在文件中讀取的。 我試圖通過scores1 = dict(scores1)等創建一個新的字典對象，但同樣的時間差異依然存在。相當混亂，但我敢肯定，如果我能弄明白的話，這裏將會有一個很好的教訓。

scores1 = create_score_dict_from_file('lcs_scores.txt') 
scores2 = create_score_dict(find_alp(s1, s2), match=1, mismatch=0, indel=0) 
print scores1 == scores2 # True 
alignment(s1, s2, scores1) # gives right answer in about 12s 
alignment(s1, s2, scores2) # gives right answer in about 4s 

編輯：添加代碼和下面的結果：

這裏是代碼的簡化版本：

import numpy as np 
from time import time 

def create_scores_from_file(score_file, sigma=0): 
    """ 
    Creates a dict of the scores for each pair in an alphabet, 
    as well as each indel (an amino acid, paired with '-'), which is scored -sigma. 

    """ 
    f = open(score_file, 'r') 
    alp = f.readline().strip().split() 
    scores = [] 
    for line in f: 
     scores.append(map(int, line.strip().split()[1:])) 
    f.close() 
    scores = np.array(scores) 
    score_dict = {} 
    for c1 in range(len(alp)): 
     score_dict[(alp[c1], '-')] = -sigma 
     score_dict[('-', alp[c1])] = -sigma 
     for c2 in range(len(alp)): 
      score_dict[(alp[c1], alp[c2])] = scores[c1, c2] 
    return score_dict 

def score_matrix(alp=('A', 'C', 'G', 'T'), match=1, mismatch=0, indel=0): 
    score_dict = {} 
    for c1 in range(len(alp)): 
     score_dict[(alp[c1], '-')] = indel 
     score_dict[('-', alp[c1])] = indel 
     for c2 in range(len(alp)): 
      score_dict[(alp[c1], alp[c2])] = match if c1 == c2 else mismatch 
    return score_dict 

def use_dict_in_function(n, d): 
    start = time() 
    count = 0 
    for i in xrange(n): 
     for k in d.keys(): 
      count += d[k] 
    print "Time: ", time() - start 
    return count 

def timing_test(): 
    alp = tuple('A C D E F G H I K L M N P Q R S T V W Y'.split()) 
    scores1 = create_scores_from_file('lcs_scores.txt') 
    scores2 = score_matrix(alp, match=1, mismatch=0, indel=0) 
    print type(scores1), id(scores1) 
    print type(scores2), id(scores2) 
    print repr(scores1) 
    print repr(scores2) 
    print type(list(scores1)[0][0]) 
    print type(list(scores2)[0][0]) 
    print scores1 == scores2 
    print repr(scores1) == repr(scores2) 
    n = 10000 
    use_dict_in_function(n, scores1) 
    use_dict_in_function(n, scores2) 

if __name__ == "__main__": 
    timing_test() 

的結果是：

<type 'dict'> 140309927965024 
<type 'dict'> 140309928036128 
{('S', 'W'): 0, ('G', 'G'): 1, ('E', 'M'): 0, ('P', '-'): 0,... (440 key: values) 
{('S', 'W'): 0, ('G', 'G'): 1, ('E', 'M'): 0, ('P', '-'): 0,... (440 key: values) 
<type 'str'> 
<type 'str'> 
True 
True 
Time: 1.51075315475 
Time: 0.352770090103 

這裏是文件內容lcs_scores.txt：

A C D E F G H I K L M N P Q R S T V W Y 
A 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
C 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
D 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
E 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
F 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
G 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
H 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
I 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 
K 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 
L 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
M 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 
N 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
P 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 
Q 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 
R 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 
S 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 
T 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 
V 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 
W 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
Y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 

Answer 1

哪個版本的Python？並打印每個字典的repr()，以確保他們真的是相同的（不是只是，他們比較相等）。無法猜測。例如，可能您使用的是Python 2，在一種情況下，您的char1和char2是純字符串，但在另一種情況下，它們是Unicode字符串。然後，比較會說它們是相同的，但repr()將示區別：

>>> d1 = {"a": 1} 
>>> d2 = {u"a": 1} 
>>> d1 == d2 
True 
>>> print repr(d1), repr(d2) 
{'a': 1} {u'a': 1} 

在任何情況下，在CPython的是絕對哪裏任何對象是從哪裏來的內部沒有「元數據」的記錄。

編輯 - 一些嘗試

出色的工作，消減下來的問題！這成爲一種樂趣:-)我希望你嘗試一下。首先註釋掉該行：

scores = np.array(scores) 

然後改變這一行：

  score_dict[(alp[c1], alp[c2])] = scores[c1, c2] 

到：

  score_dict[(alp[c1], alp[c2])] = scores[c1][c2] 
                ^^^^^^ 

當我做到這一點，這兩種方法返回基本上是相同的時間。我不是numpy專家，但我的猜測是，你的「來自文件」代碼使用的是機器原生的numpy整數類型的字典值，並且在使用這些值時將這些整數轉換爲Python整數有很大的開銷。

或許不是 - 但是這是我的猜測，現在，我堅持它;-)