Mathematica „Listy” połączone i wydajność

Question

W Mathematica, tworzę pojedynczo związane listy tak:

toLinkedList[x_List] := Fold[pair[#2, #1] &, pair[], Reverse[x]]; 

fromLinkedList[ll_pair] := List @@ Flatten[ll]; 

emptyQ[pair[]] := True; 
emptyQ[_pair] := False;  

Używanie symbolu pair dla komórek minusy ma tę zaletę Flatten pracuje bezpiecznie nawet jeżeli wykazy zawierają Mathematica- style List s, i pozwala zdefiniować niestandardową notację za pomocą MakeExpression/MakeBoxes, co czyni wszystko znacznie przyjemniejszym. W celu uniknięcia konieczności wymieszania się z $IterationLimit, napisałem funkcje do pracy z tymi listami za pomocą pętli While lub NestWhile zamiast rekursji. Oczywiście, chciałem zobaczyć, które podejście byłoby szybciej, więc napisałem dwóch kandydatów, więc mogłem oglądać „em walczyć:

nestLength[ll_pair] := 
With[{step = {#[[1, -1]], #[[-1]] + 1} &}, 
    Last@NestWhile[step, {ll, 0}, ! emptyQ@First@# &]]; 

whileLength[ll_pair] := 
Module[{result = 0, current = ll}, 
    While[! emptyQ@current, 
    current = current[[2]]; 
    ++result]; 
    result]; 

Wyniki były bardzo dziwne. Testowałem funkcje na połączonych listach o długości 10000, a whileLength było zazwyczaj o około 50% szybsze, o około 0,035 sekundy do 0,055 sekundy, czyli nestLength. Jednak czasami whileLength zajęłoby około ~ 4 sekund. Pomyślałem, że może wystąpić pewne zachowanie związane z buforowaniem, więc zacząłem generować świeże, losowe listy do sprawdzenia, a whileLength niekoniecznie będzie wolne przy pierwszym uruchomieniu z nową listą; może to zająć kilkadziesiąt razy, aby zobaczyć spowolnienie, ale potem nie powtórzyłoby się (przynajmniej nie dla 200 przebiegów próbowałem z każdą listą).

Co może się dziać?

Dla porównania, funkcja I wykorzystywane do testowania to:

getTimes[f_, n_] := 
With[{ll = toLinkedList@RandomInteger[100, 10000]}, 
    Table[Timing[f@ll], {n}][[All, 1]]] 

EDIT: I zapomniał wspomnieć wersję wcześniej; Mam te wyniki z Mathematica 8.

edytować drugiego: Kiedy czytam Daniel Lichtblau's answer, zdałem sobie sprawę, że moje czasy dla „typowych” przebiegów pominięte wiodącą 0. Jest został naprawiony.

EDYTUJ trzecią: Myślę, że Leonid Shifrin jest poprawna, aby skojarzyć problem z Module; Mogę dostać ten sam rodzaj zachowania z NestWhile wersji opartym zastępując With z Module:

nestModuleLength[ll_pair] := 
    Module[{step = {#[[1, -1]], #[[-1]] + 1} &}, 
    Last@NestWhile[step, {ll, 0}, ! emptyQ@First@# &]]; 

In[15]:= Select[getTimes[nestModuleLength, 100], # > 3 &] 
Out[15]= {3.797} 

Answer 1

Poniższe przykłady dają typowe wyniki.

Jeden powolny przykład w przebiegu o długości 20.

In[18]:= getTimes[whileLength, 20] 

Out[18]= {0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, \ 
0.031, 0.047, 0.032, 0.031, 0.031, 3.547, 0.047, 0.031, 0.031, 0.032, \ 
0.031, 0.031} 

Zauważam, że czasy są ~ 10x szybsze niż w oryginalnym poście, z wyjątkiem powolnych przypadków, które są porównywalne. Nie jestem pewien, co wyjaśnia tę różnicę w stosunkach.

Bez powolnych przykładów.

In[17]:= getTimes[nestLength, 20] 

Out[17]= {0.047, 0.047, 0.062, 0.047, 0.047, 0.062, 0.047, 0.047, \ 
0.047, 0.063, 0.046, 0.047, 0.047, 0.063, 0.047, 0.046, 0.047, 0.063, \ 
0.047, 0.047} 

Jeden powolny przykład na 100 długości.

In[19]:= getTimes[whileLength, 100] 

Out[19]= {0.031, 0.031, 0.031, 0.032, 0.031, 3.594, 0.047, 0.031, \ 
0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.047, 0.031, \ 
0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.047, 0.031, 0.031, \ 
0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, \ 
0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, \ 
0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, 0.031, \ 
0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.047, 0.031, 0.031, 0.032, \ 
0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.046, 0.032, \ 
0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, 0.032, 0.031, \ 
0.031, 0.031, 0.032, 0.031, 0.047, 0.031, 0.031, 0.031, 0.032, 0.031, \ 
0.031, 0.031} 

Mathematica narzędzia, niedoskonały, co nazywane jest "nieskończony ewaluacja". Oznacza to, że wyrażenie ponownie się sprawdza, dopóki nie przestaje się zmieniać. Aby zrobić to w miarę szybko, istnieją różne optymalizacje, które w miarę możliwości próbują zwierać ten proces.

W niektórych przypadkach może to być trudne do rozpoznania (ze względu na efekt podobny do mieszania haszu), a wyrażenia mogą być niepotrzebnie przewartościowane. Głęboko zagnieżdżone wyrażenia są najgorszym przypadkiem. Mamy dodatkowy kod, który często odnosi się do nich nawet w przypadku kolizji.

Winowajcą w tym przypadku jest właśnie ten kod, który próbuje szybko określić, czy wyrażenie wymaga ponownej oceny. Jest to osobliwe, ale prawdopodobnie wskazówka (dla kogoś), że dzieje się to najwyżej raz w biegu wewnątrz pętli While. Więc coś dzieje się w złych przypadkach, które zapobiegają nawrotom w tym samym czasie.

Kiedyś znałem kod wykrywania reewaluacji, po napisaniu kawałka tego. Ale został przepisany na wersję 8. Tak więc nawet po zobaczeniu tego suboptymalnego zachowania w debugerze, jest to dla mnie coś tajemniczego. W tej chwili mogę powiedzieć, że złożyłem raport o błędzie.

Jak zauważył Leonid Shifrin, symbole z atrybutem HoldAllComplete są odporne na ten problem. Używanie tego atrybutu może być korzystne dla tego typu kodu.

Daniel Lichtblau Wolfram Research

Answer 2

Wygląda to związane z modułem symboli lokalnych zarządzania pamięcią.

Pokażę serie czasowe z niektórych serii. Każdy bieg daje oczywiście wyjątkową fabułę, ale sprawdziłem "zgodność" pomiędzy biegami.Spójrz:

whileLength[l2_pair] := 
    Module[{result = 0}, current = l2; 
    While[! emptyQ@current, current = current[[2]]; 
    ++result]; 
    result]; 

wydaje następujący szereg czasowy:

Podczas korzystania tylko symbole globalne:

whileLength[l2_pair] := 
    Module[{}, result = 0; current = l2; 
    While[! emptyQ@current, current = current[[2]]; 
    ++result]; 
    result]; 

otrzymujemy:

Answer 3

Zrzeczenie się odpowiedzialności: poniższe spekulacje. Wydaje się, że jest to związane z poszukiwaniem UpValues. Wygląda na to, że został zoptymalizowany pod kątem zmiennych globalnych (tak, że system pomija ten krok, gdy może określić, że może to zrobić), ale nie dla Module - generowanych zmiennych lokalnych. Aby to sprawdzić, należy przypisać atrybut HoldAllComplete do pair, a znika efekt (od tego czasu, UpValues nie są sprawdzane pod kątem current):

SetAttributes[pair, HoldAllComplete]; 

In[17]:= ll = toLinkedList@RandomInteger[100, 10000]; 
Max[Table[Timing[whileLength[ll]], {1000}][[All, 1]]] 

Out[18]= 0.047 

HTH