В поисках истины (или последствия одной дискуссии в интернет-форуме). Software. ГП ДПИ.

Вы здесь:   >ГП ДПИ   >Software   >В поисках истины (или последствия одной дискуссии в интернет-форуме).

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

Попытаюсь сперва кратко передать суть разборок в форуме. Все началось с вопроса одного студента, который просил помочь построить нисходящий вариант рекурсивной функции reverse без использования функции append (преподаватель, очевидно, решил потренировать своих студентов в написании элементарных Lisp-функции с помощью базовых - желание, вообще-то похвальное, хотя и не все придерживаются этого мнения). Ход любой дискуссии в интернет-форумах довольно часто отличается непредсказуемостью поворотов. Так случилось в этот раз. После ряда уточнений исходных условий появился вариант (автор некто Олег), который на мой взгляд почти идеально (почему не полностью - см. ниже) соответствовал заявленным требованиям:

(defun MyReverse (Spis)
  (Recurse Spis nil)
)

(defun Recurse (Spis Rezult)
  (if Spis
    (Recurse (cdr Spis) (cons (car Spis) Rezult))
    Rezult
  )
)
Сперва были высказаны (тем самым студентом) сомнения в том, что данный является "нисходящим". Когда я предложил вариант определения, согласно которому рекурсию можно назвать нисходящей в том случае, когда результат строится во время прямого хода (или движения вниз-вглубь по списку) и восходящей, соответственно, в случае когда, результат строится во время обратного хода. Такое определение представляется мне достаточно логичным и (в форуме) не было оспорено. Если я все же не прав - объясните мне (только аргументировано) почему. Но, если принять это определение, то убедиться, что предложенный вариант функции именно нисходящий можно с помощью обычной трассировки:
Ввод (RECURSE (1 2 3 4) nil)
  Ввод (RECURSE (2 3 4) (1))
    Ввод (RECURSE (3 4) (2 1))
      Ввод (RECURSE (4) (3 2 1))
        Ввод (RECURSE nil (4 3 2 1))
        Результат:  (4 3 2 1)
      Результат:  (4 3 2 1)
    Результат:  (4 3 2 1)
  Результат:  (4 3 2 1)
Результат:  (4 3 2 1)
Хорошо видно, что результат и в самом деле строится при движении вниз (вглубь), а на верх передается уже сформированный результат.
Довольно неожиданно (некто casual goer) поставил под сомнение вообще правомерность деления рекурсии на нис- и восходящую (а может быть предложенного только определения), мотивируя это тем, что: "рекурсия может вообще не возвращать результат (ни в каком обрабатываемом виде), может возвращать его (вовне) на каждой итерации (и не иметь формального возврата при завершении) или любой комбинированный в вариант - классифицировать рекурсию по этому параметру, это всё равно, что обувь выбирать по дню недели, как это делает "поколение пепси", а потом получаются программисты уровня: "стою на асфальте, в лыжи обутый..."повторю - рекурсия это всего лишь _самовызов_" и форум живо перекинулся на обсуждение этой "свежей" мысли. Когда же я попытался объяснить что классификация не обязана строиться по единственному признаку, а классификация рекурсии "Есть и довольно обширна" последовал ответ: "классификация должна упрощать понимание, а не запутывать, что как раз и происходит тут". Я не стал засорять форум, но здесь не могу удержаться, мне представляется примерно такой диалог:
- этот автомобиль дизельный?
- нет, он переднеприводной!!
- вы что оба дальтоники? он ведь красный!!!  
автомобили невозможно классифицировать по единому признаку, думаю с этим спорить никто не будет, точно так же и у рекурсии есть несколько параметров по которым можно ее классифицировать. Для меня не ясно, что здесь вызывает у некоторых удивление?!
тем не менее, в ходе этой дискуссии, появился еще один вариант функции от casual goer:
(defun rdc (l)
    (if (> (length l) 1)
        (cons (car l) (rdc (cdr l)))
    ) ;_ end of cond
) ;_ end of defun
;;; Вспомогательная функция обратная - cdr.

