Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
1  
What would be your expected output for your example? – march Feb 13 at 19:44
    
Also what do you mean by "efficient"? You want the fewest operations? Fastest code? Shortest code? – Quantum_Oli Feb 13 at 19:45
    
@march The result given by Gatherby[Sortedby[ ]]. – Shb Feb 13 at 19:47
1  
Check those results with a calculator, they are wrong! – Simon Woods Feb 13 at 23:38
2  
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. – Simon Woods Feb 14 at 11:41
up vote 10 down vote accepted

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

share|improve this answer
    
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. – Shb Feb 13 at 22:40
1  
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. – Simon Woods Feb 13 at 22:47
    
f7 too returns the wrong results for the example list in the updated question. – Shb Feb 13 at 23:04
    
Thank you @Simon, I updated the post with your suggestions. – kglr Feb 13 at 23:09
    
@Shb, the only difference between the outputs of the 10 functions is the ordering within each group; groups are ordered correctly. – kglr Feb 13 at 23:15

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

AbsoluteTiming[list3 = SortBy[GatherBy[list, Norm], N[Norm[#[[1]]]] &];]
share|improve this answer
    
I had result = With[{n = #.# &}, list~GatherBy~n~SortBy~n@*First] - same principle but faster if list is integers. – Simon Woods Feb 13 at 21:08
    
@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 :) – Dr. belisarius Feb 13 at 21:10
    
see updated question. – Shb Feb 13 at 22:09
    
@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]]] &]] – Dr. belisarius Feb 13 at 22:17
    
I don;t understand why you have an additional sort in there, but no your new suggestion too returns the old wrong answer. – Shb Feb 13 at 22:29
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  *)
share|improve this answer
    
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. – Shb Feb 13 at 20:17
    
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. – Shb Feb 13 at 20:19
    
hmmm why is SortBy[list, Norm] giving me: {{1, 7}, {1, 3}, {3, 1}, {1, 6}, {1, 20}} – Shb Feb 13 at 20:20
1  
I suggest using #.#& in place of N@*Norm for integers - it omits the square root step but that doesn't change the ordering. – Simon Woods Feb 13 at 21:10
2  
I am finished chasing a moving target. – Bob Hanlon Feb 14 at 1:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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