Python字典优化

Question

我正在尝试用Python复制一个Perl脚本，但是遇到了一些严重的性能问题。

基本上，我有一个元组的列表，并逐个处理一个列表。该列表包括TYPE（字符串），ID（字符串），OVERALL_COUNT（整数），TYPE_ID_COUNT（整数）和DROP_KEEP_FLAG（字符串）。

我的目标是将数据读入内存有效的数据结构中，并快速访问。每次处理新记录时，我想要根据修剪标准修剪结构，即如果当前TYPE_ID_COUNT大于历史TYPE_ID_COUNT-2，则不能包括任何TYPE_ID_COUNT（即，如果历史TYPE_ID_COUNT小于当前TYPE_ID_COUNT-2，则删除）。

与我的Perl代码相比，这种方法慢了好几个数量级。我已经包含了两个版本（我用dict替换了dict.keys()）。我对Python相对较新，所以我肯定有更优化的编写代码的方法。Numpy数组会更好吗？

import timeit
from collections import defaultdict
from copy import deepcopy

# FIELDS: TYPE, ID, OVERALL_COUNT, TYPE_ID_COUNT, DROP_KEEP_FLAG 

a = (['TYPE_1','000000001',1,1,'K'],['TYPE_2','000000002',2,1,'K'],['TYPE_3','000000001',3,1,'K'],
     ['TYPE_1','000000002',4,1,'K'],['TYPE_1','000000002',5,2,'K'],['TYPE_3','000000002',6,1,'K'],
     ['TYPE_1','000000002',7,3,'K'],['TYPE_1','000000002',8,4,'D'],['TYPE_1','000000002',9,5,'K'],  
     ['TYPE_1','000000001',10,2,'K'],['TYPE_2','000000001',11,1,'K'],['TYPE_2','000000001',12,2,'K'],
     ['TYPE_2','000000001',13,3,'K'],['TYPE_3','000000001',14,2,'K'],['TYPE_3','000000001',15,3,'K'],
     ['TYPE_3','000000002',16,2,'K'],['TYPE_3','000000002',17,3,'K'],['TYPE_3','000000002',18,4,'K'])

expand = a
for x in range(0, 250):
    expand = expand + a

window = 2

def version_1(data,window):
    result = defaultdict(lambda: defaultdict(list))
    output = {}

    for i_idx,i_val in enumerate(data,start=1):

        #ADD NEW ELEMENT IF IT IS A 'K'
        if i_val[4] == 'K':
            result[i_val[0]][i_val[1]].append(i_val[2])

        # TRIM OLD ELEMENTS AND COMPUTE LENGTHS
        for j_idx, j_key in enumerate(result.keys(),start=1):
            j_val = result.get(j_key)
            j_val_cp = deepcopy(j_val)

            output[j_key] = 0 

            for k_idx, k_key in enumerate(j_val_cp.keys(),start=1):
                k_val = j_val.get(k_key)

                for item in (x for x in k_val if x < i_val[2] - window):
                    k_val.remove(item)
                    if not k_val:
                        del j_val[k_key]

                    if k_key == i_val[1]:

                        output[j_key] = len(k_val)
                    #print('Output ' + str(i_idx) + ': ID: ' + i_val[1] + ' , values: ' + str(output.items()))
    return output    

def version_2(data,window):
    result = defaultdict(lambda: defaultdict(list))
    output = {}

    for i_idx,i_val in enumerate(data,start=1):

        #ADD NEW ELEMENT IF IT IS A 'K'
        if i_val[4] == 'K':
            result[i_val[0]][i_val[1]].append(i_val[2])

        # TRIM OLD ELEMENTS AND COMPUTE LENGTHS
        for j_idx, j_key in enumerate(result,start=1):
            j_val = result.get(j_key)
            j_val_cp = deepcopy(j_val)

            output[j_key] = 0 

            for k_idx, k_key in enumerate(j_val_cp,start=1):
                k_val = j_val.get(k_key)

                for item in (x for x in k_val if x < i_val[2] - window):
                    k_val.remove(item)
                    if not k_val:
                        del j_val[k_key]

                    if k_key == i_val[1]:

                        output[j_key] = len(k_val)
                    #print('Output ' + str(i_idx) + ': ID: ' + i_val[1] + ' , values: ' + str(output.items()))
    return output

# timeit.timeit(version_1(2))
start_time = timeit.default_timer()
version_1(expand,2)
print(timeit.default_timer() - start_time)

start_time = timeit.default_timer()
version_2(expand,2)
print(timeit.default_timer() - start_time) 

非常感谢您的帮助！

- Brad

---

不要遍历字典的键，而是直接遍历项本身，这样肯定比先遍历键再查找对应项更有益。使用 itervalues() 来仅遍历值，或者使用 iteritems() 来同时遍历键和值。 - Tom

我不理解你的标准......你能详细说明一下吗？你是说你想保留最后两个类型_ID_计数还是删除所有小于当前值-2的计数？这与返回的最终值有什么关系？你不断将输出中的数据丢弃output[j_key]=0，所以我无法确定应该放置什么。为什么每个值都要重新处理？难道你不只是在最后构建列表并筛选它们吗？ - tdelaney

你的version2代码返回{'TYPE_1': 0, 'TYPE_2': 0, 'TYPE_3': 0}，但我无法想出任何符合你的标准的解释。你确定它是正确的吗？ - tdelaney

你有一个嵌套字典 result[TYPE][ID]，但是构建了一个扁平的字典 output[TYPE]。这行代码 output[j_key] = len(k_val) 会不断地覆盖已经记录的 ID，以便于处理最后一个。那么为什么还要处理其他的呢？ - tdelaney

这个 expand = a for x in range(0, 250): expand = expand + a 只是为了创建更多的样本数据进行测试，以便我可以看到性能上的更大差异。 - Brad

Answer 1

我很难理解你的问题，所以我不知道你想要什么输出。在Python中使用大量嵌套循环是一个坏主意。你尝试过使用查找表方法来获取你想要过滤的项吗？例如：

# a is your 'historical' data
# Now create a look-up table to access elements of interest:
types = defaultdict(list)

for i, item in enumerate(a):
    t = item[0]
    types[t].append(i)

# You can now use your look-up table to grab items of interest e.g:
new_record = ['TYPE_3','000000002',100,2,'K']
type_idxs = types[new_record[0]]

old_types_id_counts = [a[i][2] for i in type_idxs]

# Collect the indexes of the items you want to remove:
f = [type_idxs[i] for i in range(len(type_idxs)) if old_types_id_counts[i] < current_id_count - 2]

# Once you have your indexes of items to remove, you just need to remove those items and update your table

- kezzos