Python数据结构，用于高效的添加，删除和random.choice [英] Python data structure for efficient add, remove, and random.choice

问题描述

我正在寻找一个内置的Python数据结构，可以添加一个新元素 remove 现有元素，并选择一个随机元素，全部超过O（n）时间。

I'm looking for a built-in Python data structure that can add a new element, remove an existing element, and choose a random element, all in better than O(n) time.

我希望设置可以这样做，但是AFAIK是从Python集合中选择随机元素的唯一方法是 random.choice（list（my_set）），它需要O（n ）时间。

I was hoping that set could do this, but AFAIK, the only way to choose a random element from a Python set is random.choice(list(my_set)), which takes O(n) time.

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

I would greatly prefer a solution that's built into Python, since I require efficiency and easy deployment. Unfortunately, Python does not seem to have built-in tree data types.

推荐答案

Python没有内置的

Python does not have a built-in data structure which meets all 3 of your requirements.

这就是说，自己实现一个树是相当微不足道的。

That said, it's fairly trivial to implement a tree yourself.

另一个选择是将字典与列表组合，以创建一个有效的集合，它还维护其项目列表：

Another option would be to combine a dictionary with a list to create what is effectively a set that also maintains a list of its items:

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实现，至少）。

Since the only operations done on the list are .pop() and .append(), they shouldn't take more than constant time (in most Python implementations, at least).

这篇关于Python数据结构，用于高效的添加，删除和random.choice的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！