3

我正在尝试在 Python 中为 MultiGraph 实现边缘列表。

到目前为止我已经尝试过：

>>> 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 数据结构可以同时提供恒定时间随机选择和删除？

4

1 回答 1

2

我认为您尝试做的事情在理论上是无法实现的。

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

如果您不使用加权值来表示重复项，那么您需要一些允许您存储多个副本的结构。并且哈希表不会这样做 - dup 必须是独立的对象（例如，(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；您可能会从红黑树、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)

（当然，您可以将 replace-list-with-list-comprehension 行更改为三行 find-and-update-in-place，但这仍然与重复次数成线性关系。）

显然，如果您打算真正使用它，您可能需要稍微加强一下课程。通过实现一些方法并让适当的/填充其余部分，您可以使其看起来像 a listof edges、a setof tuples 每个边的多个副本、 aCounter等。collections.abc.Foocollections.Foo

那么，哪个更好？好吧，在您的示例中，平均重复计数是列表大小的一半，最大值是列表大小的 2/3。如果这对您的真实数据是正确的，那么这棵树会好得多，因为log N显然会被吹走(N/2)**2。另一方面，如果重复很少，senderle 的解决方案显然会更好，因为W**2如果W是 1，仍然是 1。

当然，对于 3 元素样本，恒定开销和乘数将主导一切。但大概你真正的收藏并没有那么小。（如果是，只需使用list...）

如果您不知道如何表征您的真实数据，请编写两个实现并使用各种实际输入对它们进行计时。

于 2013-02-18T22:15:00.663 回答