В поисках истины. Часть 2. Software. ГП ДПИ.

Вы здесь:   >ГП ДПИ   >Software   >В поисках истины. Часть 2.

В предыдущей части мы остановились на том, что последний вариант ( rrev05 ) ускорился почти в 90 раз по сравнению с первоначальным. Неужели все проблемы быстродействия исходного варианта можно списать на rdc? Как мы уже видели, быстродействие этой подфункции может оказать заметное влияние на общее быстродействие, но далеко не решающее... Чтобы понять это окончательно сравним быстродействие нашего последнего "чемпиона" (речь идет только о функциях, которые, дают верный результат) с несколькими другими функциями. Для проведения этого сравнения я использовал несколько функций. Все они либо взяты прямо из форума, либо составлены на прозвучавших там идеях. Я позволил себе лишь незначительные изменения и изменения некоторых названий - так мне было проще проводить дальнейшие сравнения. Итак, вот эти функции:

(defun frev (x / i res)
  (foreach i x (setq res (cons i res)) ))
Думаю легко узнаваемый вариант предложенный Эдуардом...
(defun mrev (x / res)
  (mapcar '(lambda(z)(setq res (cons z res))) x )
  res)
а такого варианта в "конфе" не было, но идея использовать mapcar - вот я и решил попробовать...
(defun wrev (x / res)
  (while (setq res (cons (car x) res)
	       x   (cdr x)))
  res)
этот вариант был необходим чтобы представить практически все что возможно для обычных, не рекурсивных, вариантов. Вполне возможно, я упустил какой-нибудь еще интересный вариант, но тут уж вся надежда на дотошных читателей, если мне пришлют какой-нибудь интересный (быстродействие имеет значение) вариант, то я с удовольствием включу его в это сравнение.
И ведь прислали (большое спасибо leha2k!!!)
То, чего (по моему мнению) не хватает в Вашем анализе:
Вы рассмотрели все стандартные (или встроенные - как назвать неважно)
разновидности циклов, кроме repeat. Есть два варианта:

(defun myreverse25 (lst / nmb answer)
  (setq nmb -1)
  (repeat (length lst)
    (setq answer (cons (nth (setq nmb (1+ nmb)) lst) answer))
  );repeat
);defun
Очень медленный, но не из-за repeat, а из-за nth. Ну это понятно.
Действительно с этим вариантом все ясно заранее, и с "диагнозом" я полностью согласен. Первоначально, я хотел включить нечто подобное в обзор сразу, но потом подумал что это едва ли будет интересно. А теперь подумал еще и решил - ну почему собственно нет?
(defun myreverse26 (lst / i answer)
  (repeat (1- (length (setq lst (cons -1 lst))))
    (setq answer (cons (car (setq lst (cdr lst))) answer))
  );repeat
);defun
Есть несколько лишних операций, но они выполняются всего ОДИН раз -
соответственно на производительности не особенно сказываются. Думаю,
что этот вариант будет примерно на уровне foreach (может чуть
медленнее).
Эти два варианта нужны только для полноты картины, чтобы действительно
в итогах можно было сказать, что рассмотрены все разновидности циклов.
Для этого обзора, и исключительно для него, интересный вариант. Но думаю ни с одним из итерационных вариантов он едва ли сможет поспорить - просто на те конструкции задача "ложится" более естественно. Впрочем, посмотрим...
(defun rev(x) (rev0 x nil))
(defun rev0 (x y)
  (cond ((null x) y)
	(t (rev0 (cdr x) (cons (car x) y))) ))
Ну а это, то что у меня получилось из функции предложенной Олегом. Разумеется, можно было бы переписать и с использованием функции atom, как в условии на форуме, но этого я делать не стал...
Ваш вариант rev0 явно хуже
первоначального варианта Олега. Хуже по двум причинам:
Первая: cond работает медленнее if, т.е.:
(defun rev00 (x y)
  (if (null x)
    x
    (rev00 (cdr x) (cons (car x) y))
  );if
);defun
Будет уже быстрее Вашей rev0 (можете замерить, не на много, но
быстрее). Тут я согласен с casual goer: "cond при таких условиях
неоптимален".
Вторая: использование лишней здесь функции null. Она конечно базовая и
очень быстрая, но какое-то время занимает и у Олега ее нет. Думаю,
вариант с null будет работать с той-же скоростью, что и вариант Олега
с притянутым atom. Но это будет медленнее первоначального варианта.
Давайте проверим и это, раз уж мы взялись выяснять истину...
(defun REVERSE3 (l)
  (if (not (atom l))
    (append (REVERSE3 (cdr l)) (list (car l))) ))

Инструмент для измерения времени работы той или иной функции остался тем же что и предыдущей части, хотя появились некоторые нюансы в его использовании. Но об этом по ходу. Итак для начала вспомним результат нашего "чемпиона":
_$ (evaltime '(repeat 10 (rrev05 l1k)))
Время выполнения  2.36  секунд
_$ (evaltime '(repeat 10 (rrev05 l1k)))
Время выполнения  2.36  секунд
_$ (evaltime '(repeat 10 (rrev05 l1k)))
Время выполнения  2.31  секунд
чтобы получить этот результат пришлось немного повозиться с выделением дополнительной памяти Лиспу (expand 10000) хоть и отрабатывал довольно длительное время, но позволил добиться того, что в ходе проведения замера не запускалась автоматическая "сборка мусора" и результаты стали более-менее стабильными. Первоначально, правда, я планировал измерять скорость (repeat 100 (rrev05 l1k)), но тут я не смог быстро победить "сборку мусора" и решил остановиться на достигнутом... А теперь - наши новые функции, для большего удобства я собрал их результаты в таблицу:
100*1k10*1k
rrev05   2.36 2.36 2.31
reverse3   4.34
frev 0.82 0.83 0.83  
mrev 0.6 0.61 0.66  
wrev 0.83 0.77 0.83  
myreverse25 5.44 5.44 5.44  
myreverse26 1.21 1.26 1.21  
rev 1.37 1.43 1.37  
rev00 1.32 1.27 1.32  
myreverse 1.1 1.1 1.1  

Сперва "новички". Если с myreverse25 все как ожидалось, то myreverse26 показал себя далеко не так уж резво, как можно было того ожидать. Особенно удивляет тот факт, что этот вариант умудрился проиграть даже лучшему из рекурсивных. А лучшим из рекурсивных стал, как и предсказал leha2k первоначальный вариант Олега (myreverse). Мне остается только принести Олегу свои извинения за столь грубое искажение результатов своими (отнюдь не злонамеренными) исправлениями исходного варианта. Зато сколько информации к размышлению...
Бросается в глаза что даже самому "медленному" варианту наш "чемпион" (теперь уже предыдущий) уступает просто неприлично много (более 16 раз). Весьма близкие результаты показала и reverse3, функция, которую casual goer предлагал в качестве своеобразного теста. Вообще-то результат вполне закономерный, если помните я отнес в список "плохих" функций append, last, length, nth, remove, reverse (список, безусловно, далеко не полон...) - таким образом мы увидели соревнование append и reverse... К сожалению, я не смог, исключить "сборку мусора" при измерении скорости работы reverse3 - вполне возможно что реально она примерно на секунду быстрее. Почему append несколько медленнее reverse? Вот здесь могу ограничиться лишь гипотезами: append вынужден принимать два аргумента, в то время как reverse лишь один - вполне возможно что затраты на организацию передачи двух аргументов выше, влияние других функций едва ли может быть столь заметным.
$ (evaltime '(append L1m '(1)))
Время выполнения  0.5  секунд

_$ (evaltime '(reverse L1m ))
Время выполнения  0.44  секунд
меня такие результаты, если честно, не особо удивляют...
Почему замена last на car почти не отобразилась на общей производительности мы уже разбирались... Удивительно ровно выступили три новых варианта, причем такой значительный (относительно, конечно) отрыв функции, использующей mapcar, если честно, был для меня довольно неожиданным... "Выступление" варианта Олега можно признать более чем удовлетворительным, особенно если вспомнить какими значительными затратами сопровождается вызов пользовательской функции (ну помните rrev3 и rrev4 ??). Интересно насколько линейны результаты новых функций (точнее, сомнений в том что первые три линейны - нет практически ни каких, и речь больше идет именно о rev)?
100*1k10*10k
frev 0.82 0.83 0.83 0.82 0.82 0.83
mrev 0.6 0.61 0.66 0.66 0.66 0.66
wrev 0.83 0.77 0.83 0.77 0.77 0.83
myreverse25 5.44 5.44 5.44 68.8 !!!
myreverse26 1.21 1.26 1.21 1.26 1.32 1.32
rev 1.37 1.43 1.37 1.43 1.42 1.43
rev00 1.32 1.27 1.32 1.32 1.31 1.32
myreverse 1.1 1.1 1.1 1.15 1.15 1.16
как видим, все функции (кроме myreverse25, что и понятно) показали свою практически полную "линейность" (все аномалии в пределах точности измерений). Вообще-то результаты легко предсказуемые и вполне ожидаемые. Совершенно другая картина должна быть для rrev05 (мы помним, что там есть две функции, которые являются сами по своей сути циклами - last и reverse). К сожалению, проверить скорость работы этой функции на списке из 10 тыс. элементов мне просто не хватило терпения, поэтому пришлось двигаться в сторону уменьшения списка:
100*10050*20010*1k
rrev05 0.44 0.38 0.44 0.6 0.6 0.6 2.36 2.36 2.31
rrev05* 0.044 0.038 0.044 0.12 0.12 0.12 0.236 0.236 0.231

* - пересчитанные результаты без repeat
не очень-то похоже на "линейность"... пожалуй, это гораздо ближе к чему-то типа n2/2 (не забыли еще про сумму от 2 до n?). Итак, как, пожалуй, можно сделать вывод - как бы ни хороша была бы функция rdc3 (так уж получилось что именно она используется в rrev05), все равно она является циклом (пусть даже очень быстрым, реализованным на уровне встроенных функций). А раз так, то результирующая функция автоматически становится "нелинейной". Собственно, это почти то, что я и пытался доказать - при использовании любой "циклической" функции должно быть крайне осторожным, во всяком случае, программист обязан представлять себе ту степень опасности, которую таит в себе их необдуманное использование.

Впереди еще одна часть. Там я планирую рассмотреть как изменится быстродействие рассматриваемых вариантов после их компиляции. Только это будет чуть позже. Если честно, то написание этих двух забрало гораздо больше времени, чем планировалось в начале - выходные получились почти без отдыха...