蟒蛇字典时间谜

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整数有很大的开销。

或许不是 - 但是这是我的猜测，现在，我坚持它;-)