Нестабильность в DeleteDuplicates и Tally

Ответ 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, [email protected][#, 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... Confused

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 *)

Злодей Unmasked

Основным виновником во всем этом обсуждении является формат реального числа с плавающей запятой. Просто невозможно представить произвольные действительные числа в полной форме, используя конечный формат. Вот почему Mathematica подчеркивает символическую форму и делает все возможную попытку работать с выражениями в символической форме как можно дольше. Если вы обнаружите, что числовые формы неизбежны, то нужно впасть в это болото, называемое численный анализ, чтобы разобраться во всех случаях, связанных с равенством и неравенством.

Плохое SameQ, Equal, DeleteDuplicates, Tally и все их друзья никогда не выходили.

Ответ 2

По-моему, полагаясь на что-либо для Tally или DeleteDuplicates с функцией сравнения по умолчанию (SameQ -like), а числовые значения полагаются на детали реализации, потому что SameQ не имеет четко определенных семантика по числовым значениям. То, что вы видите, обычно называется "поведение undefined" на других языках. Что нужно делать для получения надежных результатов, так это использовать

DeleteDuplicates[a,Equal]

или

Tally[a,Equal]

и аналогично для Union (хотя я бы не использовал Union, поскольку явный тест приводит к квадратичной сложности для него). OTOH, если ваше желание понять детали внутренней реализации, потому что вы хотите их использовать, я не могу сказать многого, кроме как предупредить, что это может принести больше вреда, чем пользы, особенно потому, что эти реализации могут быть изменены с версии на версию - даже если предположить, что вы получите все свои данные для определенной версии.