我正在尝试用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数据结构可以让我同时进行恒定时间的随机选择和删除？
我不认为你试图做的事情在理论上是可以实现的。
如果使用加权值来表示重复项，则无法获得恒定时间的随机选择。你能做的最好的事情是某种跳过列表类型的结构，它可以让你通过加权索引（对数）对元素进行二进制搜索。
如果不是使用加权值来表示重复，那么您需要一些允许存储多个副本的结构。哈希表不能做到这一点——重复数据集必须是独立的对象（例如(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填充其余部分，可以使其看起来像边的list、每个边的多个副本的tuples的set、Counter等
那么，哪个更好呢？好吧，在您的示例案例中，平均重复计数是列表大小的一半，最大值是列表的2/3。如果你的真实数据是这样的话，树会更好，因为log N显然会破坏(N/2)**2。另一方面，如果dup很少，senderle的解决方案显然会更好，因为如果W是1，W**2仍然是1。
当然，对于一个三元素样本，常数开销和乘数将主导一切。但据推测，你真正的收藏并没有那么少。（如果是，只需使用list…）
如果你不知道如何描述你的真实数据，那么写两个实现，并用各种现实的输入来计时。