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

https://www.tutorialspoint.com/lowest-common-ancestor-of-a-binary-tree-in-python

Насколько быстро хз

А, че то я не увидел, что у тебя количество дочерних веток не ограничено. Тогда это не пойдет. Он для бинарных вариантов.

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

Добавьте в node ссылку на предка и не нужно будет искать …

100 тысяч узлов
примерно миллиарда пар узлов

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

Посмотри binary lifting.

https://e-maxx.ru/algo/lca
https://e-maxx.ru/algo/lca_simpler
https://e-maxx.ru/algo/lca_linear
https://e-maxx.ru/algo/lca_linear_offline

Хм, если хранить список предков как односвязный список, из глубины наружу, и шарить по максимуму, то памяти должно хватить.

а если еще и поля структур повыравнивать... ах, мы не знаем что за яп.

Посмотри binary lifting.

Спасибо, уже смотрю.

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

Но по моим прикидкам потребуется несколько тысяч часов.

мы не знаем что за яп.

Пока Питон. Можно любой другой не слишком экзотический.

Возможно, выбранное дерево не подходит для хранения этих данных, раз такая разбалансировка?

100 тысяч узлов
примерно миллиарда пар узлов

Т.е. примерно почти все возможные пары?

Нет, менее десятой части. 5+5=10, а не 9.

Что-то больно много.

Пока Питон

Понял, ухожу.

тут вроде уже мелькало в советах сделать бек референс на парента. да, это правильное направление.

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

Вот тебе голубчик, для изучения тулупчик.

algolist.manual.ru
algorithm.narod.ru
compgeom.cs.uiuc.edu
ecss.nl
forum.algolist.ru
kvodo.ru
math.nist.gov
matt.might.net
neerc.ifmo.ru вики-конспекты
rain.ifmo.ru
www.algosort.com
www.chorochronos.org
www.coders-library.ru
www.coq.inria.fr
www.cs.cmu.edu
www.cs.princeton.edu
www.cs.sunysb.edu
www.cs.usfca.edu
www.e-maxx.ru
www.fourmilab.ch
www.geom.uiuc.edu
www.intuit.ru
www.iproc.ru
www.keithschwarz.com
www.link.cs.cmu.edu
www.maths.surrey.ac.uk
www.okmij.org
www.people.csail.mit.edu
www.sorting-algorithms.com
www.theory.esm.rochester.edu
www.tproger.ru
www3.cs.stonybrook.edualgorith
xlinux.nist.gov
yury.name

Посмотри binary lifting.

Заранее составить список предков для каждого узла? С этого и начал, не хватает памяти.

а тупо маркировать 2-мя битиками путь не судьба ?

бежиш по пути инкрементишь счётчик в проходном узле ..счётчик==2, переходишь к следующему из дохулиарда ветвей.

ближайший к корню узел с счётчик=2 есть искомое

O(log) при мин.требований по памяти

Какая нахрен библиотека? Такую задачку на собеседованиях дают на 10 минут. Есть решение за O(глубины) времени и O(1) памяти. Готовое решение давать не буду, потому что ты позорник.

всего пар 100000*99999/2, миллиард чуть более пятой части, но вообще да, в 5 раз меньше

На сайтах и в книгах по алгоритмам полно примеров обхода деревьев.
Не нужно здесь ни каких списков строить …

Дерево какое? Бинарное?

Там предки не все нужны, а только (2^i)-е, их количество максимум логарифм

Возможно, выбранное дерево не подходит для хранения этих данных, раз такая разбалансировка?

Дерево отражает хитрый физический смысл. Оно нужно только для установления общих предков. Можно ли перебалансировать дерево, сохранив возможность искать их?

Давай быстрое решение на твоём любимом языке.

Быстрые деревья (комментарий)

Дерево отражает хитрый физический смысл. Оно нужно только для установления общих предков. Можно ли перебалансировать дерево, сохранив возможность искать их?

Конечно можно, не сомневайтесь …
Структуру опубликуйте.
А то какие-то кошки, мышки …

бек референс на парента

Есть с самого начала.

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

По ним и так пробегает только один раз, когда ищут их.

Хотя имеет смысл все вызовы листовых узлов заменить на вызовы их предков. Кроме вызовов, когда аргуметны совпадают. Попробую.

Структуру опубликуйте.

https://stepik.org/media/attachments/lesson/541855/test3.zip

Вторая строка — массив предков для узлов, начиная со 2-го. 1-й узел предков не имеет, 0-й отсутствует. 999999 чисел. Можно строить из него дерево, можно работать с массивом. 3-я строка — веса узлов.

Узлы, для которых надо искать предков, перечислены с 5-й по 10004-ю строку и с 10006-й до конца, кроме левой колонки. Первая группа — 2-й аргумент, 2-я — 1-й. Списки генов, связанных с болезнями и симптомами.

Да, это тестовое задание. Срок сдачи истёк. Хочу попытаться решить, не заглядывая в официальный ответ.

https://e-maxx.ru/algo/lca https://e-maxx.ru/algo/lca_simpler https://e-maxx.ru/algo/lca_linear https://e-maxx.ru/algo/lca_linear_offline

