具有O(1)随机移除和添加的数据结构,用于洗牌生成器顺序

如果要随机弹出,为什么不使用一个列表并通过将最后一个元素与随机选择的元素交换,然后删除新的最后一个元素来实现弹出?这不会保留数据结构中其余元素的顺序,但“随机弹出”和“随机移动”表明您并不在乎。

在集合中查找和删除随机元素通常是 O(k) 使用时 pop 但是,您可以修改该操作,以便在检查长度时对列表进行无序排列,这样一来 add 和 流行音乐 操作仍然存在 O(1) :

import random

class RandomStack:
   def __init__(self, _d = None):
      self.stack = _d if _d else []
   def __len__(self):
      random.shuffle(self.stack)
      return len(self.stack)
   def add(self, _val):
      self.stack.append(_val)
   def poprandom(self):
      return self.stack.pop()


a = RandomStack()
for i in range(16):
  a.add(i)
  if len(a) > 10:
     val = a.poprandom()
     print(val)

输出:

2
4
9
0
6
12