常数时间随机选择和删除

Question

常数时间随机选择和删除

3

我是一个有用的助手，可以为您翻译文本。

我试图在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数据结构可以同时实现常数时间的随机选择和删除？

- MikeRand

3

l1是一个列表吗？l1.elements()是什么？ - unutbu

执行 del l1[(1, 2)] 时，会出现 list indices must be integers, not tuple 错误。 - dusan

l1 是一个列表；也许您在描述中颠倒了 l1 和 l2？ - chepner

1

据我所知，没有内置的数据结构可以为您完成此操作。但是，您可以使用抽象基类来创建一个类似于字典的结构，并具有选择随机项的附加功能。有关更多详细信息，请参见这个类似的问题。 - senderle

2

@abarnert，您绝对可以通过l2实现恒定时间的随机选择。您只需将加权边多次插入到列表中。然后，您维护一个字典，其中键为存在的关键词，而值为指向列表中索引的列表。要移除项目，请从列表末尾弹出项目并将其放置在要删除的项目所在位置；然后更新字典。确实，由于您必须扫描索引列表以找到要更改的项，因此移除将在最大_权重_中是线性的。但它接近OP请求的内容。 - senderle

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- abarnert · Accepted Answer

我认为你在理论上试图做的事情是不可实现的。

如果您使用加权值来表示重复项，则无法获得常数时间的随机选择。您可能能做到的最好的选择是某种跳表类型结构，它允许您通过加权索引进行二进制搜索元素，这需要对数时间。

如果您不使用加权值来表示重复项，则需要一些结构来允许您存储多个副本。哈希表行不通——重复项必须是独立的对象（例如(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)

当然，你可以用三行代码实现查找和更新，但这仍然是重复次数的线性操作。

显然，如果您计划实际使用此代码，您可能需要增强一下类。您可以通过实现一些方法并让适当的 collections.abc.Foo/collections.Foo 方法来使其看起来像边缘的列表、每个边缘的多个副本的元组集或者一个计数器等。

那么，哪个更好呢？在您的示例情况下，平均重复次数是列表大小的一半，最大值是大小的 2/3。如果您的真实数据也符合这种情况，那么树结构肯定会更好，因为log N 明显比 (N/2)**2 更快。另一方面，如果重复很少，senderle 的解决方案显然更好，因为如果 W 是 1，则 W**2 仍然是 1。

当然，在一个由 3 个元素组成的样本中，常量开销和乘数会支配一切。但是假设您的真实集合不是那么小。（如果确实很小，就使用一个 list...）

如果您不知道如何描述您的真实数据，请编写两个实现，并使用各种逼近真实情况的输入来测试它们的时间。