Структуры данных: Который я должен использовать для этих условий?
Это не должно быть трудным вопросом, но я буду точно так же, как кто-то для возврата его прочь того, прежде чем я продолжу. Я просто должен решить что структуру данных использовать на основе этих ожидаемых операций:
- Должен будет часто выполнять итерации через в отсортированном порядке (запускающийся в голове).
- Должен будет удалить/восстановить произвольные элементы из the/a отсортированное представление.
- Позже я буду часто обращаться данные и работать с несколькими отсортированными представлениями.
- Также позже я буду часто менять положение элементов в рамках их отсортированных представлений.
Это находится в Java, между прочим.
Мое лучшее предположение - то, что я буду или прокручивать некоторый пользовательский Связанный Набор Хеша (для расположения ссылок в отсортированном порядке) или возможно просто использовать Древовидный Набор. Но я еще все еще не абсолютно уверен. Рекомендации?
Править: Я предполагаю из-за произвольного, удаляют/восстанавливают, я должен, вероятно, придерживаться Древовидного Набора, правильно?
На самом деле, не обязательно. Хм...
2 ответа
Теоретически я бы сказал, что правильная структура данных - это многостороннее дерево, предпочтительно что-то вроде дерева B +. Традиционно это дисковая структура данных, но современная основная память имеет много схожих характеристик из-за уровней кеш-памяти и виртуальной памяти.
Итерация дерева B + по порядку очень эффективна, потому что (1) вы перебираете только связанный список листовых узлов - узлы ветвления не нужны, и (2) вы получаете очень хорошую локальность.
Поиск, удаление и вставка произвольных элементов - это log (n), как и в любом сбалансированном дереве, но с разными постоянными коэффициентами.
Использование дерева в основном сводится к выбору алгоритма, который дает хорошую производительность при работе со связанным списком блоков (конечные узлы), сводя к минимуму необходимость использования конечных узлов - варианты быстрой сортировки или сортировки слиянием кажутся вероятными кандидатами. . После того, как элементы отсортированы в узлах ветвления, просто распространите сводную информацию обратно через конечные узлы.
НО - прагматично, это то, что вы бы сделали, только если очень уверены, что вам это нужно. Скорее всего, вам лучше использовать какой-нибудь стандартный контейнер. Оптимизация алгоритмов / структуры данных - лучший вид оптимизации, но все же может быть преждевременным.
Стандартный LinkedHashSet или LinkedMultiset из коллекций Google, если вы хотите, чтобы в вашей структуре данных хранились не уникальные значения.