python - 管理大点列表，最好的方法是什么？

Question

我的代码遇到了性能瓶颈，并决定重写它，并且需要一些有关如何解决此问题的建议。我有一个巨大的光流数据列表，其中包含带有框架、X 和 Y 坐标的列表。像这样:

[[[frame,x,y],[frame,x,y]],[[frame,x,y],[frame,x,y]]...]

我在这里上传了一个示例:http://pastebin.com/ANUr8bwc

我需要找到一种方法来管理这些数据，以便我可以快速查找并查看哪些列表包含某些帧。

到目前为止，我已经循环遍历了所有数据，以查看哪些列表包含第 34 帧和第 35 帧，然后将它们索引到新列表中以供引用。

thisFrame = 34
nextFrame = thisFrame + 1
if any(e[0] == thisFrame for e in item) and any(e[0] == nextFrame for e in item): #Check if the item contains this frame and next
    DoStuff()

对 10.000 多个点的列表执行数千次，很快就会变成瓶颈。所以我的想法是为每个帧创建一个字典，这样就可以轻松找到特定帧上可用的项目:

{frame, [list1,list2,list3]}

但我想这次我最好问一下。是否有一个好的 goto 方法来存储并能够在大数据集中进行查找，以避免每次需要时都循环遍历所有数据集？

Answer 1

Dictionaries是 Python 最优化的数据结构之一。将数据转换为字典需要一些时间，但之后，查找(例如 item 中的 thisFrame)会在 O(1) 中完成。时间，比列表快得多。

您最好的选择是使用如下代码转换为字典:

注意看起来您的列表嵌套了两次，如果不是这种情况，您将必须稍微修改迭代。

item_dict = {}
for big_lst in item:
    for lst in big_lst:
        try:
            item_dict[lst[0]] += [lst[1:],] # Append to existing value
        except KeyError:
            item_dict[lst[0]] = [lst[1:],] # Initialize value

编辑 02/05:尝试/排除更快

item_dict 将如下所示，合并重复的帧，以便单帧查找将返回 [x, y] 对的列表。

item_dict = {
    1: [list1, list2, list3]
    2: [list1, list2]
    3: [list1]
    4: [list1, list2, list3]
}

从此以后的查找将会非常快:

thisFrame = 34
nextFrame = thisFrame + 1
if thisFrame in item_dict and nextFrame in item_dict:
    foo = item_dict[thisFrame] # e.g. [list1, list2]
    bar = item_dict[nextFrame] # e.g. [list1, list2, list3]
    DoStuff()

如果您需要跟踪各个 [x, y] 对所属的父列表，您可以为每个列表添加一个附加元素，该元素将父列表的索引存储在 item 中:

item_dict = {}
for list_index, big_lst in enumerate(item):
    for lst in big_lst:
        if lst[0] in item_dict:
            item_dict[lst[0]] += [lst[1:]+[list_index],] # Append
        else:
            item_dict[lst[0]] = [lst[1:]+[list_index],] # Initialize

然后，像这样的查找

parent_list = item_dict[thisFrame][2] # [x, y, list_index]

将返回可以访问的父列表:

item[parent_list]