python - 在重复迭代期间更有效的洗牌

Question

我需要遍历列表任意次数，yield列表中的每个元素以随机顺序(每次遍历整个列表时顺序不同)。我需要在第二次生成该元素之前生成每个元素一次，在第三次生成该元素之前生成每个元素两次，等等。

目前，我的代码如下所示:

def random_yield(data):
  random.shuffle(data)
  data_index = 0
  while True:
    yield data[data_index]
    data_index += 1

    if data_index == len(data):
      random.shuffle(data)
      data_index = 0

有没有办法更有效地做到这一点，这样我就不会在每次 len(data) 之后支付 random.shuffle() 的性能损失>产量？

Answer 1

您可以在每次迭代中执行一个 Fisher-Yates 洗牌步骤，从而在每次迭代中平均分配成本。这并没有提高效率——事实上，它可能效率较低，因为库函数可能比 Python 代码更快——但它避免了长时间停顿。

这段代码与每次只抓取一个随机元素没有太大区别。唯一的区别是您从向量的一个子集中获取随机元素:

from random import randrange
def random_yield(data):
  index = 0
  limit = len(data)
  while True:
    if index + 1 >= limit:
      yield data[index]
      index = 0
    else:
      # Get a random element which we haven't yet used this cycle
      # (This is a single iteration of the F-Y shuffle algorithm)
      j = randrange(index, limit)
      rv = data[j]
      yield rv
      # Swap the element we just selected so its not in the next subrange
      data[j] = data[index]
      data[index] = rv
      index += 1