Структура данных с произвольным удалением 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()

Сначала я попробовал питон set(), однако отсюда: Set.pop () не является случайным? , похоже, что set() на самом деле не удаляет элементы в произвольном порядке.Как бы я реализовал структуру данных с использованием выше?

Answer 1

Поиск и удаление случайного элемента в коллекции обычно O(k) при использовании pop, однако вы можете изменить действие так, чтобы список был перетасован при проверке длины, таким образом,остаются операции add и pop 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

Answer 2

Если вы хотите всплыть случайным образом, почему бы вам не использовать список и реализовать всплывающее окно, поменяв местами последний элемент с каким-то случайно выбранным элементом, а затем отбросив новый последний элемент?Это не сохранит порядок оставшихся элементов в структуре данных, но «случайное всплытие» и «случайное перемешивание» говорят о том, что вам все равно.