(defun rev (l)
    (if (not (atom l))
        (cons (last l) (rev (rdc l)))
    ) ;_ end of if
) ;_ end of defun

вызываем - (rev )
это уже не так "по-лисповски", но формально, соблюдаются выставленные условия
комментировать подробнее не вижу смысла - всё предельно элементарно
(комментарии автора)
Сперва я вообще не обратил на него почти ни какого внимания, но затем вдруг всплыл вопрос о быстродействии различных вариантов, я сравнил варианты Олега и Эдуарда:
(defun myreverse2 (lst / i answer)
  (foreach i lst
    (setq answer (cons i answer))
  );foreach
);defun
при попытке оценить быстродействие варианта от casual goer я столкнулся с тем, что функция оказалась чудовищно медленной. Именно это и заставило меня посмотреть на нее более внимательно. Уже беглого взгляда оказалось достаточно чтобы установить возможную причину. Сразу бросается в глаза использование в рекурсивной функции "сложных" функций (в данном случае last и length). Я написал об этом. На что последовала реплика: "не надо опять выдавать домыслы за истину. причина удручающей производительности совсем в другом (и она, кстати, совершенно очевидна...), но кому это интересно - выводы уже сделаны на основе домыслов..." Я хочу показать, что мои заявления вовсе не лишены основания. На этом вводная часть заканчивается и начинается собственно поиски истины...

Поиски истины не всегда дело простое, вот и в данном случае, пришлось потратить довольно значительное время на получение публикуемых результатов. Итак, сперва инструмент для измерения скорости выполнения тех или иных функций:

;******************************************************************************
; Рыбас В.И.                                                           05.02.91
;------------------------------------------------------------------------------
; Программе передается символ, который вычисляется.
; expr - символ...
;------------------------------------------------------------------------------
(defun evaltime (expr / sec sec1 v)
   (setq sec  (* 86400.0 (- (getvar "tdusrtimer")
                            (fix (getvar "tdusrtimer")))))
   (eval expr)
   (setq sec1 (* 86400.0 (- (getvar "tdusrtimer")
                            (fix (getvar "tdusrtimer")))))
   (setq v (- sec1 sec))
   (princ (strcat "\nВремя выполнения  " (rtos v 2 3) "  секунд"))
   (princ)
)
;------------------------------------------------------------------------------
а теперь наши подопытные:
(defun rdc (x)
  (if (> (length x) 1)
    (cons (car x) (rdc (cdr x))) ))
	
(defun rrev (x)
  (if (null (cdr x)) x
    (cons (last x) (rrev (rdc x))) ))
я лишь позволил себе изменить оригинальное имя, так как на тот момент у меня уже был один вариант с таким же. Для того чтобы проследить влияние length на быстродействие несколько модифицируем функцию rdc:
(defun rdc1 (x)
  (if (cdr x)
    (cons (car x) (rdc1 (cdr x))) ))

(defun rrev1 (x)	
  (if (cdr x)
    (cons (last x) (rrev1 (rdc1 x)))
    x ))	
