Какая структура данных оптимальнее для вставки, удаления и доступа к элементу?
Нужно выбрать структуру, которая лучше всего подходит под задачи: добавления, удаления и доступа к элементу. А еще нужна возможность быстро перебрать все ключи структуры без генерации мусора. Так же структура должна содержать одно поле (key), то есть поле значения (value) не нужно.
Здесь нашел информацию по структурам данных.
Похоже что SortedSet лучше всего подходит для этого, но я не уверен. Подскажите наилучшую структуру данных для поставленой задачи.
Ответы (1 шт):
Предположу, что вам лучше всего подходит HashSet<T>.
Согласно приведённой вами ссылке, доступ к элементу (то есть по сути проверка нахождения в коллекции по самому элементу) и добавление имеют (амортизированную) асимптотическую сложность O(1). Удаление, согласно официальной документации, также имеет сложность O(1).
С перечислением несколько сложнее, в документации гарантий я не нашёл, но глядя в исходник, цикл foreach по HashSet<T> внутри делает просто цикл по внутренней коллекции _entries, которая содержит по сути все элементы HashSet<T>, а также свободное место. Процент свободного места, однако, в текущей реализации может быть большим в случае, если вы добавили много элементов, а потом поудаляли их (Remove не меняет размер _entries), так что у нас выходит O(M), где M — макмсимальное количество элементов, которое когда-либо было в данном экземпляре HashSet<T>.
По сравнению с этим:
List<T>: удаление медленное, т. к. требует сдвига в среднем половины элементов коллекции; поиск элемента по значению также требует просмотра в среднем половины коллекции; добавление (в конец списка) быстрое (амортизированно), энумерация очень быстрая (сравнима с проходом по массивы)SortedSet<T>: асимптотика доступа и добавления хуже (O(log n)), чем уHashSet<T>, т. к. нужен расход на поддержание коллекции в сортированном состоянииQueue<T>иStack<T>— для ваших целей не отличается отList<T>LinkedList<T>требует также просмотра в среднем половины коллекции для доступа, а вот добавление/удаление и энумерация у него быстрые.
Всё это имеет смысл, если ваша коллекция будет иметь большое количество элементов. Для маленьких коллекций часто производительность List<T> превосходит производительность сложных коллекций (за счёт более простых, хотя и менее эффективных на больших коллекциях операций). В этом случае имеет смысл просто измерить время, за которое конкретно ваш сценарий использования выполняется на разных типах коллекций.