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实现中)。