列表效率搜索方法(嵌套lis)

Question

我有一个嵌套列表和514000列表。

我必须找到复制的名单并存储他们的位置。

我写了一段代码，但效率很差

你有高效率的解决方案吗？我的嵌套列表：

[["src_ip","src_port","dst_ip","dst_port"],["src_ip","src_port","dst_ip","dst_port"],
and so on
] 

Answer 1

一个更快的解决方案是使用set来跟踪到目前为止已经看到的项目，并将重复项的位置添加到列表中。因为列表是不可理解的，所以可以将它们转换为元组。以下是生成的代码：

seen = set()  # Unique items
result = []   # List of duplicate positions
for pos, item in enumerate(lst):
    tmp = tuple(item)
    if tmp in seen:
        result.append(pos)
    else:
        seen.add(tmp)

如果要跟踪与找到的副本关联的唯一项在哪里，可以只将seen更改为dict，并将seen.add(tmp)更改为seen[tmp] = pos。得到的解在线性时间内运行。O(n)，其中n是输入lst的大小。这段代码在我的机器上需要大约250毫秒，其中包含514000个子列表，包含4个短随机字符串。