Эффективная функция сбора в Common Lisp - PullRequest
Новая
       22

Эффективная функция сбора в Common Lisp

5 голосов
/ 19 декабря 2010

Я изучаю Lisp и написал следующую функцию для сбора списка результатов. 

(defun collect (func args num)
  (if (= 0 num)
      ()
      (cons (apply func args)
        (collect func args (- num 1)))))

Она выдала вывод, аналогичный встроенной функции цикла. 

CL-USER> (collect #'random '(5) 10)
(4 0 3 0 1 4 2 1 0 0)
CL-USER> (loop repeat 10 collect (random 5))
(3 3 4 0 3 2 4 0 0 0)

Однако, моя функция сбора ломает стек, когда я пытаюсь сгенерировать список длиной 100 000 элементов 

CL-USER> (length (collect #'random '(5) 100000))
Control stack guard page temporarily disabled: proceed with caution

В то время как версия цикла не 

CL-USER> (length (loop repeat 100000 collect (random 5)))
100000

Как я могу сделать мою версию больше местаэффективны, есть ли альтернативы coning?Я думаю, что хвост рекурсивен.Я использую sbcl.Любая помощь будет великолепна.

Ответы [ 3 ]

11 голосов
/ 19 декабря 2010

Нет, это не хвостовая рекурсия. Ни ANSI Common Lisp ничего не говорит об этом, ни ваш код: 

(defun collect (func args num)
  (if (= 0 num)
      ()
      (cons (apply func args)
            (collect func args (- num 1)))))

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

В Common Lisp стандартным способом программирования итерационных вычислений является использование одной из нескольких итерационных конструкций: DO, DOTIMES, DOLIST, LOOP, MAP, MAPCAR, ...

Стандарт Common Lisp не предусматривает оптимизацию оконечного вызова (TCO). Необходимо указать, что должен делать TCO при наличии нескольких других языковых функций. Например, динамическое связывание и специальные переменные влияют на TCO. Но стандарт Common Lisp просто ничего не говорит о TCO в целом и о возможных последствиях TCO. TCO не является частью стандарта ANSI Common Lisp.

Несколько реализаций Common Lisp имеют способ включить различные оптимизации хвостовых вызовов с помощью переключателей компилятора. Обратите внимание, что как способ их включения, так и ограничения зависят от конкретной реализации.

Резюме : В Common Lisp используйте итерационные конструкции, а не рекурсию. 

(defun collect (func args num)
  (loop repeat num
        collect (apply #'func args)))

Добавлен бонус: его легче читать.

10 голосов
/ 19 декабря 2010

Стандартные реализации Lisp не требуются стандартом ANSI для оптимизации хвостового вызова; тем не менее, большинство того, что стоит их соли (включая SBCL), оптимизируют.

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

    (defun collect (func args num)
      (labels ((frob (n acc)
                 (if (= 0 n)
                     acc
                     (frob (1- n) (cons (apply func args) acc)))))
        (frob num nil)))

(Исходные параметры FUNC и ARGS исключены в локальной функции, поскольку они постоянны по отношению к ней).

1 голос
/ 19 декабря 2010

Ну, альтернатива рекурсии - итерация.

Вы должны знать, что Common Lisp не требует хвостовой рекурсии от своих разработчиков, в отличие от Схема. 

(defun mycollect (func args num)
  (let ((accumulator '()))     ; it's a null list. 
    (loop for i from 1 to num 
      do
      ;;destructively cons up the accumulator with the new result + the old accumulator
      (setf accumulator                   
        (cons (apply func args) accumulator)))
  accumulator))                ; and return the accumulator
...