Конструкция дерева из упорядоченного списка

Question

В Java, я создаю SortedSet из списка, который всегда будет упорядочен (но только типа ArrayList). Я полагаю, что их добавление один за другим будет иметь довольно низкую производительность (в случае, например, дерева AVL), поскольку ему придется много переупорядочивать дерево.

мой вопрос, как должен создать этот набор? таким образом, чтобы построить сбалансированное дерево как можно быстрее?

конкретная реализация, которую я планировал использовать, была либо IntRBTreeSet, либо IntAVLTreeSet из http://fastutil.dsi.unimi.it/docs/it/unimi/dsi/fastutil/ints/IntSortedSet.html

после написания этой статьи, я думаю, что плохая производительность в любом случае не сильно повлияет на меня (слишком маленький объем данных), но мне все еще интересно, как это будет сделано в общем случае.

Answer 1

Набор, имеющий реализацию дерева, будет иметь средний элемент из вашего списка в верхней части. Таким образом, алгоритм будет следующим:

1. найти средний элемент списка
2. вставить его в набор
3. повторите для обоих подсписков слева и справа от среднего элемента

Answer 2

Красно-черные деревья - хороший выбор для общего случая, и они имеют очень быстрые вставки. См. статью Криса Окасаки для элегантной и быстрой реализации. Библиотека Functional Java имеет общий класс Set , который поддерживается красно-черным деревом, реализованным в соответствии с этим документом.

Answer 3

Со всем обсуждением использования набора мне приходит в голову, что, возможно, проблема может быть переформулирована. Зачем вообще использовать набор? Если вы просто хотите проверить членство, и ваш список источников отсортирован, тогда выполните бинарный поиск объекта - это будет так же быстро (и, вероятно, быстрее), чем любое n-дерево, которое вы можете себе представить, и это не так сложно код.

Итак, представьте интерфейс OrderedListSet, который просто оборачивает подчиненный объект List. Пока компаратор, используемый для упорядочивания списка, также используется для двоичного поиска, это должно быть довольно простым.

Все операции Set начнутся с вызова getIndex (Object ob), затем в списке будет выполнено соответствующее действие.

Answer 4

Встроенный TreeSet (http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeSet.html) класс использует красно-черное дерево в качестве своего базового дерева (и, как было отмечено, красно-черные деревья довольно быстро вставляются). Вот полезная информация на красно-черных деревьях (у них нет проблемы типичной реализации двоичного дерева при вставке данных, которые в основном уже упорядочены).

Если вы имеете дело с огромными наборами данных (достаточно большими, чтобы требовать резервное копирование на диске или значительный обмен файлами подкачки), то B + Tree - очень хороший вариант (см. JDBM для Java на основе версия самобалансирующегося B + Tree - он не реализует Set, но при желании может быть использован таким образом).

В зависимости от того, как ваше приложение на самом деле использует эти данные, вы можете рассмотреть библиотеку GlazedLists и сделать ваши списки «живыми». Если все, что вы делаете, это статический анализ, то это может быть излишним, но это совершенно фантастический способ работы с данными на основе списка. Обязательно стоит прочитать о.

Answer 5

Есть ли у вас проблемы с производительностью, когда вы просто вставляете элементы по мере их поступления?

Если нет, не оптимизируйте.