@jonasas

Как можно найти петлю в односвязном списке при помощи 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 вся работа проделывается. Но если существует петля, то цепочки уже не сокращаются.

Так вот вопрос, как можно локализовать и устранить петлю. Или, может, кто-нибудь придумает более элегантный алгоритм для поставленной задачи.
  • Вопрос задан
  • 615 просмотров
Пригласить эксперта
Ответы на вопрос 1
@SeptiM
Задача непонятно сформулирована. Я понял, что есть набор элементов. Для каждого элемента определен следующий. Глобально, элементы могут образовать несколько компонент связности, каждая из которых либо путь, либо цикл, либо образуют букву p (хвост + петля).

А вот что значит, выкинуть посредников, я не понял. Можете как-то более обще сформулировать?
И еще объяснить, где у вас закончилась задача, и начался алгоритм.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы