Структуры данных: что мне следует использовать в этих условиях?

Это не должно быть сложным вопросом, но я просто хотел бы, чтобы кто-нибудь ответил на него, прежде чем я продолжу. Мне просто нужно решить, какую структуру данных использовать на основе этих ожидаемых действий:

  1. Потребуется часто выполнять итерацию в отсортированном порядке (начиная с головы).
  2. Потребуется удалить / восстановить произвольные элементы из отсортированного представления.
  3. Позже я буду часто прибегать к данным и работать с несколькими отсортированными представлениями.
  4. Также позже я буду часто менять положение элементов в их отсортированных представлениях.

Кстати, это на Java.

Я предполагаю, что я либо буду использовать какой-нибудь настраиваемый набор связанных хешей (чтобы упорядочить ссылки в отсортированном порядке), либо, возможно, просто буду использовать набор деревьев. Но я все еще не совсем уверен. Рекомендации?

Изменить: я полагаю, из-за произвольного удаления / восстановления мне, вероятно, следует придерживаться набора деревьев, верно?

На самом деле, не обязательно. Хм...


java performance sorting data-structures multiway-tree
person Daddy Warbox    schedule 21.02.2010    source источник
comment
Я бы предпочел оставить основной тег в начале заголовка, пожалуйста.   -  person Daddy Warbox    schedule 21.02.2010

Ответы (2)


arrow_upward
3
arrow_downward

Теоретически я бы сказал, что правильная структура данных - это многостороннее дерево, предпочтительно что-то вроде дерева B +. Традиционно это дисковая структура данных, но современная основная память имеет много схожих характеристик из-за уровней кеш-памяти и виртуальной памяти.

Итерация по порядку дерева B + очень эффективна, потому что (1) вы перебираете только связанный список конечных узлов - узлы ветвления не нужны, и (2) вы получаете очень хорошую локальность.

Поиск, удаление и вставка произвольных элементов - это log (n), как и в любом сбалансированном дереве, но с разными постоянными коэффициентами.

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

НО - прагматично, вы бы сделали это только в том случае, если очень уверены, что вам это нужно. Скорее всего, вам лучше использовать какой-нибудь стандартный контейнер. Оптимизация алгоритмов / структуры данных - лучший вид оптимизации, но все же может быть преждевременным.

person Steve314    schedule 21.02.2010

arrow_upward
3
arrow_downward

Стандартный LinkedHashSet или LinkedMultiset из коллекций Google, если вы хотите, чтобы в вашей структуре данных хранились не уникальные значения.

person Roman    schedule 21.02.2010