|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rustam Gadeyev 2:5008/14 24 Oct 2001 20:17:36
To : Evgeny Sharandin
Subject : 8 мирных ферзей
--------------------------------------------------------------------------------
23 Окт 01 14:39, Evgeny Sharandin wrote Rustam Gadeyev:
RG>> Рекурсия всегда короче, но не быстрее.
ES> Точнее - не всегда быстрее ;). Здесь же была идея сделать две
ES> процедуры для учета повторяющихся комбинаций, но она не сработала ;(.
У рекурсии принципиально есть накладные расходы на стек, хотя бы на адрес
возврата. Так что в общем случае рекурсия тормознее.
ES> Hу кто же так делает? Сразу видно завзятого паскалиста ;). Замени
ES> арифметическое and на логическое (вместо & поставь &&) и все встанет
ES> на свои места. То, что ВС сработал в этом случае по короткой схеме
ES> характеризует его не лучшим образом.
Hу так BC почему-то не любит &&, условие тормознее делается. А вот для
микроконтроллеров && и || в самый раз.
RG>> (/5 /oilr /s).
ES> О! Оптимизатор ваткома всегда отличался причудливостью, а уж его
ES> разворачивание циклов... Вполне достаточно было бы /r.
Я проверял, просто r недостаточно.
Посмотрел на твой последний вариант, тоже самое, что и у меня было, инвариант,
просто оптимизатор компилятора BC не смог адекватно перевести это в команды,
пришлось немного помочь. Разница в том, что у тебя перебор столбца не с первого
элемента, а с конца. И еще постоянные смещения у тебя убраны в описание
массивов. Если бы я по алгоритму написал бы ассемблерную программу, то
получилось бы одинаково с твоего и моего исходника, ну с учетом разницы.
Я был удивлен, оказывается Borland постоянные смещения в массиве почти не
оптимизирует. Вот в d1[-1+n+t] удалось этот -1 учесть в смещении, а в
d2[num+n-t] этот num прибавлялся отдельной командой. TASM без проблем учитывает
постоянные смещения массивов, да и другие компиляторы С тоже могут также
оптимизировать.
А вообще действительно, еще немного удается ускорить, но уже не за счет
алгоритма, а за счет оптимизации. От перестановки мест слагаемых в индексе сумма
не меняется, зато получается сильно быстрее. Hапример d1[-1+b+t] преобразуется в
[ofs][bx][di], что лучше тупого вычисления окончательного адреса и даже еще
более тупого прибавления дополнительного смещения, которое я так не хотел
убирать. За счет этого удалось опять заметно ускорить С вариант, паскалевский я
трогать не стал, смысла нет делать это с BP7. Он все переменные хранит на стеке
вместо регистров и делает впустую излишние пересылки, как впрочем и BC. Исходник
приводить я уже не буду, все изменения в основном в целях помочь компилятору
сгенерировать более оптимальную конструкцию кода. Даже Ватком оптимизирует лишь
частности, а весь алгоритм реализует неоптимально. Так что ручками можно
добиться намного лучшего результата. Hо это уже не интересно, интереснее вопрос,
есть ли какие-то методы супероптимизаторов позволяющие получать оптимальную
реализацию небольших алгоритмов или все компиляторостроители продолжают генерить
код напрямую, а потом пытаются оптимизировать на уровне команд ассемблера?
Good Bye.
--- ---
* Origin: Ulan-Ude. Buryatia. (2:5008/14)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
