问恒定时间随机选择与删除

EN

我不认为你想要做的在理论上是可以实现的。

如果您使用加权值来表示重复值，则无法获得固定时间的随机选择。你能做的最好的就是某种跳过列表类型的结构，它允许你通过加权索引搜索元素，这是对数的。

如果您没有使用加权值来表示副本，那么您需要某种允许存储多个副本的结构。哈希表是不会做到的-- dups必须是独立的对象(例如，(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+Tree；您可以从一棵红黑树、一只踏板或其他东西中获得更好的性能。您可以在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 /collections.Foo填充其余的方法，使其看起来像边缘的set，每个边的多个副本的tuple，Counter等等。

那么哪一个更好？在您的示例中，平均dup计数是列表大小的一半，最大值为2/3 3rds。如果您的真实数据是这样的话，那么树会好得多，因为log N显然会吹走(N/2)**2。另一方面，如果dups是罕见的，senderle的解决方案显然会更好，因为如果W**2是1，则W仍然是1。

当然，对于三元素样本来说，恒定的开销和乘数将主宰一切。但想必你真正的收藏并没有那么小。(如果是，只需使用list.)

如果您不知道如何描述真实的数据，那么编写实现，并使用各种实际的输入对它们进行计时。