GroupBy twice gives different results

Question

Bug introduced in 7.0 or earlier and persisting through 11.1

---

It took me quite a lot of time to finally trace down to this strange output. I really don't know why.

First, I create a list

rot1 = RotationTransform[{{1, 0, 1}, {0, 0, -1}}, {0, 0, 0}];
tmp = rot1@Tuples[Range[0, 10, 1], 3];

Then run

grouptmp1 = GroupBy[tmp, N[Last[#], 8] &];
grouptmp2 = GroupBy[tmp, N[Last[#], 8] &];
grouptmp1 === grouptmp2

The first time you run the above code, it will give "False", the second time and after, it will give true. So strange, what is wrong here?

BTW, I use N[Last[#], 8] & to add some tolerance to the GroupBy operation. If there is better method, welcome to leave a comment or write an answer

Updata*

New discovery!! GatherBy also suffers, Try

gathertmp1 = GatherBy[tmp, N[Last[#], 8] &];
gathertmp2 = GatherBy[tmp, N[Last[#], 8] &];
gathertmp1 === gathertmp2

Maybe all By suffers

Update2

Temporary workaround I figured out at this moment:

    test1 = KeySort@KeyMap[(#[[1]]*N[FromDigits[#[[2]]]]) &, 
  GroupBy[tmp, {Sign[Last@#], RealDigits[N@Last@#, 10, 8]} &]]
    test2 = KeySort@KeyMap[(#[[1]]*N[FromDigits[#[[2]]]]) &, 
  GroupBy[tmp, {Sign[Last@#], RealDigits[N@Last@#, 10, 8]} &]]
    test1 === test2

This gives true no matter how many times of evaluating

Update3

Simon Woods provide a simple example to reproduce the bug

ClearSystemCache[]; a = 3/Sqrt[2] + 2 Sqrt[2]; Table[ GroupBy[{a, a}, N[#, 3] &], {2}]

I tested it in mma version 7, since ver 7 doesn't have GroupBy, I use GatherBy instead, this is the result

{{{3/Sqrt[2] + 2 Sqrt[2]}, {3/Sqrt[2] + 2 Sqrt[2]}}, {{3/Sqrt[2] + 
    2 Sqrt[2], 3/Sqrt[2] + 2 Sqrt[2]}}}

So this bug lurking since version 7 !

Answer 1

Quit the kernel before each test. This is on MMA 10.3 on Mac OS X.

Simplify the problem

We can simplify so that tmp is much much smaller and easier to analyse:

rot1 = RotationTransform[{{1, 0, 1}, {0, 0, -1}}, {0, 0, 0}];
tmp = rot1@Tuples[Range[3, 6], 3];

grouptmp1 = GroupBy[tmp, N[Last[#], 8] &];
grouptmp2 = GroupBy[tmp, N[Last[#], 8] &];
grouptmp1 === grouptmp2

This still returns False.

Where is the problem?

The Keys of each association are the same:

Keys[grouptmp1] === Keys[grouptmp2] (* outputs True *)

Subsequent evaluations of grouptmp1 === grouptmp2 remain False.

The only Key where the values in grouptmp1 are different is:

Select[Keys[grouptmp1], grouptmp2[#] =!= grouptmp1[#] &]

Output is {-6.3639610}.

How can this possibly be? How can we group a list in two "different" ways and have the output differ in only one place?

What is the problem?

What is different about grouptmp1 and grouptmp2 in this position? If we Sort we still get different lists, so it's not an ordering problem:

Sort@grouptmp1[-6.36396103067892753155009157319037478428`8.] === Sort@grouptmp2[-6.36396103067892753155009157319037478428`8.]

returns False.

It turns out that grouptmp2 has the extra element {-(3/Sqrt[2]) + 3 Sqrt[2], 3, -(3/Sqrt[2]) - 3 Sqrt[2]} relative to grouptmp1 in this position. (Use Complement[grouptmp1[key], grouptmp2[key]], and the same with the arguments reversed, to work this out.)

Flatten[Values[grouptmp1], 1] // Length

This returns 63. That is, grouptmp1 has mysteriously lost the element {-(3/Sqrt[2]) + 3 Sqrt[2], 3, -(3/Sqrt[2]) - 3 Sqrt[2]} from tmp.

This very definitely looks like a bug. GroupBy has lost an element of the first thing we ran it on. (It's not to do with the variable names grouptmp1 and grouptmp2, it seems, because I swapped the order in which they were assigned and it's the first one which has the error.)

Answer 2

It looks like a problem of numeric cache:

SetSystemOptions["CacheOptions" -> {"Numeric" -> {"Cache" -> False}}];
tmp = {3/Sqrt[2] + 3 Sqrt[2], 3/Sqrt[2] + 3 Sqrt[2]};

grouptmp1 = GroupBy[tmp, N[#, 8] &];
grouptmp2 = GroupBy[tmp, N[#, 8] &];
grouptmp1 === grouptmp2
(* True *)

With caching I get False. See also Simon Woods's comment.

There is a more global problem even without caching. Let us consider a list with almost equal values

list = Rationalize[RandomReal[{1.0006, 1.00062}, 1000], 0];

However, GroupBy splits it to 2 groups:

keys = Keys@GroupBy[list, N[#, 4] &]
(* {1.001, 1.001} *)

keys // InputForm
(* {1.00060319124101772085572137934965342771`4., 
    1.00061484060574776948630746611773121172`4.} *)

Equal @@ keys
(* True *)

It looks like that GroupBy performs some sort of rounding and hashing

Hash /@ N[list, 4] // Tally
(* {{7485563185340423637, 516}, {3244483472298741377, 484}} *)

Finally, I propose to use robust grouping by pairwise comparison:

Length@Gather[list, Abs[# - #2] < 0.001 &]
(* 1 *)