數學「鏈表」和性能

Question

在數學，我創建單鏈表，像這樣：

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

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

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

使用符號pair的利弊細胞具有Flatten安全工作，即使列表包含Mathematica-優勢style List s，並且允許您使用MakeExpression/MakeBoxes來定義自定義符號，這使得一切都變得更加愉快。爲了避免與$IterationLimit混淆，我編寫了使用While循環或NestWhile而不是遞歸使用這些列表的函數。當然，我想看看哪種方法會更快，所以我寫了兩個候選人，所以我能看到「時間打：

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]; 

結果非常奇怪。我測試了長度爲10000的鏈表上的函數，並且whileLength通常快了大約50％，在大約0.035秒到nestLength的0.055秒處。但是，偶爾whileLength需要約4秒。我認爲可能存在一些緩存行爲，所以我開始生成新的隨機列表來檢查，並且whileLength在第一次運行時不一定會很慢，並且具有新的列表;它可能需要幾十次才能看到放緩，但不會再發生（至少不是我試圖用每個列表進行的200次）。

可能會發生什麼？

僅供參考，我用於測試的功能是這樣的：

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

編輯：我忘了前面提到的版本;我得到這些結果與數學8.

編輯第二：當我讀到Daniel Lichtblau's answer，我意識到，我的時間「典型」運行省略了領先的0它已經固定。

編輯第三個：我認爲Leonid Shifrin是正確的關聯問題與Module;我可以用Module更換With得到相同的排序從NestWhile基於版本的行爲：

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

的例子給出了典型的結果。

長度爲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} 

我順便指出，而定時爲10倍〜比在原崗位快，除了速度慢的情況具有可比性。不確定什麼說明了這種差異。

沒有緩慢的例子。

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} 

長度爲100的一個緩慢示例。

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不完美地實現了所謂的「無限評估」。也就是說，表達式會重新評估直到它停止改變。爲了使這個過程合理快速，有各種優化嘗試儘可能短路過程。

在某些情況下，可能很難辨別（由於與散列衝突類似的效果），並且可能不必要地重新評估表達式。深度嵌套的表達式往往是最糟糕的情況。我們還有更多的代碼，即使在發生碰撞的情況下也可以解決這些問題。

在這個例子中的罪魁禍首正是這個代碼，試圖迅速確定表達式是否需要重新評估。這是特殊的，但可能是一個線索（對某人），在While循環內最多發生一次這種情況。因此，在壞情況下發生的事情可以防止在同一時間內再次發生。

有一段時間我很熟悉重新評估檢測代碼，寫了一大塊。但是它被重寫爲版本8.所以即使在調試器中看到這種不理想的行爲，這對我來說也是一個謎。關於我現在可以說的一切，就是我提交了一個錯誤報告。

正如Leonid Shifrin所觀察到的，具有HoldAllComplete屬性的符號不受此問題影響。所以使用這個屬性對於這種類型的代碼可能是有益的。

丹尼爾Lichtblau 沃爾夫勒姆研究

Answer 2

好像它關係到模塊局部符號內存管理。

我會顯示一些運行的時序系列。每次運行當然會給出一個獨特的繪圖，但我在運行中檢查了「一致性」。看：

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

給出以下計時系列：

，而只使用全局符號：

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

給出：

Answer 3

A免責聲明：以下是推測。這似乎與搜索UpValues有關。看起來這已經針對全局變量進行了優化（以便系統可以在確定可以執行此操作時跳過此步驟），但不會生成局部變量Module。爲了測試這一點，分配HoldAllComplete屬性pair，效果消失（從此，UpValues不檢查用於current）：

SetAttributes[pair, HoldAllComplete]; 

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

Out[18]= 0.047 

HTH下面