Как можно найти петлю в односвязном списке при помощи MapReduce?
У меня имеется набор элементов, которые могут иметь родителя такого же типа. Элементы, имеющие родителей, образуют графы (односвязные списки).
Моя задача заключается в том, чтобы для каждого элемента, имеющего родителя-не вершину, указать в качестве родителя элемент, являющийся вершиной всей цепочки. Например: из 1 -> 2 -> 3 -> 4 нужно получить: 1 -> 4, 2 -> 4, 3 -> 4.
Вот мой алгоритм:
На вход Map подаются пары элементов C -> P. На выход Map я отправляю пары C -> P, P -> C.
Таким образом на вход Reduce поступает элемент в качестве ключа K, его родитель P и ребёнок C: K -> {P, C}.
На выходе Reduce шага я сообщаю ребёнку элемента-ключа, что теперь его родителем будет родитель элемента-ключа.
Так как списки небольшой длины, то за небольшое количество итераций MapReduce вся работа проделывается. Но если существует петля, то цепочки уже не сокращаются.
Так вот вопрос, как можно локализовать и устранить петлю. Или, может, кто-нибудь придумает более элегантный алгоритм для поставленной задачи.
Задача непонятно сформулирована. Я понял, что есть набор элементов. Для каждого элемента определен следующий. Глобально, элементы могут образовать несколько компонент связности, каждая из которых либо путь, либо цикл, либо образуют букву p (хвост + петля).
А вот что значит, выкинуть посредников, я не понял. Можете как-то более обще сформулировать?
И еще объяснить, где у вас закончилась задача, и начался алгоритм.
Блин, прикольно. До сих пор думаю. Пока можно уточнить, какой ответ мы хотим получить для циклов и ro-фигур.
В обычных условиях для такой задачи есть техника little step - big step. Заводим два указателя на один элемент. За одну итерацию один указатель передвигаем на родителя (little step), а другой -- на дедушку (big step). Итерации повторяем, пока не упремся или little step не совпадет с big step.
Если на big step мы уперлись и дальше идти некуда, то мы пришли в конец пути (прим. не забыть сделать один little step после).
Если в графе есть петля, то в какой-то момент big step догонит little step и они совпадут.
Пара дополнений.
1. На самом деле в обычном случае (без MapReduce) можно сделать проще. Берем все вершины, у которых нет родителя, и говорим, что они хорошие и ставим в качестве их корней их самих.
Дальше берем все вершины, про которые мы еще не знаем, хорошие они или нет. Смотрим, если их родитель хороший, то говорим, что и ребенок хороший и ставим корень, указанный в родителе.
2. Я тут понял, что даже если родитель один, детей может быть много. Не очень понятно, что делать в таком случае на шаге Reduce.
Про little step - big step знаю как "Fast step - Slow step"
Ваш алгоритм имеет сложность между O(nlogn) и O(n^2). С такой сложностью у меня тоже есть несколько. Но вот хочется что-то ближе к O(n).
В асимптотике есть некоторая проблема даже с вашим алгоритмом. По задаче у каждого элемента не более одного родителя. Но как я понимаю, у каждого элемента может быть сколько угодно детей. Я пока не представляю, как собрать всех детей для каждой вершины быстрее, чем за O(n log n).
Кстати, что вы хотите делать с элементами, которые упираются в циклы?
Да, мой алгоритм по разбору в худшем случае O(nlogn), в лучшем O(n)
Что делать... Надо разрывать цикл. Начиная от рандомного элемента цепочки, заканчивая анализом всей цепочки, и по результатам анализа разрывать.
Я подумал. Наверное, самое простое, это добавить в возвращаемое значение расстояние до предка. Понятно, что за O(log n) итераций мы либо упремся в корень, либо расстояние превысит n, и это будет намек. =)
SeptiM: Так проблема то в том, что в MapReduce мы не можем видеть больше двух рёбер одновременно. В моём алгоритме с каждой итерацией сокращается количество цепочек с длиной больше 1. И тот момент, когда это количество прекращает сокращаться, означает, что остались только петли
jonasas: Мне кажется, терминология расползлась. Что значит, не видим больше двух ребер? Мы видим окрестность для каждой вершины. Там может быть сколько угодно ребер.
И как ты (ничего?) планируешь определить, прекратили ли сокращаться цепочки?
Каждый раз, когда на Reduce шаге мне попадается элемент, у которого есть и ребёнок и родитель, это означает, что есть цепочка длинной более одной связи. Есть счётчик, который подсчитывает это дело.
Первый map принимает на вход пары С -> P и эмитит две пары: C -> (P, +1), P -> (C, -1). Второе число -- это расстояние со знаком. В сторону корня положительное.
Reduce собирает для каждой вершины её окрестность. Работать будет за O(n log n), но что поделаешь.
Дальше каждый map принимает на вход окрестность. Она может иметь вид несколько детей -> родитель -> несколько предков. Оставляем самого далекого предка (G, d_g). Выкидываем родителя. Для каждого ребенка (C, -d_c) эмитим пары С -> (G, d_g + d_c) и G -> (C, -(d_g + d_c)).
Reduce снова собирает окрестность.
Через log n операций мы останавливаемся и выкидываем все пары, которых расстояние больше чем n.
Может я путаю, но это должно по количеству операций занимать O(n log^2 n).
