34
$\begingroup$

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 !

$\endgroup$
  • 1
    $\begingroup$ Same with we (V 10.0) - very strange $\endgroup$ – eldo Nov 22 '15 at 12:51
  • $\begingroup$ Same if you use Range[3, 6] - makes it a lot easier to analyse. Investigating. $\endgroup$ – Patrick Stevens Nov 22 '15 at 12:59
  • 2
    $\begingroup$ 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. $\endgroup$ – Daniel Lichtblau Nov 22 '15 at 19:02
  • $\begingroup$ @DanielLichtblau I also thought so, but check my answer. After disbling the cache you get the second (correct) result twice. $\endgroup$ – ybeltukov Nov 22 '15 at 21:43
  • 1
    $\begingroup$ @ybeltukov I see what you mea.. Thanks for the note and very simple example. This seriously warrants further investigation. $\endgroup$ – Daniel Lichtblau Nov 23 '15 at 16:19
21
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So, a bug? I have to say this bug is especially strange. $\endgroup$ – matheorem Nov 22 '15 at 13:14
  • 5
    $\begingroup$ 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}] $\endgroup$ – Simon Woods Nov 22 '15 at 13:29
  • $\begingroup$ @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 :( $\endgroup$ – matheorem Nov 22 '15 at 14:27
19
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.