LINUX.ORG.RU

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

 ,


6

3

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

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

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

★★★★★

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

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

anonymous
()

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

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

anonymous
()

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

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

TheAnonymous ★★★★★
()

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

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

Посмотри binary lifting.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
anonymous
()
Ответ на: комментарий от Zubok

Посмотри binary lifting.

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

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

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

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

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

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

MKuznetsov ★★★★★
()

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

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

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

TheAnonymous ★★★★★
()

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

anonymous
()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

pathfinder ★★★★
()
Последнее исправление: pathfinder (всего исправлений: 2)
Ответ на: комментарий от slovazap

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

тс верно?

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

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

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

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

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

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

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

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

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

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

anonymous
()

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

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

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

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

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

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

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

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

pathfinder ★★★★
()

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

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

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

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

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

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

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

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

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

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

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

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

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

pathfinder ★★★★
()
Последнее исправление: pathfinder (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.