Ошибка производительности на Python

Question

У меня проблема с производительностью на Python. В нижеприведенном фрагменте есть 4 вложенных цикла, повторяющихся над OrderedDict, matrix_col, который содержит 11000 элементов. Другая итерация проходит через defaultdict, trans, который также имеет ~ 11000 элементов в нем. Выполнение этого процесса занимает слишком много времени. Я ценю, если кто-нибудь может посоветовать, как улучшить производительность.

import string 
from collections import namedtuple 
from collections import defaultdict 
from collections import OrderedDict 
import time 

trans = defaultdict(dict) 
... 
matrix_col = OrderedDict(sorted(matrix_col.items(), key=lambda t: t[0])) 
trans_mat = [] 
counter = 0 

for u1, v1 in matrix_col.items(): 
    print counter, time.ctime() 
    for u2, v2 in matrix_col.items(): 
     flag = True 
     for w1 in trans.keys(): 
      for w2, c in trans[u1].items(): 
       if u1 == str(w1) and u2 == str(w2): 
        trans_mat.append([c])  
        flag = False 
     if flag: 
      trans_mat.append([0]) 

trans_mat = np.asarray(trans_mat) 
trans_mat = np.reshape(trans_mat, (11000, 11000)) 

Вот его текущее представление. Это в основном обработка 2 штук в минуту. С такой скоростью он будет принимать более 5 дней, чтобы сформировать матрицу, trans_mat:

0 Tue Oct 6 11:31:18 2015 
1 Tue Oct 6 11:31:46 2015 
2 Tue Oct 6 11:32:19 2015 
3 Tue Oct 6 11:32:52 2015 
4 Tue Oct 6 11:33:19 2015 
5 Tue Oct 6 11:33:46 2015 

Answer 1

без контекста трудно понять логику и то, что вы пытаетесь достичь, но вы должны с учетом изменения алгоритма перебора trans первый и затем проверьте trans_mat. Что-то вроде:

for w1, t_val in trans.items(): 
    w1_is_in_matrix_col = str(w1) in matrix_col 
    for w2, c in t_val.items(): 
     if w1_is_in_matrix_col and str(w2) in matrix_col: 
      trans_mat.append([c]) 
     else: 
      trans_mat.append([0]) 

Теоретически вы можете использовать список понимание здесь и это даст вам некоторое повышение, а также (но незначительные по сравнению с текущей неэффективностью).

Answer 2

Вы не пользуетесь быстрым поиском, доступным для словарей. Поиск ключа в dict - это O (1). Чтобы это исправить, нужно просто изменить свой алгоритм, так что вы не итерацию всех ключей ищут те, что вы хотите ..

from itertools import product 
trans_mat = [ [trans[u1][u2]] if (u1 in trans) and (u2 in trans[u1]) else [0] 
       for u1 in matrix_col for u2 in matrix_col ]