常量时间随机选择和删除

Question

我正在尝试在Python中为一个多重图实现边列表。

我到目前为止尝试过的：

>>> l1 = Counter({(1, 2): 2, (1, 3): 1})
>>> l2 = [(1, 2), (1, 2), (1, 3)]

l1可以在常量时间内删除两个顶点之间的所有边（比如说，del l1[(1, 2)]），但是在随机选择这些边时需要线性时间（例如，random.choice(list(l1.elements()))）。需要注意的是，你必须在elements上进行选择，而不是直接在l1上。

l2可以在常量时间内进行随机选择（random.choice(l2)），但删除所有等于给定边的元素时需要线性时间（比如说，[i for i in l2 if i != (1, 2)]）。

问题是：有没有一种Python的数据结构，可以让我同时实现常量时间的随机选择和删除？

Answer 1

我觉得你想做的事情在理论上是不可行的。

如果你用加权值来表示重复项，那就无法实现常时间的随机选择。你能做到的最好方法是某种跳表结构，这样可以通过加权索引进行二分查找，这样的时间复杂度是对数级别的。

如果你不使用加权值来表示重复项，那么你需要一种结构来存储多个副本。而哈希表是无法做到的——重复项必须是独立的对象（例如，(edge, autoincrement)），这意味着无法在常时间内删除所有符合某个条件的项。

如果你能接受对数时间的复杂度，显而易见的选择是树结构。例如，使用blist：

>>> l3 = blist.sortedlist(l2)

要随机选择一个：

>>> edge = random.choice(l3)

文档似乎没有保证这不会做一些O(n)的操作。但幸运的是，3.3和2.7的源代码显示它会正确执行。如果你不相信，可以直接写l3[random.randrange(len(l3))]。

要删除所有边的副本，可以这样做：

>>> del l3[l3.bisect_left(edge):l3.bisect_right(edge)]

或者：

>>> try:
...     while True:
...         l3.remove(edge)
... except ValueError:
...     pass

文档详细解释了每个操作的性能保证。特别是，len是常数时间，而索引、切片、按索引或切片删除、二分查找和按值删除都是对数时间，所以这两种操作的时间复杂度都是对数级别的。

值得注意的是，blist是一种B+树；你可能会从红黑树、treap或其他结构中获得更好的性能。大多数数据结构的良好实现可以在PyPI上找到。

---

正如senderle所指出的，如果边的最大副本数量远小于集合的大小，你可以创建一种数据结构，使其在最大副本数量上以平方时间完成。将他的建议转化为代码：

class MGraph(object):
    def __init__(self):
        self.edgelist = []
        self.edgedict = defaultdict(list)
    def add(self, edge):
        self.edgedict[edge].append(len(self.edgelist))
        self.edgelist.append(edge)
    def remove(self, edge):
        for index in self.edgedict.get(edge, []):
            maxedge = len(self.edgelist) - 1
            lastedge = self.edgelist[maxedge]
            self.edgelist[index], self.edgelist[maxedge] = self.edgelist[maxedge], self.edgelist[index]
            self.edgedict[lastedge] = [i if i != maxedge else index for i in self.edgedict[lastedge]]
            del self.edgelist[-1]
        del self.edgedict[edge]
    def choice(self):
        return random.choice(self.edgelist)

当然，你可以将替换列表的那一行改为三行的就地查找和更新，但这仍然是线性的，取决于重复项的数量。

显然，如果你打算真正使用这个，你可能想稍微增强一下这个类。你可以通过实现一些方法，让它看起来像是边的list、多个副本的tuple集合、Counter等，来填补其余部分。

---

那么，哪个更好呢？在你的示例中，平均重复数量是列表大小的一半，最大是三分之二。如果你的真实数据也是这样，树结构会好得多，因为log N显然会远远超过(N/2)**2。另一方面，如果重复项很少，senderle的解决方案显然会更好，因为如果W是1，W**2仍然是1。

当然，对于一个包含3个元素的示例，常数开销和乘数会主导一切。但可以假设你的真实集合不会那么小。（如果真的很小，就直接用list吧……）

如果你不知道如何描述你的真实数据，可以写出这两种实现，并用各种现实输入来测试它们的时间。