Подходящий тип коллекции для эффективного выбора случайного элемента в Scala

Question

Для проекта, над которым я работаю, мне нужно отслеживать до нескольких тысяч объектов.Выбранная коллекция должна поддерживать вставку, выбор и удаление случайных элементов.Мой алгоритм выполняет каждую из этих операций несколько раз, поэтому я хотел бы, чтобы коллекция могла выполнять все эти операции за постоянное время.

Существует ли такая коллекция?Если нет, каковы некоторые компромиссы с существующими коллекциями?Я использую Scala 2.9.1.

РЕДАКТИРОВАТЬ: Под "случайным" я подразумеваю математически / вероятностно случайный, т. Е. Я хотел бы выбрать элементы случайным образом из коллекции, используя случайный или некоторые другиедругой подходящий генератор.

Answer 1

Определить «случайный». Если вы имеете в виду индексированный, то такой коллекции нет. Вы можете осуществлять вставку / удаление в постоянное время, если вы откажетесь от требования «случайный элемент» - то есть у вас будет неконстантный поиск элемента, который будет удален или который будет точкой вставки. Или вы можете иметь постоянный поиск без постоянной вставки / удаления.

Коллекция, которая наилучшим образом соответствует этому требованию, - Vector, которая обеспечивает O(log n) для этих операций.

С другой стороны, если у вас есть элемент, который вы будете искать или удалять, просто выберите HashMap. Это не точно постоянное время, но это справедливое приближение. Просто убедитесь, что у вас есть хорошая хеш-функция.

Answer 2

В качестве отправной точки взгляните на API коллекций Scala 2.8 , особенно на Performance Characteristics.