|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rustam Gadeyev 2:5008/14 27 Oct 2001 12:07:44
To : Evgeny Sharandin
Subject : 8 мирных ферзей
--------------------------------------------------------------------------------
27 Окт 01 00:15, Evgeny Sharandin wrote Rustam Gadeyev:
RG>> У рекурсии принципиально есть накладные расходы на стек, хотя бы
RG>> на адрес возврата. Так что в общем случае рекурсия тормознее.
ES> Hе всегда рекурсивный алгоритм может быть так безболезненно заменен на
ES> цикл, как это было в рассматриваемом случае. Может потребоваться
ES> сохранять результаты предыдущих итераций, для чего придется самому
ES> лепить некий аналог стека. И здесь аппаратный стек может оказаться
ES> гораздо быстрее.
Согласен, теоретически могут быть и такие случаи, хотя до сих пор они мне в
явном виде не попадались.
ES> впрочем, тоже). Hо есть более принципиальные моменты. В твоем случае
ES> внутри цикла сидит два последовательных цикла, в моем - один с
ES> небольшим хвостиком (c рестартом на
ES> внешний цикл, а не на последующий). Это не дает никаких альтернатив
ES> оптимизатору при распределении переменных по регистрам (gpc умудрился
ES> распихать по регистрам не только переменные, но и адреса массивов).
ES> Кроме того, модификация переменных максимально приближена к проверкам
ES> их значений. Hапример, dec(x); if x=0... Это позволяет компилятору
ES> слить два оператора (декремента и сравнения с нулем) в один.
Hу это-то не новость, когда два года ежедневно просматриваешь листинг программы,
как он там был выражен в виде ассемблера микроконтроллера и при этом есть
сильное ограничение по объему кода, плюс в отдельных местах нужно уложиться по
быстродействию, то быстро вникаешь во все тонкости типа цикла
i=100; do { } while (--i); который наиболее оптимален в ассемблере.
Да, я в своем последнем варианте именно так и сделал. Привел все смещения к 0,
основной перебор теперь идет с минимальными потерями без захода в цикл. Hо с
переходами BC3 сильно напортачил. JMP, JNx друг на друга целый блок, это я не
хотел применять прямой goto в нужное место, а фиктивный do { } while (0); с
continue по условию внутри неадекватно воспринимается BC. Это IAR меня
расслабил, у него таких ляпов нет.
ES> Если планируется защищенный режим, то наличие единицы не
ES> принципиально. Что есть она, что нет - все равно одна инструкция
ES> процессора. Убирать ее имеет смысл только при использовании тупого
ES> компилятора под RM или PM с 16-тибитными регистрами. BP или BC,
ES> например ;)))
Hе, постоянное смещение должно быть бесплатным независимо от режима. А вот если
все элементы сделать размером с DWORD, то 32-битный режим адресации будет весьма
к месту.
По крайней мере, совершенно неоптимизированный вариант удалось за счет
оптимизации ускорить в несколько раз. Hо алгоритм при этом принципиально не
поменялся, а именно это я и хотел узнать в первом письме. А то я уже видел тут
недавно исходник на С про 8 ферзей, где автор, не долго думая, реализовал
очевидный алгоритм, который должен просто смертельно тормозить на больших
размерах доски. Видимо такие алгоритмические задания студентам не изменялись со
времен IBM PC/XT 4.77MHz, который загружался с дискеты объемом 160Kb, - не у
всех были винты с невероятным объемом 5-10Mb.
Good Bye.
--- ---
* Origin: Ulan-Ude. Buryatia. (2:5008/14)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
