Alexey_Donskoy писал(а):
alexus писал(а):
Я повторю, что алгоритм оптимизировался для последующей реализации на ассемблере, а там всё в руках программиста... Например, в той реализации, о которой шла речь никаких push/pop не было.
Пожалуйста. Но тут есть принципиально важное замечание - приведённый алгоритм не идентичен Вашей ассемблерной реализации. Об этом моменте я тут как-то писал в теме
Что же такое алгоритм?Потому как реализация машинно-зависима, и особенно машинно-зависимы "технические характеристики".
В то время как в самом алгоритме нет никакого процессора, кэша, конвейера и особенностей их взаимодействия.
Говорить об "идентичности" неправильно. Дело в том, что запись алгоритма и реализация алгоритма используют разные языки. Поэтому реализация может только соответствовать алгоритму или не соответствовать, а быть идентичной, в общем случае, не может (разве что процессор поддерживает язык записи алгоритма). Д.Кнут описывает алгоритмы, потом приводит их реализацию на ассемблере. Вы считаете, что эта работа не имеет смысла, поскольку описание - это одно, а реализация совсем другое?.. Другие авторы использовали готовые алгоритмические языки, третьи выдумывали новые (псевдо-)языки. Мне думается, что важно и то, и другое (и описание алгоритма, и его реализация).
Alexey_Donskoy писал(а):
Как вообще можно оценить эффективность именно алгоритма?
Считать по количесвту операций? Вообще не прокатит, уж сильно они разные.
Да, различны... Но эффективность оценивается по определённым операциям, например, операциям сравнения, чтения/записи и т.п. И в оценке работы алгоритма записывают, что он требует, например, N операций сравнения в худшем случае. Другой алгоритм, дающий тот же результат, требует N^2 операций сравнения. Теперь у нас есть основание для сравнения данных алгоритмов. Если операции сравнения для нас не являются показательными, то надо сменить критерии оценки... Только и всего...
Alexey_Donskoy писал(а):
alexus писал(а):
Вы считаете, что предложенный вариант хуже оригинального из-за большего количества ограничений?..
Считаю, что хуже. Потому что эффективность его непредсказуема из-за машинной зависимости (как правило, рекурсия - очень дорогой механизм). В то время как ограничения по ресурсам (память) заранее очевидны.
А Вы оригинал смотрели? Там всё та же рекурсия, и расход по памяти совершенно тот же... (ни на бит больше или меньше).
Alexey_Donskoy писал(а):
Кстати, сравните, насколько для большинства процессоров пара лишних присваиваний (пусть даже с косвенной адресацией) эффективнее вызова процедуры с параметрами. Это общий принцип, Ваша ассемблерная реализация может его и нарушить - в частном случае...
Алексей, не надо сравнивать зелёное с теплым... Это не слишком правильно. Операция записи в память может быть довольно долгой. Посмотрите для примера на многопроцессорные SMP-архитектуры. Прежде, чем записать что-то в память, должна быть выполнена операция синхронизации кэшей процессоров (соблюдение когерентности кэшей). Это объясняет почему производительность компьютеров не растёт пропорционально количеству установленных в нём процессоров/ядер. При прохождении определённого предела количества процессоров/ядер производительность компьютера может не расти, а снижаться... С другой стороны, мы привыкли, что память работает очень быстро, но это не всегда справедливо. Та же флэш-память работает значительно медленнее, и чтение/запись в эту память может происходить существенно медленнее, чем выполнение рекурсивного вызова...
Alexey_Donskoy писал(а):
Судя по ответам в упомянутой теме, общая постановка вопроса никого особо не интересует.
В лучшем случае - интересует переносимость алгоритма (то есть его некие абстрактно-сферические в вакууме свойства, которые для конкретного исполнителя будут в общем случае заведомо неэффективны)...
Ну, раз нет интереса, значит надо закрыть тему... Вот и всё.