Breadth-first traversal on Cell.

[thesz]

DDJ 's article on subject

Цитата:On a Pentium 4 HT running at 3.4 GHz, this algorithm is able to check 24-million edges per second. On the Cell, at the end of our optimization, we achieved a performance of 538-million edges per second. This is an impressive result, but came at the price of an explosion in code complexity. While the algorithm in

Comments

[nealar]

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

[thesz]

Не на асме, на Си.

Ну, самое простое, пожалуй: на шаге нам надо получить множество S всех вершин, связанных с текущим списком стартовых и граф G, в котором убраны все связи с текущими стартовыми вершинами.

--вариант использования:
(s',g') = bfsStep s g -- как сделан bfsStep, я не знаю.

Вот шаги по графу:

bfsSteps s g = iterate (uncurry bfsStep) (s,g)

Наш поиск вширь заканчивается, когда текущее множество стартовых вершин станет пустым:

bfs s g = takeWhile (not . empty) $ map fst $ bfsSteps s g

Форсирование очередного g' на выборке следующего за очередным s' приводит к тому, что отрезание вершин в графе g'' выполняется уже за меньшее время.

От того, что кусочки графа будут не форсированы мы, действительно, не застрахованы. Ну, и что? Все равно эти кусочки будут выброшены. ;)

[nealar]

Надо мне какой-нибудь таг на твои записи ставить "toreadlater". Не всегда моск принимает запись, когда она появляется, а потом я часто забываю перечитать.

[nealar]

Что такое bfStep?

[levgem]

а чего тебе не нравится?

[thesz]

Мне бы подошла статья, где берется код в 1500 строк и урезается до 28. ;)

[levgem]

С 5-кратным ускорением

[thesz]

Да. Именно.

Урезается до 28 строк с пятикратным ускорением. ;)