具有O(1)随机删除的数据结构并添加用于改组生成器顺序

Question

我需要一个数据结构,允许您添加元素并O(1)及时随机删除它们.

这样做的原因是我需要从生成器中移植数据,但由于大小的原因,我无法同时将所有内容加载到内存中.

这是一个使用示例,它自动混合生成器表达式生成的结果的顺序,而不将所有内容加载到内存中:

def generator_shuffler(generator)
    a = magical_data_structure_described_above
    for i in generator:
        a.add(i)
        if len(a) > 10: yield a.poprandom()

最初我尝试了一个python set(),但是从这里开始:Set.pop()不是随机的？,似乎set()实际上并没有以任意顺序删除项目.如何使用上述用法实现数据结构？

Answer 1

如果你想随机弹出,为什么不只是使用一个列表并通过交换一个随机选择的元素然后删除新的最后一个元素来实现pop？这不会保留数据结构中剩余元素的顺序,但"随机弹出"和"随机播放"表明您并不真正关心.