jonasas: Мне кажется, терминология расползлась. Что значит, не видим больше двух ребер? Мы видим окрестность для каждой вершины. Там может быть сколько угодно ребер.
И как ты (ничего?) планируешь определить, прекратили ли сокращаться цепочки?
Я подумал. Наверное, самое простое, это добавить в возвращаемое значение расстояние до предка. Понятно, что за O(log n) итераций мы либо упремся в корень, либо расстояние превысит n, и это будет намек. =)
В асимптотике есть некоторая проблема даже с вашим алгоритмом. По задаче у каждого элемента не более одного родителя. Но как я понимаю, у каждого элемента может быть сколько угодно детей. Я пока не представляю, как собрать всех детей для каждой вершины быстрее, чем за O(n log n).
Кстати, что вы хотите делать с элементами, которые упираются в циклы?
Пара дополнений.
1. На самом деле в обычном случае (без MapReduce) можно сделать проще. Берем все вершины, у которых нет родителя, и говорим, что они хорошие и ставим в качестве их корней их самих.
Дальше берем все вершины, про которые мы еще не знаем, хорошие они или нет. Смотрим, если их родитель хороший, то говорим, что и ребенок хороший и ставим корень, указанный в родителе.
2. Я тут понял, что даже если родитель один, детей может быть много. Не очень понятно, что делать в таком случае на шаге Reduce.
Блин, прикольно. До сих пор думаю. Пока можно уточнить, какой ответ мы хотим получить для циклов и ro-фигур.
В обычных условиях для такой задачи есть техника little step - big step. Заводим два указателя на один элемент. За одну итерацию один указатель передвигаем на родителя (little step), а другой -- на дедушку (big step). Итерации повторяем, пока не упремся или little step не совпадет с big step.
Если на big step мы уперлись и дальше идти некуда, то мы пришли в конец пути (прим. не забыть сделать один little step после).
Если в графе есть петля, то в какой-то момент big step догонит little step и они совпадут.
Повторение -- не проблема. Считаете расстояние между каждой парой комнат и на этом ищете коммивояжера. Начальную точку можно задать аккуратными начальными условиями динамики.
А что именно не срастается? Если вуз неплохой, можно на какие-нибудь школы попроситься. Я вот на MADALGO в Дании пару раз был. Очень достойный уровень, приезжают крутые дядьки, вам плюс в знания и резюме.
В любом случае, бигдата происходит там где есть бигдата. Мне пока единственное, что приходит в голову, это Яндекс или Mail.ru. Можно еще Контакт попробовать, но туда попасть по-сложнее будет.
MBakhterev: оп-па. А у Хоара-то в книжке предел другой. Он говорит, что предел определяется как . Кроме того, в теореме о неподвижной точке он берет бесконечную последовательность процессов, каждый из которых является подмножеством следующего. Если функция непрерывная -- -- то работает теорема. При это теорема активно использует именно это определение предела и то, что процессы друг в друга вложены.
MBakhterev: просто как я понял, каждый процесс - это множество строк, которое мы определяем рекурсивно. В первом случае у нас все процессы совпадают. Гм... во втором с beep у нас не получается частично упорядоченного множества: ни один процесс не является подмножеством другого. Просто картинка не складывается.
Али Алиев Почему нет? Гарднера можно за просто так читать.
Полистал вчера Андерсона. Что нужно из школьной программы, чтобы понять, что такое множество, граф, логическая формула, отношение? А это уже понятийный аппарат. Если кто-то подскажет, как связаны двумерный массивы и матрицы, таблицы в БД и отношения, графы и дружба в социальных сетях, совсем будет здорово.
При анализе свойств могут потребоваться экспоненты, логарифмы, суммы арифметичской и геометрической прогрессии. Но это отдельные темы, которые во-первых отчасти описаны в первых двух главах Кормена, во вторых их можно изучить отдельно, как только возникнет необходимость.
Я может не очень акцентировал внимание, но есть школьные олимпиады с тимуса (желательно первые), Эйлер и braingames. Решать их довольно увлекательно и мотивирует изучать книги выше.
А пробовали профилировать? Тормозит на построении дерева или на запросах? Если первое, то по эффективности в глаза бросается поштучная аллокация объектов. Возможно имеет смысл избавиться от класса prefixTreeNode и аллоцировать несколько больших массивов для хранения вершин.
И как ты (ничего?) планируешь определить, прекратили ли сокращаться цепочки?