python dict timing тайна

Question

Я делаю выравнивание последовательностей и столкнулся с довольно загадочным вопросом времени, связанным с началом моей структуры данных dict. В принципе, у меня есть функция alignment(s1, s2, scores) , которая берет две строки s1 и s2 и матрицу подсчета (как питон-дикт) для каждой возможной пары из 20 аминокислот и пробел '-'. Таким образом, scores имеет 440 ключей (char1, char2), с целыми значениями.

Вот тайна: Если я читаю scores из текстового файла (назовем его scores1) и запустить alignment(s1, s2, scores1) для некоторых 1000-иш длинных строк s1, s2 аминокислот я получаю следующие сроки (с использованием Cprofile и не показывая выход функции):

2537776 function calls in 11.796 seconds

Теперь, если я создаю точно такой же Dict в моем файле (назовем его scores2) и запустить alignment(s1, s2, scores2) я получаю те же выходные результаты, но в 3 раза меньше времени:

2537776 function calls in 4.263 seconds

Выход в обоих случаях идентичен, это просто время, которое отличается. Запуск print scores1 == scores2 приводит к True, поэтому они содержат идентичную информацию. Я проверил, что использование произвольной функции (вместо выравнивания), которая обращается к dict , во много раз дает тот же коэффициент из 3 временных расхождений в двух случаях.

Должно быть какое-то метаданные, связанные с тем, откуда возникли диктофоны, что замедляет мою функцию (когда из файла), хотя в обоих случаях я действительно читаю в файле. Я попытался создать новый объект dict для каждого через 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 

EDIT: Добавлен код и результаты ниже:

Вот это упрощенная версия кода:

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 нет абсолютно никакой внутренней «метаданных» записи, где любых объекта пришел.

EDIT - что-то попробовать

Замечательная работа сводила вниз проблема! Это становится приятным :-) Я бы хотел, чтобы вы что-то попробовали. Во-первых закомментировать эту строку:

scores = np.array(scores) 

Затем изменить эту строку:

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

к:

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

Когда я делаю, что эти два метода возвращают по существу идентичные времена. Я не эксперт numpy, но я предполагаю, что ваш код «из файла» использует собственный целочисленный тип машины numpy для значений dict и что для их преобразования в целые числа Python есть существенные накладные расходы, когда используются значения.

Или, может быть, нет - но это мое предположение, на данный момент, и я приклеить к нему ;-)