python - 具有 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() is not random? ，似乎set()实际上并没有以任意顺序删除项目。我将如何使用上述用法实现数据结构？

标签： pythonpython-3.xalgorithmdata-structures

Answer 1

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