kb
16.02.2013 05:15
А я правильно понимаю, что в википедии тупые и в ленивых яп или просто при помощи итераторов (потоков) сложность по памяти при обходе bfs как раз линейная? http://en.wikipedia.org/wiki/Breadth-fir... Или таки я снова тупой?
12 comments
recommend
bookmark
subscribe
в энергичных тоже линейная, не видишь что ли?
Я хотел сказать константная.
не может быть константной. где-то да надо иметь список/очередь узлов текущего уровня, по детям которых на следующем шаге гулять.
Дык в том-то и дело, что не нужно держать весь список. Достаточно итерировать по одному элементу, забывая предыдущий и считывая следующий.
Обосрался я в том, что на картинке было дерево нарисовано, вот я дерево себе и представил в голове. А для графа таки нужно держать список, чтоб не идти по узлам, по которым уже ходил. Вот и всё.
не понимаю, как можно не иметь списка узлов текущего уровня. Покажешь код?
Да. Например, у тебя нода представлена как
type Value = Integer
data Node = Node { value :: Value, children :: [Node] }
Тогда взятие списка узлов дочернего уровня будет делаться при помощи
getSubNodes :: [Node] → [Node]
getSubNodes nodes = concatMap children nodes
concatMap память не жрёт.
а не будет ли concatMap, случаем, в своём "окружении" хранить nodes либо его часть?
Должен, чтобы getSubNodes выдавала результат.
Ну и считаем, что на каждом уровне длина списка nodes растёт, если в среднем более одного дитя у каждого узла (например, в случае околосбалансированного двоичного дерева).
короче говоря:
1. concatMap — не будет ничего хранить, а вот х-ль (в контексте полного алгоритма) будет хранить результат concatMap по той причине, что по нему придётся дважды пройтись (первый раз чтоб поискать по элементам, второй — чтоб сделать concatMap следующий).
2. Про высоту ты совершенно прав. Таки будет лишний расход на высоту дерева. Но высота, всё же, это не так страшно.
Итого: последнее усилие (после показанных в http://kb.psto.net/tszhsf ), которое я хочу сделать:
1. сгенерировать в меру широкое (чтоб хранение ширины было ощутимо по памяти) и очень высокое дерево
2. проходясь по нему убедиться, что данные с предыдущей высоты можно как-то освобождать (правда надо подумать, сможет ли это сделать GC)
ну я вот к тому, что совершенно константно не выйдет.
а большое по ширине — не надо, там будет всё хорошо, мне очевидно (concatMap при редукции будет просто хранить в окружении то, что осталось от текущего списка, список оставшихся списков, и не должен даже выделять памяти при этом).
ты прав, совершенно константно не выходит, но всё же получается O(w), где w — максимальная ширина дерева. При этом есть мысль, что если алгоритм распараллелить, то я могу сделать за константную память.
если параллелить, будем ли учитывать затраты памяти на контекст для каждого параллельного вычисления?
по поводу параллельности — это я, всё же, фигню написал. Если коротко — в конце концов я просто пришёл к поиску в глубину (хотя хотел просто побороть повторный проход по элементам одной высоты).
по поводу окончательных мыслей про всю эту "константную сложность по памяти". Всё же, чтоб показать, что оно работает, нужно:
1. построить в памяти строгое дерево (чтоб при хождении по нему память не выделялась)
2. убедиться, что х-ль не жрёт память, как при простом прохождении по его нодам с проверкой на равенство значнеию, таки при mapConcat этом для детей.
В теории, всё же, кроме памяти, необходимой для хранения дерева, другой потребоваться не должно (если я снова ничего не упустил).