Python数据结构以实现高效添加、删除和随机选择

Question

Python数据结构以实现高效添加、删除和随机选择

30

我正在寻找一个内置的Python数据结构，它可以

添加新元素，删除现有元素，并选择一个随机元素，所有这些操作都在O（n）时间内执行得更好。
我希望set能够做到这一点，但是据我所知，从Python集合中选择随机元素的唯一方法是random.choice(list(my_set))，这需要O（n）时间。
我非常希望能够使用Python内置的解决方案，因为我需要高效和易于部署。不幸的是，Python似乎没有内置的树数据类型。

- tba

1

这可能是接口设计的问题。在树/哈希表中进行随机选择并不难，但甚至C++ STL的map / unordered_map也不支持随机选择。 - richselian

2个回答

0

这是对@Amber和@user2357112答案的变体。它是作为list的子类实现的，并直接处理random.choice()。它仍然像一个set一样工作。它执行了这两种类型的一些常见操作，但我确定它并不完全或完美地模拟它们。

class ListSet(list): """ 派生自：https://dev59.com/h2Qo5IYBdhLWcg3whPki#15993515 初始化：与列表相同（基本上与集合相同）：（包括集合、列表、元组、生成器表达式和range()表达式。）集合行为： for x in S(): if x in S: 这是常数时间。 S.add(x) " " " " S.remove(x) " " " " len(s) " " " " print(S), str(S), repr(S) copy(S), list(S), set(S) 复制或转换。列表行为使用内部列表位置： S[3], S[-1] # 返回一个项。 S[10:20] # 返回一个列表，而不是ListSet。 random.choice(S) 这是常数时间。 S += [4, 5, 6] S.append(7)，与S.add(7)相同。 len(s)在常数时间内。 x = S.pop() # 从内部列表中弹出最后一个元素。 y = S.pop(3) # 从内部列表中弹出S[3]。 """ def __init__(self, *args, idx_of=None): super(ListSet, self).__init__(*args) if idx_of: self.idx_of = idx_of.copy() else: self.idx_of = {item: i for (i, item) in enumerate(self)}

def add(self, item): if item not in self.idx_of: super(ListSet, self).append(item) self.idx_of[item] = len(self) - 1 def append(self, item): """ append和+=总是添加到内部列表，但是除了末尾之外的remove和pop可以改变内部列表的顺序。 """ self.add(item) def copy(self): """ 返回ListSet的浅拷贝。 """ return ListSet(self, idx_of=self.idx_of) def list(self): return super(ListSet, self).copy() def __iadd__(self, items): """ self += items """ for item in items: self.add(item) return self

def remove(self, element): """ 从集合中删除一个元素；它必须是成员。

如果元素不是成员，则引发KeyError。 """ try: position = self.idx_of.pop(element) except: raise(KeyError(element)) last_item = super(ListSet, self).pop() if position != len(self): self[position] = last_item self.idx_of[last_item] = position def pop(self, i=-1): """ 根据内部列表位置删除。 """ item = self[i] self.remove(item) return item def __contains__(self, item): return item in self.idx_of def _str_body(self): return ", ".join(repr(item) for item in self) def __repr__(self): return "ListSet([" + self._str_body() + "])" def __str__(self): if self: return "{" + self._str_body() + "}" else: return "ListSet()"

- SteveWithamDuplicate

@user2357112 这是你编辑过的内容的一个变种。 - undefined

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

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

- Amber · Accepted Answer

Python没有一个内置的数据结构能够满足您所有三个要求。

话虽如此，自己实现一棵树是相当容易的。

另一个选择是将字典与列表组合在一起，创建一个有效地维护其项列表的集合：

import random

class ListDict(object):
    def __init__(self):
        self.item_to_position = {}
        self.items = []

    def add_item(self, item):
        if item in self.item_to_position:
            return
        self.items.append(item)
        self.item_to_position[item] = len(self.items)-1

    def remove_item(self, item):
        position = self.item_to_position.pop(item)
        last_item = self.items.pop()
        if position != len(self.items):
            self.items[position] = last_item
            self.item_to_position[last_item] = position

    def choose_random_item(self):
        return random.choice(self.items)

由于列表上的唯一操作是.pop()，.append()和索引检索和赋值，因此它们不应该花费超过常量时间（至少在大多数Python实现中）。

您可以使用额外的方法扩展上述定义以支持其他有用的操作，例如len，in和迭代：

class ListDict(object):
    ... # methods from above

    def __contains__(self, item):
        return item in self.item_to_position

    def __iter__(self):
        return iter(self.items)

    def __len__(self):
        return len(self.items)