# GroupBy twice gives different results

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 !

• Same with we (V 10.0) - very strange – eldo Nov 22 '15 at 12:51
• Same if you use Range[3, 6] - makes it a lot easier to analyse. Investigating. – Patrick Stevens Nov 22 '15 at 12:59
• Using GatherBy in version 9 (what I have access to at the moment) I notice that the problematic result is the first one, not the second one (the first has repeats that are numerically the same to 8 digits). That is to say, the operation appears to improve with use of cached numeric values. Needs further investigation though. – Daniel Lichtblau Nov 22 '15 at 19:02
• @DanielLichtblau I also thought so, but check my answer. After disbling the cache you get the second (correct) result twice. – ybeltukov Nov 22 '15 at 21:43
• @ybeltukov I see what you mea.. Thanks for the note and very simple example. This seriously warrants further investigation. – Daniel Lichtblau Nov 23 '15 at 16:19

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.363961030678927531550091573190374784288.] === Sort@grouptmp2[-6.363961030678927531550091573190374784288.]


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

• So, a bug? I have to say this bug is especially strange. – matheorem Nov 22 '15 at 13:14
• Looks like some kind of bug relating to the caching of numerical values. A simplified example: ClearSystemCache[]; a = 3/Sqrt[2] + 2 Sqrt[2]; Table[ GroupBy[{a, a}, N[#, 3] &], {2}] – Simon Woods Nov 22 '15 at 13:29
• @SimonWoods So you mean this seems a more fundamental bug? Oh, my god! How many kind of situation can this bug affect? I may have already "written" some other bugs in my code :( – matheorem Nov 22 '15 at 14:27

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.000603191241017720855721379349653427714.,
1.000614840605747769486307466117731211724.} *)

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

• Thank you, see my recent update. Version 7 also suffers – matheorem Nov 22 '15 at 14:37
• You propose what?! – Simon Woods Nov 22 '15 at 15:56
• @SimonWoods Thanks, I corrected the typo. – ybeltukov Nov 22 '15 at 16:15
• I think GroupBy uses a comparison equivalent to MatchQ instead of Equal. Consider MatchQ[#, First@keys] & /@ N[list, 4] // Tally. – Michael E2 Nov 22 '15 at 16:57