Python数据结构,用于高效添加,删除和random.choice

Question

我正在寻找一个内置的Python数据结构,它可以add包含一个新元素,remove一个现有元素,并选择一个随机元素,所有这些都比O(n)时间好.

我希望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实现中).