LINUX.ORG.RU
Форум — Development  

Быстрые деревья

 ,


6

3

Имеется структура данных: дерево из 100 тысяч узлов. Самая длинная ветвь — 50 тысяч. Число дочерних узлов не ограничено. Требуется быстро найти наинизшую общую вершину для примерно миллиарда пар узлов.

Для менее асимметричного дерева из 10 тысяч узлов и 20 миллионов пар я тупо построил список списков предков и сравнил для каждой пары. Но для большого дерева не хватит памяти.

Вопрос: есть ли готовая библиотека, способная быстро искать общую вершину?

★★★★★

Последнее исправление: question4 (всего исправлений: 1)
← В скрипте несколько вызовов datetime.now() выдает одинаковое время
Аналог PascalABC.net под linux →
  1 2 →
Ответ на: комментарий от AntonI

Вообще, если нужен универсальный алгоритм, не учитывающий какую-то специфику конкретных деревьев, то ИМХО лучшее предложил анонимус в самом начале в виде ссылок.

pathfinder ★★★★
()
Ответ на: комментарий от AntonI

А причем тут пары узлов? Чем «найти наинизшую общую вершину для миллиарда пар узлов» отличается от «найти наинизшую общую вершину для двух миллиардов (или сколько их там будет) узлов»?

Для каждой пары — своя LCA со своим весом, который нужен в задаче принятия решения по группе из 2-100 пар.

question4 ★★★★★
() автор топика
Ответ на: комментарий от pathfinder

для каждой пары своя общая вершина.

Именно.

question4 ★★★★★
() автор топика
Ответ на: комментарий от pathfinder

ИМХО лучшее предложил анонимус в самом начале в виде ссылок.

Возможно. При первом прочтении я пропустил важную деталь, что в список добавляются не все предки. Попробовать пока не было времени.

question4 ★★★★★
() автор топика
Ответ на: комментарий от question4

А можно предполагать, что почти всегда будет одна очень длинная ветка, а все остальные ветки будут небольшими «отростками» в некоторых местах этой длинной ветки? Можно ли предполагать что все деревья специфичны и для таких деревьев специальный алгоритм будет эффективнее универсального?

Меня смущает, что всего 100 тыс. узлов, и при этом самая длинная ветка 50 тыс. узлов.

pathfinder ★★★★
()
Последнее исправление: pathfinder (всего исправлений: 1)

В зависимости от вида деревьев задача либо очень простая, либо не очень простая. Какое дерево то хоть? Упорядоченное как-то или нет?

peregrine ★★★★★
()
Ответ на: комментарий от question4

Тогда картинку нарисуй чтоль. Или как я выше сказал. Возми пустое дерево, добавь пару вычисли нужное, добавь ещё пару снова вычисли и так до победного пока тупо все данные не перегонишь. В итоге у тебя будет общая твоя точка которую в дальнейшем при добавлении ты просто будешь корректировать, а не вычислять всё заново каждый раз. Итоговая новая стурктура тупо заменит текущую и всё. Короче тупо перезапись, но уже с балансом вот и всюо.

anonymous
()
Ответ на: комментарий от pathfinder

А можно предполагать, что почти всегда будет одна очень длинная ветка, а все остальные ветки будут небольшими «отростками» в некоторых местах этой длинной ветки?

Нет. В других заданиях есть и более симметричные.

question4 ★★★★★
() автор топика

Если память позволяет, то попробуй дерево ван Эмде Боаса, главная особенность этой структуры — выполнение всех операций за время O(log(log(U))) независимо от количества хранящихся в ней элементов.

https://habr.com/ru/post/125499/

wall_jvm
()

А в каком виде вообще дерево хранится? Это ведь не в оперативку тебе такое влезло? Это бд? Какая структура записей?

Aswed ★★★★★
()
Ответ на: комментарий от Aswed

В любом желаемом. Выше ссылка на текстовый файл с пояснениями. Линейный массив родителей, линейный массив весов, короткие линейные массивы того, что следует искать.

question4 ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
  1 2 →
← В скрипте несколько вызовов datetime.now() выдает одинаковое время
Development
Аналог PascalABC.net под linux →