9
$\begingroup$

So let's say I want to group a list of points based on their distance from the origin. I would do something like:

list = {{1, 20}, {1, 6}, {1, 7}, {1, 3}, {3, 1}};
gathered = GatherBy[list, Norm[#]&]

and that would give me what I need, but that would not necessarily respect the ordering. I can apply SortBy[] first and then GatherBy[] the result:

sorted = SortBy[list, Norm[#] &]
partitionedBy = GatherBy[sorted, Norm[#] &]

But that is not very efficient. Is there any more efficient way of doing this using Mathematica's built-in functions. If not, What would be the most efficient way of achieving this?

update: if list is set to be a reduced accuracy version of an exact numerical expression, some of the methods suggested below will yield incorrect results. That is investigated in this question.

Improve this question
$\endgroup$
23
  • 1
    $\begingroup$ What would be your expected output for your example? $\endgroup$
    – march
    Commented Feb 13, 2016 at 19:44
  • $\begingroup$ Also what do you mean by "efficient"? You want the fewest operations? Fastest code? Shortest code? $\endgroup$
    – Quantum_Oli
    Commented Feb 13, 2016 at 19:45
  • $\begingroup$ @march The result given by Gatherby[Sortedby[ ]]. $\endgroup$
    – Shb
    Commented Feb 13, 2016 at 19:47
  • 1
    $\begingroup$ Check those results with a calculator, they are wrong! $\endgroup$
    – Simon Woods
    Commented Feb 13, 2016 at 23:38
  • 2
    $\begingroup$ The issue of how N affects Accuracy is a quite different problem to the original question regarding efficient sort & gather algorithms. It should be a separate question. People took time and trouble to answer the original question, and it's rather unfair to claim that their (perfectly good) answers don't work because of special features in your data that you didn't reveal until several hours later. It will also be more useful to future visitors looking for efficient sort & gather algorithms if the question is unencumbered by the requirement to avoid using N. $\endgroup$
    – Simon Woods
    Commented Feb 14, 2016 at 11:41

3 Answers 3

Reset to default
10
$\begingroup$

As noted by @SimonWoods in the comments, using #.#& instead of Norm gives a huge speed up.

ClearAll[f1, f1b, f2, f2b, f3, f3b, f4, f5, f6, f7, f8]
f1 = GatherBy[SortBy[#, N@Norm@# &], N@Norm@# &] &;
f2 = SplitBy[SortBy[#, N@Norm@# &], N@Norm@# &] &;
f3 = SortBy[GatherBy[#, N[Norm@#] &], N[Norm[#[[1]]]] &] &;
f1b = GatherBy[SortBy[#, #.# &], #.# &] &;
f2b = SplitBy[SortBy[#, #.# &], #.# &] &;
f3b = SortBy[GatherBy[#, #.# &], #[[1]].#[[1]] &] &;
f4 = With[{norms = #.# & /@ #, lst = #}, 
    lst[[#]] & /@ SplitBy[Ordering[norms], norms[[#]] &]] &;
f5 = With[{norms = #.# & /@ #, lst = #}, 
    lst[[#]] & /@ GatherBy[Ordering[norms], norms[[#]] &]] &;
f6 = With[{gathered = GatherBy[#, #.# &]}, 
    gathered[[Ordering[#.# & /@ (First /@ gathered)]]]] &;
f7 = With[{gathered = GatherBy[#, #.# &]}, 
    With[{norms = #.# & /@ (First /@ gathered)}, 
     gathered[[Ordering[norms]]]]] &;

list0 = RandomInteger[{0, 20}, {100000, 2}];
timings = 
  First[AbsoluteTiming[# = #2@list0;]] & @@@ 
   Transpose[{{l1, l1b, l2, l2b, l3, l3b, l4, l5, l6, l7}, {f1, f1b, 
      f2, f2b, f3, f3b, f4, f5, f6, f7}}];
functions = {"f1", "f1b", "f2", "f2b", "f3", "f3b", "f4", "f5", "f6", 
   "f7"};
TableForm[Transpose[{functions, timings}], 
 TableHeadings -> {None, {"functions", "timings"}}]

Mathematica graphics

Equal @@ ((Norm /@ (First /@ #) & /@ {l1, l1b, l2, l2b, l3, l3b, l4, l5, l6, l7}))
(* True *)

Additional timings:

list0 = RandomInteger[{0, 500}, {100000, 2}];

Mathematica graphics

list0 = RandomInteger[{0, 20}, {100000, 5}];

Mathematica graphics

Improve this answer
$\endgroup$
10
  • $\begingroup$ Thanks. FYI, I just tested these with {{0.*10^-2, 0.*10^-2}, {1.3, 1.}, {0.2, 0.6}, {0.2, -0.6}, {1.3, -1.}, {-0.5, 1.5}, {-0.5, 0.4}, {0.6, 0.*10^-2}, {-1.6, 0.*10^-2}, {-0.5, -0.4}, {-0.5, -1.5}} and only f2 and f4 are giving me the results I am expecting. $\endgroup$
    – Shb
    Commented Feb 13, 2016 at 22:40
  • 1
    $\begingroup$ The difference between using Norm and #.#& accounts for a lot of the speed differences. It would be interesting to compare the different approaches using the same norm function throughout. $\endgroup$
    – Simon Woods
    Commented Feb 13, 2016 at 22:47
  • $\begingroup$ f7 too returns the wrong results for the example list in the updated question. $\endgroup$
    – Shb
    Commented Feb 13, 2016 at 23:04
  • $\begingroup$ Thank you @Simon, I updated the post with your suggestions. $\endgroup$
    – kglr
    Commented Feb 13, 2016 at 23:09
  • $\begingroup$ @Shb, the only difference between the outputs of the 10 functions is the ordering within each group; groups are ordered correctly. $\endgroup$
    – kglr
    Commented Feb 13, 2016 at 23:15
6
$\begingroup$

This is more than 50% faster, since it evaluates only one Norm for each sublist:

AbsoluteTiming[list3 = SortBy[GatherBy[list, Norm], N[Norm[#[[1]]]] &];]
Improve this answer
$\endgroup$
10
  • $\begingroup$ I had result = With[{n = #.# &}, list~GatherBy~n~SortBy~n@*First] - same principle but faster if list is integers. $\endgroup$
    – Simon Woods
    Commented Feb 13, 2016 at 21:08
  • $\begingroup$ @SimonWoods Can't try it as it is, because V9 still here, but Norm is usually a slow thing, so I guess you're right :) $\endgroup$
    – Dr. belisarius
    Commented Feb 13, 2016 at 21:10
  • $\begingroup$ see updated question. $\endgroup$
    – Shb
    Commented Feb 13, 2016 at 22:09
  • $\begingroup$ @Shb The only difference is the order into the sublists list2 = {{0.*10^-2, 0.*10^-2}, {1.3, 1.}, {0.2, 0.6}, {0.2, -0.6}, {1.3, -1.}, {-0.5, 1.5}, {-0.5, 0.4}, {0.6, 0.*10^-2}, {-1.6, 0.*10^-2}, {-0.5, -0.4}, {-0.5, -1.5}}; Sort /@ SplitBy[SortBy[list2, Norm], Norm] == Sort /@ SortBy[GatherBy[list2, Norm], N[Norm[#[[1]]] &]] $\endgroup$
    – Dr. belisarius
    Commented Feb 13, 2016 at 22:17
  • $\begingroup$ I don;t understand why you have an additional sort in there, but no your new suggestion too returns the old wrong answer. $\endgroup$
    – Shb
    Commented Feb 13, 2016 at 22:29
4
$\begingroup$ 
list = RandomInteger[{0, 20}, {10000, 2}];

AbsoluteTiming[list2 = GatherBy[SortBy[list, N[Norm[#]] &], Norm];]

(*  {0.149292, Null}  *)

SplitBy will partition without additional sorting; however, it is nonetheless slower.

AbsoluteTiming[list3 = SplitBy[SortBy[list, N[Norm[#]] &], Norm];]

(*  {0.212032, Null}  *)

Verifiying that the two results are identical

list2 === list3

(*  True  *)

Sort and SortBy sort by canonical order. This is only equivalent to numeric order for numbers rather than numeric expressions. See Possible Issues under Sort: "Numeric expressions are sorted by structure as well as numerical value"

EDIT: To address the revised question

list4 = {{0.*10^-2, 0.*10^-2}, {1.3, 1.}, {0.2, 
    0.6}, {0.2, -0.6}, {1.3, -1.}, {-0.5, 1.5}, {-0.5, 0.4}, {0.6, 
    0.*10^-2}, {-1.6, 0.*10^-2}, {-0.5, -0.4}, {-0.5, -1.5}};

ans1 = GatherBy[SortBy[list4, N[Norm[#] &]], Norm];

Since you are using machine numbers in this case, use of N is not required

ans2 = GatherBy[SortBy[list4, Norm], Norm];

ans3 = SplitBy[SortBy[list4, N[Norm[#]] &], Norm];

Again, since you are using machine numbers, use of N is not required

ans4 = SplitBy[SortBy[list4, N[Norm[#]] &], Norm];

These are all identical

ans1 === ans2 === ans3 === ans4

(*  True  *)

These are in the correct numeric order

OrderedQ[Norm[#[[1]]] & /@ ans1]

(*  True  *)
Improve this answer
$\endgroup$
11
  • $\begingroup$ I just noticed that GatherBy[SortBy[list, Norm], Norm] does not give the answer I was expecting. it gives me: {{{1, 7}}, {{1, 3}, {3, 1}}, {{1, 6}}, {{1, 20}}} I was expecting {{1,3},{3,1}} to come first. Also there is extra parenthesis. $\endgroup$
    – Shb
    Commented Feb 13, 2016 at 20:17
  • $\begingroup$ I initially had: SortBy[GatherBy[list, Norm], Norm] but I realized that while it was giving me the right answer, it was only working because Norm[list]==Norm[{list}] which doesn't necessarily hold for a given function. $\endgroup$
    – Shb
    Commented Feb 13, 2016 at 20:19
  • $\begingroup$ hmmm why is SortBy[list, Norm] giving me: {{1, 7}, {1, 3}, {3, 1}, {1, 6}, {1, 20}} $\endgroup$
    – Shb
    Commented Feb 13, 2016 at 20:20
  • 1
    $\begingroup$ I suggest using #.#& in place of N@*Norm for integers - it omits the square root step but that doesn't change the ordering. $\endgroup$
    – Simon Woods
    Commented Feb 13, 2016 at 21:10
  • 2
    $\begingroup$ I am finished chasing a moving target. $\endgroup$
    – Bob Hanlon
    Commented Feb 14, 2016 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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