Структура данных для выбора случайных элементов?

Question

Кто-нибудь знает структуру данных, которая эффективно поддерживает две операции?

1. Вставить значение в структуру данных.
2. Отменить и вернуть запись из структуры данных с равномерно случайной вероятностью.

Это похоже на канонический «мешок из мрамора», который всегда появляется во вводных классах вероятности. Вы можете помещать произвольные мраморы в сумку и затем эффективно удалять мрамор в случайном порядке.

Лучшее решение, которое у меня есть, - использовать самобалансирующееся двоичное дерево поиска (AVL, AA, red/black и т. Д.) Для хранения элементов. Это дает время вставки O (lg n). Чтобы удалить случайный элемент, выберите случайный индекс i, затем найдите и удалите i-й элемент из дерева. Если вы соответствующим образом внедрили структуру, это можно сделать и в O (lg n).

Это время исполнения, конечно, неплохо, но мне любопытно, возможно ли сделать лучше - возможно, O (1) для вставки и O (lg n) для детекций? Или, возможно, что-то, что работает в ожидается O (1) вставить и удалить с помощью хеш-функций? Или, возможно, более сильная амортизация?

Есть ли у кого-нибудь идеи, как сделать это асимптотически быстрее?

Answer 1

Да. Используйте вектор.

Чтобы вставить, просто поместите в конец и увеличьте размер. Чтобы удалить, выберите элемент произвольно, поменяйте его содержимое конечным значением, затем выскочите конечное значение (т. Е. Верните конечное значение и уменьшите размер вектора).

Обе операции амортизируются O (1).