跟踪已处理的列表

Question

我有一个处理列表的工作流程，并跟踪我在字典中看到的列表-因为当我看到一个已经看到的列表时，我可以传递它。需要注意的是，具有相同元素的不同顺序的两个列表被认为是重复的。举一个整数列表的简单例子:[3, 1, 5, 6]和[5, 3, 6, 1]是等价的。

我是怎么做的，把tuple(sorted(L))放在我的字典里。因此，对于上面的示例，seen看起来像:

seen = {..., (1, 3, 5, 6): 1, ...}

对于我可能需要处理的每个列表，这具有恒定时间查找的优点。然而问题是，为了检查一个给定的列表是否在seen中，我必须在它上面做tuple(sorted(L))。事实证明，对于大量数据，这变得令人望而却步，以至于占用整个过程总时间的50%以上。

我想以某种方式使用collections.Counter-因为Counter[3, 1, 5, 6]和Counter[5, 3, 6, 1]将计算相等。但是Counter对象不能用作字典键。如何在不进行上述排序操作的情况下保持字典查找?提前谢谢。

编辑在查看使用frozenset的建议时，我意识到我遗漏了一件重要的事情，那就是元素可以复制。因此，虽然上面的两个列表比较相等，但[3, 1, 5, 6]和[3, 3, 1, 5, 6, 6]需要被视为不同的。由于frozenset操作将删除重复项，因此此处不提供此选项。

Answer 1

正如其他人指出的那样，frozenset是你最好的选择:

seen = set()
list_1, list_2, list_3 = [3, 1, 5, 6], [5, 3, 6, 1], [1, 2, 3]
print(frozenset(list_1) in seen)
seen.add(frozenset(list_1))
print(frozenset(list_1) in seen)
print(frozenset(list_2) in seen)
print(frozenset(list_3) in seen)

frozenset接受一个可迭代对象作为参数，因此实例化该集合需要O(n)。根据前面的响应，查找的平均时间为O(1)，与标准set相同。无论哪种方法，你都可以节省非常昂贵的排序操作O(n log n)

Answer 2

如果您确实有很多重复项，那么可能使用Counter项中的frozenset?

>>> from collections import Counter
>>> frozenset(Counter([3, 3, 1, 5, 6, 6]).items())
frozenset({(1, 1), (3, 2), (6, 2), (5, 1)})

或Counter项的排序元组:

>>> tuple(sorted(Counter([3, 3, 1, 5, 6, 6]).items()))
((1, 1), (3, 2), (5, 1), (6, 2))