rrev1 отличается от rrev, по сути, лишь тем, что использует модифицированную rdc1, измененный порядок ветвей значения практически не оказывает. Легко убедиться, что функциональность двух вариантов rdc полностью идентична. Теперь приступим к тестам:
(setq L1k   () i 0)(repeat 1000   (setq L1k   (cons i L1k)   i (1+ i)))
(setq L10k  () i 0)(repeat 10000  (setq L10k  (cons i L10k)  i (1+ i)))
(setq L100k () i 0)(repeat 100000 (setq L100k (cons i L100k) i (1+ i)))
(setq L1m   () i 0)(repeat 1000000(setq L1m   (cons i L1m)   i (1+ i)))
это списки с которыми мы будем работать - более короткие не представляют особого интереса из-за сложностей измерения скорости обработки.
_$ (evaltime '(rrev l1k))
Время выполнения  19.39  секунд
_$ (gc)
nil
_$ (evaltime '(rrev l1k))
Время выполнения  19.44  секунд
_$ (gc)
nil
_$ (evaltime '(rrev l1k))
Время выполнения  19.33  секунд
для уменьшения влияния на скорость "сборки мусора" во время исполнения, я выполнял ее перед каждым очередным запуском (как можно видеть на этом примере), в дальнейшем я буду опускать эти фрагменты в целях экономии места.
Как видим, список из 1000 элементов функция обращала немногим более 19 секунд. (Эти замеры я проводил на своем довольно древнем домашнем ПК на базе Sis620+Celeron400+256Mb RAM). Сложно сказать хорошо это или плохо не имея других результатов. Но пока нас вполне устроит и относительная картина (пожалуй, так даже пока что лучше). Посмотрим так ли уж не значительно влияние length:
_$ (evaltime '(rrev1 l1k))
Время выполнения  5.93  секунд
_$ (evaltime '(rrev1 l1k))
Время выполнения  5.93  секунд
_$ (evaltime '(rrev1 l1k))
Время выполнения  5.93  секунд
Ускорение более чем в 3 (!!!) раза едва ли можно назвать "незначительным", особенно, учитывая особенности именно этой функции. Но это влияние, так сказать, на конечный результат, а насколько ускорилась непосредственно rdc1?
_$ (evaltime '(rdc l1k))
Время выполнения  0.06  секунд
_$ (evaltime '(rdc1 l1k))
Время выполнения  0  секунд
похоже, для нормального сравнения необходимо взять список подлиннее... попутно отметим для себя, что вспомогательная функция довольно проворна на фоне главной (вообще-то это вполне нормально, но отметим разницу)
_$ (evaltime '(rdc l10k))
Время выполнения  5.16  секунд
_$ (evaltime '(rdc l10k))
Время выполнения  5.22  секунд
_$ (evaltime '(rdc l10k))
Время выполнения  5.22  секунд

_$ (evaltime '(rdc1 l10k))
Время выполнения  0.11  секунд
_$ (evaltime '(rdc1 l10k))
Время выполнения  0.16  секунд
_$ (evaltime '(rdc1 l10k))
Время выполнения  0.11  секунд
здесь, как видим, разница уже в десятки (!!!) раз, утверждение о том, что якобы "производительность last не намного ниже, чем car, а даже дополнительный вызов length даёт весьма незначительный эффект", как бы это выразится помягче, "не совсем соответствует действительности". Приводимый casual goer, якобы в качестве доказательства своих слов, пример мы еще разберем...
а ведь это был даже не дополнительный вызов, а просто не оправданный - мы ведь полностью сохранили функциональность. Ну а для тех, кто не привык думать о том "что, как устроено" есть повод серьезно задуматься - оказывается "Не все функции одинаково полезны (быстры)"
К сожалению, я не смог найти способ также заменить last на что-то более быстрое (с сохранением функциональности). Придется немного погрешить против истины и предположить что такая функция есть и называется она... ну, скажем car:
(defun rrev2 (x)
  (if (null (cdr x)) x
    (cons (car x) (rrev2 (rdc1 x))) ))
конечно, результат работы нашей новой функции совершенно не то что нам необходимо, зато мы можем исследовать влияние на скорость...
_$ (evaltime '(rrev2 l1k))
Время выполнения  5.88  секунд
_$ (evaltime '(rrev2 l1k))
Время выполнения  5.88  секунд
_$ (evaltime '(rrev2 l1k))
Время выполнения  5.87  секунд
Всего-навсего 1% после того, как мы уже начали было привыкать к разнице в сотни и даже тысячи процентов. Результат может показаться кому-то неожиданным. Может быть и в самом деле "производительность last не намного ниже, чем car..."? Но ведь логика подсказывает, что такого просто не может быть. Список это такая структура, в которой, чтобы найти любой ее элемент, необходимо двигаться последовательно по списку начиная с его головы, нет ни какой возможности "перепрыгнуть" через один, десять или сразу на нужный. Необходимо последовательно (с помощью цикла или рекурсии, здесь суть важно) путем cdr приближаться к искомому элементу. При этом, число этих шагов равно длине списка. Функции car и cdr - близнецы, их быстродействие ни при каких условиях не может заметно отличаться. А следовательно, доступ к 5-ому элементу должен быть (грубо говоря) в 20 раз более быстрым чем к 100-му, ну а к первому в n раз быстрее чем к последнему (где n, разумеется, длина списка). Разумеется, такая оценка весьма приблизительна. Особенно для малых n, т.к. для них время вызова функции и связанных с этим различных накладных расходов может очень сильно сгладить это различие. Однако, чем больше n - тем ближе зависимость к линейной, тут уж ничто не в силах этого изменить:
_$ (evaltime '(repeat 10 (last l100k)))
Время выполнения  0.22  секунд
_$ (evaltime '(repeat 10 (last l1m)))
Время выполнения  1.92  секунд
некоторую нелинейность спишем на погрешности метода измерения, тем более, что в этом случае они довольно значительны... Думаю нет необходимости объяснять что для car нет разницы какой длины список - замерить быстродействие этой функции, с более-менее достоверной точностью, я просто не могу... Но то что она быстрее чем last в число раз пропорциональное n у меня не вызывает сомнения... Между прочим, аналогичные построения справедливы и для некоторых других функций Лиспа: length, nth, append, reverse, remove, member (для последней, правда, необходимо еще учитывать и то где именно расположен искомый элемент - он ведь может быть и первым, и последним). А (last x), вообще говоря, является ни чем иным как (car (reverse x)), по крайней мере, с точки зрения многих программистов...
В чем же тогда причина столь незначительной разницы между rrev1 и rrev2?

сам автор кода сформулировал ответ следующим образом: "откуда же тогда такие отвратительные результаты rdc+rev. элементарно, но отвечать напрямую не буду - лучше задам вопрос подсказку: чего у rdc+rev в 100 раз больше уже при списке из 200 элементов, по сравнению с REVERSE3 (и большинством других вариантов), при 1000 элементов в 500 раз, при 5000 в 2500 раз, ну и так далее? при 10000 уже в 5000 раз... причём, это абсолютно очевидно."
 

(defun REVERSE3 (l)
  (if (not (atom l))
    (append (REVERSE3 (cdr l)) (list (car l))) ))
Не знаю как кому, но мне лично, "подсказки" помогли мало. Все мои гипотезы не выдерживали проверки - я не смог определить что описывал автор именно такими цифрами. Первая мысль была что автор имел в виду общее число вызовов этих функций - но я быстро прогнал от себя эту мысль - не мог автор так ошибиться даже первая беглая оценка подтверждала что рост общего числа вызовов пару указанных функций идет несравненно быстрее. В конце концов, уже не веря своей интуиции, я решил проверить все более тщательно.
(defun rdcc (x)
  (setq $i (1+ $i))
  (if (> (length x) 1)
    (cons (car x) (rdcc (cdr x))) ))

(defun rrevc (x)
  (setq $$i (1+ $$i))
  (if (null (cdr x)) x
    (cons (last x) (rrevc (rdcc x))) ))

(defun $$rev (x / $i $$i)
  (setq $i 0 $$i 0)
  (rrevc x)
  (print $i)
  (print $$i)
  (princ)
)  
а теперь попробуем найти зависимость общего числа вызовов от от числа элементов:
_$ ($$rev '(1 2 3))
5 
3 
_$ ($$rev '(1 2 3 4))
9 
4 
_$ ($$rev '(1 2 3 4 5))
14 
5 
со второй цифрой (число вызовов rrevc) все ясно, как и должно было быть, он просто равна числу элементов списка, найти зависимость для первого числа (вызовы rdcc) было несколько сложнее. Вспомнить сходу я не смог чему имеено должно быть равно число вызов внутреннего цикла. Подходить строго математически, если честно, было лень и я решил просто "проинтуитить" эту зависимость. Очень помог случай, а точнее, то какие именно списки я выбирал (совершенно не осознано) в качестве аргумента - мне вдруг показалось что данное число как-то связано с суммой передаваемого списка как ряда - ну да, так и есть, только без единицы. Таким образом, число вызовов внутренней функции rdcc растет гораздо быстрее с ростом числа элементов списка и составляет сумму от 2 до n. Для списка из 200 элементов мы получим:
_$ ($$rev l200)
20099 
200 
_$ 
20099 - никак не 100! Что же имел в виду уважаемый casual goer? REVERSE3 - функция сугубо линейная. Не по скорости работы конечно, с этим у нее большие проблемы того же характера что и в рассматриваемом случае, но к этому мы еще вернемся. Она линейна в том смысле, что число ее рекурсивных вызовов (а следовательно и каждой из ее составляющих) линейным образом зависит от размера обрабатываемого списка. Так что подсказка оказалась похлеще самого вопроса (по крайней мере для меня). Не подумайте что я лукавлю, но если кто-то понимает что имел ввиду casual goer не поленитесь и сообщите мне - вполне возможно что я и в самом деле чего-то не заметил...


Уже после публикации этой страницы casual goer все же указал мне то, что теперь, и в самом деле, достаточно очевидно. Не знаю как, но я не заметил того факта, что (20099+200)/200 и есть 100 (приблизительно, разумеется). В самом деле, n2/2*n как раз и дает ту самую закономерность, которую указывал casual goer. Тем не менее я решил не выбрасывать предыдущий фрагмент, от части, как напоминание самому себе...

После этого небольшого отвлечения, которое, для меня лично, ничего особенно не добавило к пониманию проблемы, приходится вновь возвращаться к анализу кода. В подавляющем большинстве случаев причиной плохого быстродействия являются вложенные циклы в той или иной форме (естественно под это определение вполне подходит и вложенная рекурсия). И, как правило, оптимизацию стоит начинать с самого вложенного цикла. Истина почти непреложная, но, как мы увидим, исключения все же встречаются. Хотя, по первым шагам модификации наших подопытных функций, вроде бы, даже есть подтверждения - в самом деле убрав цикл 3-ого уровня (cdr вместо length) мы получили несравненно больший эффект нежели заменой цикла 2-ого уровня last на car. Однако теперь, похоже, пришло время остановиться и на еще на одном цикле 2-ого уровня, а именно, на функции rdc. Мы сумели ускорить ее весьма существенно, но это оказало не такое существенное влияние на общую скорость работы, как можно было бы ожидать. Очевидно, есть что-то, что вносит куда более серьезный вклад в быстродействие. Но что? Для ответа на данный вопрос необходимо рассмотреть чуточку более внимательно функцию rrev1 (или если угодно rrev).

(defun rrev3 (x)
  (if (cdr x)
    (cons (car x) (rrev3 (cdr x)))	; заменили "обратный cdr" - rdc на cdr
    x ))
	
(defun rdc2 (x) (cdr x))
(defun rrev4 (x)
  (if (cdr x)
    (cons (car x) (rrev4 (rdc2 x)))	; тоже, но через промежуточною функцию
    x ))	
(defun rrev03 (x)
  (if (cdr x)
    (cons (last x) (rrev03 (cdr x)))	; вернули last 
    x ))
понятно что обе функции выдают совершенно не тот результат который необходимо (так rrev3 просто копирует исходный список, а rrev03заменяет все элементы списка последним), но для нас важно что порядок работы сохраняется. Что же мы увидим для наших новых функций:
_$ (evaltime '(rrev3 l10k))
Время выполнения  0.11  секунд
_$ (evaltime '(rrev3 l10k))
Время выполнения  0.11  секунд
_$ (evaltime '(rrev3 l10k))
Время выполнения  0.11  секунд

_$ (evaltime '(rrev4 l10k))
Время выполнения  0.16  секунд
_$ (evaltime '(rrev4 l10k))
Время выполнения  0.11  секунд
_$ (evaltime '(rrev4 l10k))
Время выполнения  0.17  секунд
_$ (evaltime '(rrev4 l10k))
при таких разбросах сложновато судить о результатах, поэтому несколько изменим условия:
_$ (evaltime '(repeat 20 (rrev3 l10k)))
Время выполнения  2.53  секунд
_$ (evaltime '(repeat 20 (rrev3 l10k)))
Время выполнения  2.53  секунд
_$ (evaltime '(repeat 20 (rrev3 l10k)))
Время выполнения  2.53  секунд

_$ (evaltime '(repeat 20 (rrev4 l10k)))
Время выполнения  3.24  секунд
_$ (evaltime '(repeat 20 (rrev4 l10k)))
Время выполнения  3.24  секунд
_$ (evaltime '(repeat 20 (rrev4 l10k)))
Время выполнения  3.24  секунд
Черт побери! Дороговато обходится лишний вызов функции, нечего сказать. Что-то мне подсказывает что компиляция способна существенно исправить ситуацию, но это исследование еще впереди... Любопытно, а как теперь себя проявит last, в отсутствии более мощных "тормозов"
(defun rrev03 (x)
  (if (cdr x)
    (cons (last x) (rrev03 (cdr x)))	; вернули last 
    x ))

_$ (evaltime '(rrev03 l10k))
Время выполнения  7.14  секунд
_$ (evaltime '(rrev03 l10k))
Время выполнения  7.2  секунд
_$ (evaltime '(rrev03 l10k))
Время выполнения  7.14  секунд
Кто-то, кажется, утверждал что нет большой разницы между last и car? Лично для меня такая разница кажется более чем достаточной... Это уже больше похоже на то к чему мы привыкли и чего ожидали, попутно обратите внимание на результаты rrev3 в сравнении с rrev2 - ускорение того же порядка между прочим (!!!). Можно было бы сделать вывод что виновата "плохая" rdc1 (про "совсем плохую" rdc мы сейчас не будем вспоминать). Попробуем ее заменить на "хорошую". Забудем про исходные условия и...
(defun rdc3 (x) (cdr (reverse x)))

(defun rrev5 (x)
  (if (cdr x)
    (cons (car x) (rrev5 (rdc3 x)))
    x ))

(defun rrev05 (x)
  (if (cdr x)
    (cons (last x) (rrev05 (rdc3 x)))
    x))
Ни у кого, думаю, не возникнет сомнения что rdc3 по сравнению даже с rdc1 "очень хорошая" - еще бы встроенная функция против рекурсивной пользовательской. Проведем замеры:
Время выполнения  0.22  секунд
_$ (evaltime '(rrev05 l1k))
Время выполнения  0.22  секунд
_$ (evaltime '(rrev05 l1k))
Время выполнения  0.22  секунд

_$ (evaltime '(rrev5 l1k))
Время выполнения  0.17  секунд
_$ (evaltime '(rrev5 l1k))
Время выполнения  0.17  секунд
_$ (evaltime '(rrev5 l1k))
Время выполнения  0.16  секунд
Оба варианта довольно неплохо ускорились, но только не по сравнению с rrev3!!! Если кто не обратил внимания, для того варианта использовался список в 10 раз более длинный! Как бы ни "хороша" была встроенная версия reverse, ей никак не под силу тягаться с базовой cdr! И снова приходится констатировать, что "встроенная" функция далеко не тоже что "базовая". Тем более когда вызывается в теле цикла (или, что тоже самое, в рекурсивной функции). Но сравним теперь rrev5 и rrev05 - разница уже около 30%! Помните, в аналогичных условиях разница между rrev1 и rrev2 составила порядка 1%? Чем быстрее остальные части функции, тем более негативное влияние оказывает last. А вот влияние "лишней" промежуточной функции, как в случае rrev3 и rrev4 здесь уже совершенно не велико, желающие могут убедиться в этом сами. Таким образом, любой, я настаиваю - любой, цикл (какова бы ни была его природа - будь то предопределенная функция для данного интерпретатора, то ли определенная пользователем) в цикле оказывает заметное влияние на снижение общей производительности. Безусловно, чем медленнее внутренний цикл - тем заметнее падение общей производительности. Разумеется, может вполне оказаться, что кто-то портит производительность еще сильнее и даже "маскирует" эффект этого цикла - но тогда мы просто имеем дело не с одной проблемой, а с несколькими.

Собственно, на этом можно было бы и закончить. Ни каких выводов пока делать не стану, пусть читатель делает их сам... Если кто-то подумал что я забыл про некоторые свои обещания - не беспокойтесь... У меня теперь есть столько разных вариантов reverse, что пройти мимо я просто не мог. Так что "to be continued..."