wolfram-mathematica - 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}}

This behavior is as I expected in each case. Tally compensates for the slight numerical differences and sees each element as being equivalent. Union and DeleteDuplicates see all elements as unique. (This behavior of Tally is not documented to my knowledge, but I have made use of it before.)

Now, consider this complication:

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}}

The output of Union is as anticipated, but the results from both DeleteDuplicates and Tally are surprising.

• Why does DeleteDuplicates suddenly see 2.1999999999999997 as a duplicate to be eliminated?

• Why does Tally suddenly see 2.2000000000000006 and 2.2 as distinct, when it did not before?

---

As a related point, it can be seen that packed arrays affect 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表现出类似但不完全相同的不稳定行为:

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他们所有的 friend 都没有机会。