SBCL działa zawsze na drugim wywołaniu funkcji

Question

funkcję:

Biorąc pod uwagę powrót lista LST wszystkie permutacje listy za treść dokładnie długości k, które domyślnie długość listy, jeśli nie są uregulowane.

(defun permute (lst &optional (k (length lst))) 
    (if (= k 1) 
    (mapcar #'list lst) 
    (loop for item in lst nconcing 
    (mapcar (lambda (x) (cons item x)) 
      (permute (remove-if (lambda (x) (eq x item)) lst) 
         (1- k)))))) 

problem: Używam szlam w emacs podłączonych do SBCL, nie robiłem jeszcze zbyt wiele personalizacji. Funkcja działa dobrze na mniejszych wejściach, takich jak lst = '(1 2 3 4 5 6 7 8) k = 3, co jest najczęściej używane w praktyce. Jednak, gdy wywołuję go z dużym wejściem dwa razy z rzędu, drugie połączenie nigdy nie wraca, a sbcl nawet nie pojawia się na górze. Są to wyniki REPL:

CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9)))) 
Evaluation took: 
12.263 seconds of real time 
12.166150 seconds of total run time (10.705372 user, 1.460778 system) 
[ Run times consist of 9.331 seconds GC time, and 2.836 seconds non-GC time. ] 
99.21% CPU 
27,105,349,193 processor cycles 
930,080,016 bytes consed 

(2 7 8 3 9 1 5 4 6 0) 
CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9)))) 

I nigdy nie wraca z drugiego połączenia. Mogę się tylko domyślać, że z jakiegoś powodu robię coś okropnego śmieciarzowi, ale nie widzę co. Czy ktoś ma jakieś pomysły?

Answer 1

Jedną z rzeczy, która jest nieprawidłowa w twoim kodzie, jest użycie EQ. EQ porównuje dla tożsamości.

EQ nie służy do porównywania liczb. EQ dwóch liczb może być prawdziwe lub fałszywe.

Użyj EQL, jeśli chcesz porównać według tożsamości, liczb według wartości lub znaków. Nie EQ.

Właściwie

(remove-if (lambda (x) (eql x item)) list) 

tylko

(remove item list) 

Dla kodzie Bugu EQ MOŻE oznacza, że ​​permute jest wywoływana w rekurencyjnego wywołania bez faktycznie wielu usunięty z listy.

Poza tym, myślę, że SBCL jest po prostu zajęty zarządzaniem pamięcią. SBCL na moim Macu uzyskał dużo pamięci (więcej niż GB) i był zajęty robieniem czegoś. Po pewnym czasie obliczono wynik.

Funkcja rekursywna generuje ogromną ilość "śmieci". LispWorks mówi: 1360950192 bajtów

Może uda się uzyskać bardziej wydajną implementację?

Aktualizacja: śmieci

Lisp zapewnia pewne automatyczne zarządzanie pamięcią, ale to nie zwalnia programistę od myślenia o efektach kosmicznych.

Lisp używa zarówno stosu, jak i sterty do przydzielenia pamięci. Sterty mogą być zbudowane w określony sposób dla GC - na przykład w generacjach, w połowie pól i/lub obszarów. Istnieją precyzyjne odśmiecacze i "konserwatywne" śmieciarki (używane przez SBCL na maszynach Intela).

Po uruchomieniu programu możemy zobaczyć różne efekty:

1. normalne procedury rekurencyjne przydzielić miejsca na stosie. Problem: rozmiar stosu jest zazwyczaj ustalony (nawet jeśli niektóre Lisps mogą go zwiększyć w procedurze obsługi błędów).

2. program może przydzielić ogromną ilość pamięci i zwrócić duży wynik. PERMUTE jest taką funkcją. Może zwracać bardzo duże listy.

3. program może przydzielić pamięć i użyć go tymczasowo, a następnie urządzenie do zbierania śmieci może je oddać do recyklingu. Tempo tworzenia i niszczenia może być bardzo wysokie, nawet jeśli program nie używa dużej ilości pamięci stałej.

Jest jednak więcej problemów. Ale dla każdego z powyższych programista Lisp (i każdy inny programista używający implementacji językowej ze zbieraniem śmieci) musi się nauczyć, jak sobie z tym poradzić.

1. Wymień rekursję na iterację. Zastąp rekursję rekurencją ogona.

2. Zwraca tylko tę część wyniku, która jest potrzebna i nie generuje pełnego rozwiązania. Jeśli potrzebujesz n-tej permutacji, obliczyć to, a nie wszystkie permutacje. Użyj leniwych struktur danych obliczanych na żądanie. Użyj czegoś takiego jak SERIA, co pozwala na użycie strumienia, ale wydajne obliczenia. Zobacz SICP, PAIP i inne zaawansowane książki Lisp.

3. Ponownie wykorzystaj pamięć przy użyciu menedżera zasobów. Ponownie używaj buforów zamiast alokować obiekty przez cały czas. Użyj wydajnego garbage collectora ze specjalnym wsparciem do zbierania efemerycznych (krótkotrwałych) obiektów. Czasami może to również pomóc w destruktywnej modyfikacji obiektów, zamiast przydzielać nowe obiekty.

Powyżej zajmuje się problemami przestrzeni rzeczywistych programów. Idealnie nasze kompilatory lub infrastruktura środowiska wykonawczego mogą zapewniać automatyczne wsparcie w celu rozwiązania tych problemów. Ale w rzeczywistości tak naprawdę nie działa. Większość systemów Lisp zapewnia niskopoziomową funkcjonalność, aby sobie z tym poradzić, a Lisp udostępnia zmienne obiekty - ponieważ doświadczenie z rzeczywistych programów Lisp pokazało, że programiści chcą z nich korzystać w celu optymalizacji swoich programów. Jeśli masz dużą aplikację CAD, która oblicza kształt łopatek turbiny, wtedy teoretyczne/purystyczne widoki dotyczące pamięci niezmiennej po prostu nie mają zastosowania - programista potrzebuje szybszego/mniejszego kodu i mniejszego śladu środowiska wykonawczego.

Answer 2

Z wyglądu wydruku, patrzysz na replikę śluzu, prawda?

Spróbuj przejść do bufora "* gorszej selekcji *", prawdopodobnie zobaczysz, że SBCL spadł do ldb (wbudowany debugger niskiego poziomu). Najprawdopodobniej udało ci się zdmuchnąć stos wywołań.

Answer 3

SBCL na większości platform używa sortownika śmieci, co oznacza, że ​​przydzielona pamięć, która przetrwa więcej niż pewna liczba zbiorów, będzie rzadziej brana pod uwagę przy gromadzeniu. Twój algorytm dla danego przypadku testowego generuje tyle śmieci, że uruchamia GC tyle razy, że rzeczywiste wyniki, które oczywiście muszą przetrwać cały czas działania funkcji, są utrzymywane, to jest przeniesione do ostatniej generacji, która jest zbierana bardzo rzadko. albo wcale. Dlatego też, w drugim przypadku, na standardowych ustawieniach dla systemów 32-bitowych, zabraknie sterty (512 MB, można zwiększyć przy pomocy opcji środowiska wykonawczego).

Danymi zebranymi mogą być śmieci zebrane przez ręczne wywołanie kolektora za pomocą (sb-ext:gc :full t). Jest to oczywiście zależne od implementacji.