Кто-нибудь знает о структуре данных, которая эффективно поддерживает две операции?
- Вставьте значение в структуру данных.
- Отменить и вернуть запись из структуры данных с равномерной случайной вероятностью.
Это похоже на канонический "мешок из мрамора", который всегда появляется во вводных классах вероятности. Вы можете помещать произвольные мраморы в сумку и затем эффективно удалять мрамор в случайном порядке.
Лучшее решение, которое у меня есть, - это использовать самобалансирующееся двоичное дерево поиска (AVL, AA, red/black и т.д.) для хранения элементов. Это дает время вставки O (lg n). Чтобы удалить случайный элемент, выберите случайный индекс i, затем найдите и удалите i-й элемент из дерева. Если вы соответствующим образом внедрили структуру, это может быть сделано для выполнения в O (lg n) времени.
Эта среда исполнения, конечно, не плохая, но мне любопытно, возможно ли сделать лучше - возможно, O (1) для вставки и O (lg n) для детекций? Или, возможно, что-то, что работает в expected O (1), вставляет и удаляет с помощью хеш-функций? Или, возможно, более сильная амортизация?
Есть ли у кого-нибудь идеи о том, как сделать это асимптотически быстрее?
