DeleteDuplicates和Tally中的不穩定

Question

在準備對Count how many different values a list takes in Mathematica的回答時，我發現DeleteDuplicates和Tally中存在不穩定（因爲缺乏更好的術語），我不明白。

首先考慮：

a = {2.2000000000000005, 2.2, 2.1999999999999999}; 

a // InputForm 
DeleteDuplicates@a // InputForm 
Union@a // InputForm 
Tally@a // InputForm 

 {2.2000000000000006`, 2.2, 2.1999999999999997`}

 {2.2000000000000006`, 2.2, 2.1999999999999997`}

 {2.1999999999999997`, 2.2, 2.2000000000000006`}

 {{2.2000000000000006`, 3}}

此行爲是如我所料在每種情況下。 Tally可補償輕微的數字差異，並將每個元素視爲等同。 Union和DeleteDuplicates將所有元素視爲唯一。 （中Tally此行爲未記錄到我的知識，但我之前已經利用它。）

現在，考慮這種併發症：

a = {11/5, 2.2000000000000005, 2.2, 2.1999999999999997}; 

a // InputForm 
DeleteDuplicates@a // InputForm 
Union@a // InputForm 
Tally@a // InputForm 

 {11/5, 2.2000000000000006, 2.2, 2.1999999999999997}

 {11/5, 2.2000000000000006, 2.2}

 {2.1999999999999997, 2.2, 11/5, 2.2000000000000006}

 {{11/5, 1}, {2.2000000000000006, 1}, {2.2, 2}}

Union的輸出與預期相同，但DeleteDuplicates和的結果令人驚訝。

• 爲什麼DeleteDuplicates突然看到2.1999999999999997爲重複被淘汰？

• 爲什麼Tally突然看到2.2000000000000006和2.2是不同的，當它不在之前？

---

作爲相關點，可以看出，堆積陣列影響Tally：

a = {2.2000000000000005, 2.2, 2.1999999999999999}; 
a // InputForm 
Tally@a // InputForm 

 {2.2000000000000006, 2.2, 2.1999999999999997}

 {{2.2000000000000006`, 3}}

a = Developer`ToPackedArray@a; 
a // InputForm 
Tally@a // InputForm 

 {2.2000000000000006, 2.2, 2.1999999999999997}

 {{2.2000000000000006`, 1}, {2.2, 2}}

Answer 1

展現的行爲似乎是由浮點算術相關的常見困境加上一些討論中的某些功能有問題的行爲引起的結果。

SameQ是不等價關係

首先在石板上：認爲SameQ不是等價關係，因爲它是不可傳遞：

In[1]:= $a = {11/5, 2.2000000000000005, 2.2, 2.1999999999999997}; 

In[2]:= SameQ[$a[[2]], $a[[3]]] 
Out[2]= True 

In[3]:= SameQ[$a[[3]], $a[[4]]] 
Out[3]= True 

In[4]:= SameQ[$a[[2]], $a[[4]]] 
Out[4]= False      (* !!! *) 

所以，出了大門，即使在轉向其他職能之前，我們也面臨着不穩定的行爲。

此行爲是由於對SameQ，指出兩個實數被視爲「平等的」，如果他們「在他們的最後二進制數字不同」的記載規則：

In[5]:= {# // InputForm, Short@RealDigits[#, 2][[1, -10;;]]} & /@ $a[[2;;4]] // TableForm 
(* showing only the last ten binary digits for each *) 
Out[5]//TableForm= 2.2000000000000006 {0,1,1,0,0,1,1,0,1,1} 
        2.2     {0,1,1,0,0,1,1,0,1,0} 
        2.1999999999999997 {0,1,1,0,0,1,1,0,0,1} 

需要注意的是，嚴格的說， $a[[3]]和$a[[4]]在最後的兩個不同，但差異的大小是最低的一位。

DeleteDuplicates無法加真的使用SameQ

其次，考慮到文檔指出DeleteDuplicates[...]相當於DeleteDuplicates[..., SameQ]。嗯，這是完全正確 - 但可能不會在這個意義上，你可能期望：

In[6]:= DeleteDuplicates[$a] // InputForm 
Out[6]//InputForm= {11/5, 2.2000000000000006, 2.2} 

In[7]:= DeleteDuplicates[$a, SameQ] // InputForm 
Out[7]//InputForm= {11/5, 2.2000000000000006, 2.2} 

一樣的，記錄在案......但是你看這個：

In[8]:= DeleteDuplicates[$a, SameQ[#1, #2]&] // InputForm 
Out[8]//InputForm= {11/5, 2.2000000000000006, 2.1999999999999997} 

看來，DeleteDuplicates當比較函數明顯是SameQ而不是其行爲與SameQ相同的函數時，會經歷不同的邏輯分支。

Tally是......困惑

Tally顯示類似，但不完全相同的，反常行爲：

In[9]:= Tally[$a] // InputForm 
Out[9]//InputForm= {{11/5, 1}, {2.2000000000000006, 1}, {2.2, 2}} 

In[10]:= Tally[$a, SameQ] // InputForm 
Out[10]//InputForm= {{11/5, 1}, {2.2000000000000006, 1}, {2.2, 2}} 

In[11]:= Tally[$a, SameQ[#1, #2]&] // InputForm 
Out[11]//InputForm= {{11/5, 1}, {2.2000000000000006, 1}, {2.2000000000000006, 2}} 

這最後特別莫名其妙，因爲相同數量的不同計數列表中出現兩次。

平等遭受類似的問題

現在，回到浮點平等的問題。 Equal票價稍好於SameQ - 但強調「小」。 Equal查看最後七位二進制數字而不是最後一位數字。這並不解決問題，但...麻煩的情況下，總是可以找到：

In[12]:= $x1 = 0.19999999999999823; 
     $x2 = 0.2; 
     $x3 = 0.2000000000000018; 

In[15]:= Equal[$x1, $x2] 
Out[15]= True 

In[16]:= Equal[$x2, $x3] 
Out[16]= True 

In[17]:= Equal[$x1, $x3] 
Out[17]= False    (* Oops *) 

小人揭密

所有這些討論的主要罪魁禍首是浮點實數格式。使用有限格式完全無限地表示任意實數是不可能的。這就是爲什麼Mathematica強調符號形式，並儘可能長時間儘可能以符號形式表達符號形式。如果發現數字形式是不可避免的，那麼就必須涉足swamp，稱爲numerical analysis，以整理所有涉及平等和不平等的角落案例。

差SameQ,Equal,DeleteDuplicates, Tally和他們所有的朋友從來沒有機會。

Answer 2

在我看來，依靠任何有Tally或DeleteDuplicates的默認（SameQ -like-based）比較函數和數值都依賴於實現細節，因爲SameQ沒有明確定義的數值語義。你看到的是其他語言中通常所說的「未定義行爲」。什麼人應該做的事，以獲得穩定的結果是使用

DeleteDuplicates[a,Equal] 

或

Tally[a,Equal] 

，類似的還有Union（雖然因爲明確的測試導致二次複雜性吧，我不會用Union）。 OTOH，如果你的願望是理解內部實現的細節，因爲你想利用它們，除了警告這可能會造成更多的傷害而不是更好，特別是因爲這些實現可能會隨着版本的變化而變化 - 即使假設你對某些特定版本的所有細節都適用。