Выглядит многообещающе, но на препроцессинг не хватает памяти. Хотя ещё не дочитал.

А может построить нечто вроде «дерева групп». Все узлы делятся на группы. В группе есть ограничение на максимальное количество участников. Группа - это структура со счетчиком участником, указателем на узел-родитель группы и указателем на группу предков. Пускай корневой узел создает первую группу и туда добавляются все его потомки первой линии, потом второй, потом третьей и так до тех пор, пока не будет превышен предел участников. Узлы-потомки, которые не смогли влезть в группу, создают свою, занося в структуру своей группы указатель на группу предков. И так всё продолжается по-новой.

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

Если в группе 1000 узлов. То дерево групп будет в 1000 раз меньше, чем исходное дерево. Если исходное дерево узлов сильно не сбалансировано, то порожденное дерево групп по идее должно быть более сбалансированным.

В самом дереве стоит таже задача - найти группу - общего предка. Т.е. можно повторить прием. Сделать дерево групп деревьев групп.

Идущие нахрен приветствуют программиста, порождающего мусор!

Реальные научные задачи отличаются от собеседований тем, что гигабайтов и гигагерц всегда не хватает. Когда начинает хватать — берутся за задачи, которые считались неподъёмными :)

Для O(1) не хватает памяти. Знаешь способ найти компромисс скорости и потребления памяти — тащи сюда.

Да, это тестовое задание. Срок сдачи истёк. Хочу попытаться решить, не заглядывая в официальный ответ.

Реальные научные задачи

Реальные научные задачи отличаются от собеседований тем, что гигабайтов и гигагерц всегда не хватает

Ничем они не отличаются, гигагерцы везде одинаковые.

Для O(1) не хватает памяти.

Для O(1) не может не хватать памяти. Нет, у тебя нигде не было O(1).

Знаешь способ найти компромисс скорости и потребления памяти — тащи сюда.

Чем тебя не устраивает общеизвестный алгоритм LCA?

https://en.wikipedia.org/wiki/Lowest_common_ancestor

Хочешь ускорить - сохраняй глубину в узлах, сложность будет не O(глубина), а O(расстояние до LCA).

Binary lifting уже посоветовали - там логарифм памяти и логарифм CPU.

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

На питоне не надо ничего считать. Никогда.

Заранее составить список предков для каждого узла?

Список предков для каждого узла не нужно составлять, он у тебя хранится в самом дереве.

С этого и начал, не хватает памяти.

Не всех предков, а только логарифма предков.

общий ближайший предок может быть не на одинаковом уровне, т.к. искать общего предка надо только среди тех у кого нет потомков.

тс верно?

общий ближайший предок может быть не на одинаковом уровне

В смысле? Если «может находиться на неодинаковом расстоянии от двух анализируемых потомков», то да, верно.

искать общего предка надо только среди тех у кого нет потомков.

А вот это не понял.

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

neo4j? или не то?

на препроцессинг не хватает памяти

На N*logN не хватает? У тебя её 640 КБ?

Заполнить вторую такую же структуру теми же данными попутно на каждои итерации заполнения выявляя наинизшую общую, хранить её и при обновлении данных просто обновлять. Тоесть она всегда должна быть найдена в любой момент времени. Итого O(1) сложность.

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

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

Давай денег, будет решение.

не хватает памяти на 10^5 узлов, чтоа?

Спасибо за подборку.

100 килобайт нынче роскошь, ты чё. 64кб хватит всем же было сказано, больше только на топовых пк. Придётся Амигу покупать или платы расширения впиховать, но их раскупили майне…. хотя стоп маёнеры только через Дцать лет появятся! Мляяяяяяя опять машина времени сломалась и нетуда я попал.!

Чем «найти наинизшую общую вершину для миллиарда пар узлов» отличается

Я так понял, что для каждой пары своя общая вершина. Берем первую пару узлов, находим общую вершину. Берем вторую пару узлов, находим общую вершину. И так миллиард раз.

дерево из 100 тысяч узлов. Самая длинная ветвь — 50 тысяч

Я правильно понимаю, что это характерная особенность деревьев, с которыми надо работать? Т.е. сильная несбалансированность, одна ветвь сильно доминирует над остальными.

Быстрые деревья - Медленные люди

Вангую тут вообще тупо связный список абсолютно никак не балансированный тоесть деревом не является просто выглядит как дерево =)

Ну тогда вообще все тривиально решается через ссылку на предка узла.

1. идем от первого узла вверх до корня помечая все что встретится
2. идем от второго узла вверх до корня и ищем первый помеченный узел
3. обнуляем все отметки

Ну тогда вообще все тривиально решается

Ага, и так 20 миллионов раз. Если дерево плохо сбалансировано, то «подъемов вверх» может быть не десятки, а десятки тысяч.

Есть подозрение, что алгоритм всё время будет упираться в подсистему памяти.

Но для нормальных, более-менее сбалансированных деревьев ИМХО предложенный алгоритм хороший.