Efektywna funkcja zbierania w Common Lisp

Question

Uczę się Lispa i napisałem następującą funkcję, aby zebrać listę wyników.

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

Produkuje podobne wyjście do wbudowanej funkcji pętli.

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) 

Jednak moja zbierać funkcja wieje stos gdy próbuję wygenerować listę 100,000 elementy długie

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

Podczas gdy wersja pętla nie

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

Jak mogę uczynić mój wersja bardziej wydajna pod względem przestrzeni kosmicznej, czy istnieją alternatywy dla consing? Myślę, że to rekurencyjny ogon. Używam sbcl. Każda pomoc byłaby świetna.

Answer 1

Typowe implementacje Lispa nie są wymagane przez standard ANSI do optymalizacji połączeń ogniskowych; jednak większość wartych swojej soli (w tym SBCL) optymalizuje się.

Z drugiej strony Twoja funkcja nie jest rekursywna.Może on być przekształcony jeden za pomocą wspólnego trick wprowadzenie dodatkowego parametru do gromadzenia wynik pośredni:

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

(Oryginalny parametry funkcjonowaniu i ARG usuwa się w funkcji lokalnych, gdyż są one stałe z recpect do niego).

Answer 2

Cóż, alternatywą dla rekurencji jest iteracja.

Powinieneś wiedzieć, że Common Lisp nie wymaga rekursji ogonowej od swoich implementatorów, w przeciwieństwie do Planu.

(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 

Answer 3

Nie, to nie jest rekursywny ogon. Ani ANSI Common Lisp mówi nic o niej ani kodzie:

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

Jeśli spojrzeć na kod, jest CONS wokół rozmowy zbierać. Ten CONS odbiera wartość rekurencyjnego wywołania COLLECT. Więc COLLECT nie może być rekursywny. Względnie proste jest przepisanie funkcji na coś, co wygląda na rekursywne, wprowadzając zmienną akumulatora. Różne literatury Lisp lub Scheme powinny to opisać.

W Common Lisp domyślny sposób zaprogramować iteracyjny obliczeń jest za pomocą jednego z kilku iteracyjnych konstruktów: Nie, DOTIMES, dolist, LOOP, MAP, mapcar ...

Common Lisp nie zapewnia optymalizację połączeń końcowych (TCO). Trzeba będzie określić, co TCO powinien zrobić w obecności kilku innych funkcji językowych. Na przykład dynamiczne wiązanie i zmienne specjalne mają wpływ na TCO. Jednak standard Common Lisp nie mówi po prostu nic o TCO w ogóle i o możliwych skutkach TCO. TCO nie jest częścią standardu ANSI Common Lisp.

Kilka implementacji Common Lisp umożliwia optymalizację różnych wywołań połączeń z przełącznikami kompilatora. Zauważ, że zarówno sposób, w jaki można je włączyć, jak i ograniczenia, zależy od implementacji.

Podsumowanie: W Common Lisp stosuj konstrukcje iteracyjne, a nie rekurencję.

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

Dodatkowy bonus: łatwiej jest go przeczytać.