哪种可变对象的集合能够在Python中快速移除元素？

Question

假设我已经对程序进行了剖析，大部分运行时间花费在“list对象的'remove'方法”上。该程序操作一组集合，这些集合不需要排序。使用Python实现这些集合的最简单方法是什么（最好使用标准Python集合），以便在collection是外部集合且item是内部集合时，删除collection.remove(item)既廉价又方便，当collection是内部集合且item只是一个不可变对象时也是如此。 在这里使用set的问题在于set不能包含可变集合，因此内部集合必须是frozenset，但是删除项就不再那么便宜了。 到目前为止我找到的最佳解决方案是由某人在这里提出的答案，但很快被删除了。他们建议使用字典。这将起作用，但您必须为每个项生成任意id，因此有点尴尬。另一种选择是使用链表，但是这也很尴尬，因为链表不是标准库的一部分。

- 108

---

当你执行 collection.remove(item) 时，这个 item 可能会出现在多个子集合中或者在单个集合中出现多次吗？无论如何，我怀疑操作的瓶颈将是搜索 item 的位置，以确定它属于哪些子集合以及与之关联的索引或键，以便继续进行删除。 - martineau

你能否更具体地说明你需要这个是用来做什么的？ - adw

我在社交遗传算法模拟中遇到了这个问题，其中有一组集合和每个组都是一组个体。个体经常从组中添加和移除，组经常从集合中添加和移除。 - 108

Answer 1

如果您可以接受把“相等”定义为“同一”，那么您可以创建一个可哈希的列表子类型，并将其作为集合成员进行快速访问/删除：

class hlist(list):
"Hashable list"
    def __hash__(self):
        return id(self)
    def __eq__(self, other):
        return self is other
    def __ne__{self, other}:
        return self is not other

in1 = hlist([1,2,3])
in2 = hlist([4,5,6])
outer = set([in1, in2])

- Don O'Donnell

Answer 2

他们建议使用字典。这个方法可行，但你需要为每个项生成任意的ID，所以有点麻烦。 你通过实例来删除它们吗？使用字典方法，你可以始终使用id()作为它们的“任意”ID？ 一个字典用于组，以它们的id()作为键，内部字典用于个人的id()。另一个全局字典用于个人，以他们的id()作为键。 不清楚一个人是否可以在多个组中...如果是这样，你需要验证个人是否在任何组中才能删除它。

- Danosaure

Answer 3

在这种情况下，字典是你想要的集合，因为它具有O(1)的查找和删除。虽然你需要为每个对象生成一个键来添加/删除，但它比扫描列表的O(n)方法要快得多。在这种情况下，为你的对象生成一个键是正确的做法。如果你有一个主键（它们来自数据库吗？），那么将抵消哈希函数以进行属性查找，并且你将实现接近完美的性能。

你似乎认为在这种情况下使用字典作为数据结构是不好的 - 实际上并不是这样。字典的目的是快速查找集合中的项。这正是你所需要的，使用它吧。

- Josh Smeaton

---

OP还可以查看http://us.pycon.org/2010/conference/schedule/event/12/，了解字典的内部结构以及为什么这是一个好选择。 - Rohan Monga

Answer 4

如果你花费了很多时间从列表中删除元素，也许你应该考虑使用过滤器来代替？换句话说，创建一个大的初始列表，然后使用后续生成器来消耗列表中的元素。

- Katriel

Answer 5

这也许不完全是你所要求的，但是 collections.deque 可能满足你的一些需求：

deque 支持线程安全、内存高效地从 deque 的任意一侧进行附加和弹出操作，并且在任何方向上具有大约相同的 O(1) 性能。

- Daniel Roseman

Answer 6

为什么不创建一个主要的列表，然后再创建另一个包含所需跟踪的集合在列表中索引的集合呢？虽然这可能需要一些额外的工作，但你应该可以将其抽象成一个类。

- rossipedia

---

这并没有帮助。你仍然需要在列表中搜索每个要删除的项。 - 108