|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
21.04.2013, 20:08 | #11 | |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Цитата:
Причины этому, минимум, две: 1. Реализация: вариант с очередью/стеком намного эффективнее, причем сразу с нескольких сторон: как по используемой памяти, так и по вычислительным ресурсам. А на современных суперскалярных процессорах разница еще больше возрастает. 2. Алгоритмически: для данной задачи оптимальнее вариант с очередью, а рекурсия безальтернативно подразумевает только стек. PS. Вообще мне кажется неверным привязываться к какой-либо "классической" реализации, которая когда-то была опубликована автором исключительно в демонстрационных целях. Основное - идея алгоритма. Я, например, не называю алгоритм своим именем, хотя и изобрел его самостоятельно, причем именно в оптимальной реализации - с очередью и без рекурсии. А называю алгоритмом Дейкстры - исключительно потому, что до основной идеи Дейкстра додумался раньше меня. |
|
21.04.2013, 20:49 | #12 | ||
Играюсь с Python
Форумчанин
Регистрация: 12.12.2012
Сообщений: 340
|
Цитата:
Там вроде нужно чтобы куски памяти рабочей области не использовались разными потоками одномоментно, и один главный рулил дочерними нитками ? Как это вообще может быть представлено в многоядерной реализации? Вот тебе Ваня кусок карты и иди на лево! И вот тебе Петя тоже кусок карты иди на право! Младший вообще идет лесом! А их батя обоих с колокольни мониторит и кричит куда идти и идти ли при этом не допускает их встречи иначе работа встанет ?? Цитата:
|
||
21.04.2013, 21:27 | #13 |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,646
|
s-andriano, хотелось бы на вашу реализацию глянуть.
На счет моей реализации, то могут быть и плохие ситуации, когда потребуется обойти почти все клетки. То есть я не говорю, что алгоритм оптимален, просто проведена оптимизация одного из самых примитивных алгоритмов (не знаю, есть ли у него какое-то официальное название). Но при желании еще есть над чем работать. P.S. На счет имени, то я его своим именем не называл, в коде комментарий указывает на то, что "Алгоритм реализовал Arigato", а не разработал. Не исключаю, что реализованные идеи были кем-то раньше уже опробованы. E-Mail: arigato.freelance@gmail.com
|
22.04.2013, 18:55 | #14 | ||
Играюсь с Python
Форумчанин
Регистрация: 12.12.2012
Сообщений: 340
|
Цитата:
Цитата:
1. Рекурсивный алгоритм поиска пути от Arigato. (C)(tm)(R) (Year). И всем все понятно. Кто не согласен см. п1. |
||
22.04.2013, 19:55 | #15 | |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
А зачем?
Что нам нужно, чтобы программа работала быстро, или чтобы алгоритм был заточен под многоядерность? Если первое, то во втором нет никакой необходимости. Цитата:
Когда я изобретал алгоритмы, И-нета у меня не было, а бумажная литература была в большом дефиците. Не говоря о том, что ни в одном учебном заведении в нашей стране подобные алгоритмы не изучали. Сегодня же - "изобретательность" скорее свидетельствует о недостатках образования и неумением пользоваться поиском. Так что палка о двух концах. |
|
22.04.2013, 20:04 | #16 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Ну, это зависит от того, насколько хочется.
Код, как я уже говорил, был написан во времена 100-166 МГц процессоров. В принципе, я барахольщик и ничего не выбрасываю, а также не допускаю непреднамеренной потери данных. Но по этой же причине найти что-то в старых архивах - дело не совсем простое. Алгоритм был написан на Ассемблере с развернутыми циклами и "заточен" под конкретную задачу (опять же, для обеспечения максимальной производительности), так что возможность адаптировать его на более общий случай - под вопросом. В общем, если это действительно интересно (т.е. больше, чем просто любопытно), то поищу, но это займет некоторое время. PS. Да, еще: алгоритм умышленно не отсекался после нахождения пути. Во-первых, при различной проходимости клеток вполне возможна ситуация, когда содержащий большее количество клеток путь может оказаться намного короче. А во-вторых, мне нужно было все поле, чтобы при "пролете" мышки над каждым квадратом сразу было видно расстояние (переопределялся курсор мыши) . Последний раз редактировалось s-andriano; 22.04.2013 в 20:11. |
22.04.2013, 20:50 | #17 | |||
Играюсь с Python
Форумчанин
Регистрация: 12.12.2012
Сообщений: 340
|
Цитата:
Цитата:
Цитата:
|
|||
22.04.2013, 21:47 | #18 |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,646
|
s-andriano, ну если сложно найти, да и реализация специфическая, то не надо утруждаться
Основная идея моей реализации - уменьшить количество проходов по неправильным клеткам, чтобы они все лежали недалеко от идеального пути. Не всегда, но зачастую это удается. Волновой же алгоритм в общем случае просмотрит все клетки в некотором радиусе. Вот, кстати, неплохой онлайн тест алгоритма: http://suvitruf.ru/2012/05/13/1176/ Видно, что он выдает хуже результат, чем у меня. E-Mail: arigato.freelance@gmail.com
|
22.04.2013, 23:42 | #19 | |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Цитата:
И - никакой самостоятельности. Могу только повториться, пытаться распараллелить конкретный алгоритм и пытаться решить задачу за минимальное время - далеко не одно и то же. Любое распараллеливание требует дополнительных ресурсов, причем, нередко бывает, что объем этих ресурсов превосходит выигрыш от распараллеливания. Что касается алгоритма Дейкстры, то для интересных с точки зрения практики случаев IMHO может представлять интерес пускать его однопоточную версию в разных потоках для разных юнитов. |
|
22.04.2013, 23:47 | #20 | |
Старожил
Регистрация: 28.01.2009
Сообщений: 21,000
|
Цитата:
хотите об этом поговорить? Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
Программа делает то что написал программист, а не то что он хотел. Функции/утилиты ждут в параметрах то что им надо, а не то что вы хотите. |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Поиск пути | Alexandr555 | Общие вопросы C/C++ | 5 | 29.01.2013 20:00 |
поиск пути | Nikita1111 | Visual C++ | 1 | 09.02.2012 00:44 |
Пропишите программу в pascal! Пока не сдам прогу- домой не отпустят. Курсантский отпуск короткий, а домой хочется! | Brusik | Помощь студентам | 0 | 09.07.2011 15:37 |
Поиск пути | Federal | Помощь студентам | 1 | 19.06.2011 12:24 |
поиск пути | NiCola999 | Общие вопросы C/C++ | 19 | 16.11.2009 09:25 |