python - 用于高效添加、删除和随机选择的 Python 数据结构

Question

我正在寻找一个内置的 Python 数据结构，它可以在比 O(n) 时间更好的时间内add创建一个新元素、一个现有元素并选择一个随机元素。remove

我希望set可以做到这一点，但是 AFAIK，从 Python 集中选择随机元素的唯一方法是random.choice(list(my_set))，这需要 O(n) 时间。

我非常喜欢内置于 Python 中的解决方案，因为我需要效率和易于部署。不幸的是，Python 似乎没有内置的树数据类型。

Answer 1

Python 没有满足您所有 3 个要求的内置数据结构。

也就是说，自己实现一棵树相当简单。

---

另一种选择是将字典与列表相结合，以创建有效的集合，该集合还维护其项目列表：

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)