Sort+Union on a list

Probably this is too trivial question for this forum but for some reason I am not getting it on my Mathematica 7 so far. I have a list

list = {{b, 3.04},{d,3},{a,3.10},{c,3}}


I want to sort it for the second element and eliminate those elements for which the second element has the same value. The first element doesn't matter much. In short, the answer should be

{{d,3},{b,3.04},{a,3.10}}


I used

SortBy[list,#[[2]] &]


to sort the list with respect to the second element. I can also do something similar for eliminating the elements for which the second element has the same value. But is there any more efficient way? It is something like Union but only for the second element if you know what I mean?

• It seems not consistent. If You want to eliminate elements for which the second part is the same then the answer should be: {{b,3.04},{a,3.10}}. If not, and You want to delete duplicates in second part then why "d" is better than "c"? Why the answer couldn't be {{d,3},{b,3.04},{a,3.10}}?
– Kuba
Jun 19, 2013 at 19:51
• @Kuba, Thanks. I want to delete duplicates in the second part and not eliminate all such elements. As I said, the first element doesn't matter much. So "d" is no better than "c". So it doesn't matter, to me, which of the two duplicates you choose.
– dbm
Jun 19, 2013 at 19:53
• Related: (21711) Feb 19, 2016 at 21:54

You could do this:

GatherBy[list, Last][[All, 1]] ~SortBy~ Last
(*  {{d, 3}, {b, 3.04}, {a, 3.1}}  *)

• Ok, this is much more direct than what I had, using similar idea. +1. Will delete mine. Jun 19, 2013 at 20:06

Simon Woods already gave what is arguably the canonical answer, but I always like seeing and sharing alternatives. Since one of the operations here is a duplicate-removal we can adapt some of the methods described in Delete duplicate elements from a list.

SeedRandom[3]
a = RandomInteger[5, {9, 2}];
(* {{3, 5}, {0, 1}, {2, 0}, {0, 4}, {5, 2}, {2, 2}, {1, 0}, {0, 2}, {1, 3}} *)


Sequence

Module[{f},
f[d : {_, x_}] := (f[{_, x}] = Sequence[]; d);
SortBy[f /@ a, Last]
]


{{2, 0}, {0, 1}, {5, 2}, {1, 3}, {0, 4}, {3, 5}}

Sow & Reap

Reap[Sow @@@ a, _, {#2[[1]], #} &][[2]] ~SortBy~ Last


Sow and Reap are also conducive to a form with integrated sorting:

Reap[Sow @@@ a, Union[Last /@ a], {#2[[1]], #} &][[2, All, 1]]


Tally

The Tally method ("For Mathematica 6") is analogous to Simon's use of GatherBy:

GatherBy[a, Last][[All, 1]] ~SortBy~ Last


Rules

With this method it makes more sense to use integrated sorting than not:

Union @ a[[All, 2]] /. Dispatch[#2 -> {##} & @@@ a]


In a maximally terse form (without the performance of Dispatch) this is the shortest method of all:

Union[Last/@a]/.#2->{##}&@@@a


Another form with an arbitrary function in place of last:

suBy[a_, f_] := Union[#] /. Thread[# -> a] &[f /@ a]

suBy[a, Last]


Performance comparison

The Sequence method is omitted as it is very slow. First on a set with heavy duplication:

a = RandomInteger[1000, {500000, 2}];

Reap[Sow @@@ a, _, {#2[[1]], #} &][[2]] ~SortBy~ Last          // Timing // First
Reap[Sow @@@ a, Union[Last /@ a], {#2[[1]], #} &][[2, All, 1]] // Timing // First
GatherBy[a, Last][[All, 1]] ~SortBy~ Last                      // Timing // First
Union @ a[[All, 2]] /. Dispatch[#2 -> {##} & @@@ a]            // Timing // First


0.171

0.266

0.046

1.857

Then a set with limited duplication:

a = RandomInteger[300000, {150000, 2}];

Reap[Sow @@@ a, _, {#2[[1]], #} &][[2]] ~SortBy~ Last          // Timing // First
Reap[Sow @@@ a, Union[Last /@ a], {#2[[1]], #} &][[2, All, 1]] // Timing // First
GatherBy[a, Last][[All, 1]] ~SortBy~ Last                      // Timing // First
Union @ a[[All, 2]] /. Dispatch[#2 -> {##} & @@@ a]            // Timing // First


1.389

1.046

0.375

0.483

Plainly GatherBy is best in either case but the alternatives are more competitive here.

SplitBy

Szabolcs proposed a different form with the claim that "it might be theoretically a bit more efficient."

Here are some Timings comparing it to the GatherBy method. Also, SortBy[. . ., Last] is not a stable sort, so I shall additionally include a variation with {Last}; this is arguably more "correct" and also often more efficient.

With heavy duplication:

a = RandomInteger[1000, {500000, 2}];

GatherBy[a, Last][[All, 1]] ~SortBy~ Last  // Timing // First
SplitBy[SortBy[a, Last], Last][[All, 1]]   // Timing // First
SplitBy[SortBy[a, {Last}], Last][[All, 1]] // Timing // First


0.05992

0.593

0.514

Here SplitBy is an order of magnitude slower; the stable version is a bit faster but not by a lot.

With limited duplication:

a = RandomInteger[300000, {150000, 2}];

GatherBy[a, Last][[All, 1]] ~SortBy~ Last  // Timing // First
SplitBy[SortBy[a, Last], Last][[All, 1]]   // Timing // First
SplitBy[SortBy[a, {Last}], Last][[All, 1]] // Timing // First


0.468

0.375

0.343

Here SplitBy is faster but not nearly to the degree that it was slower in the prior example. The stable version is again slightly faster.

With non-packed String data (moderately heavy duplication):

a = FromCharacterCode /@ RandomInteger[{97, 122}, {150000, 2, 3}];

GatherBy[a, Last][[All, 1]] ~SortBy~ Last  // Timing // First
SplitBy[SortBy[a, Last], Last][[All, 1]]   // Timing // First
SplitBy[SortBy[a, {Last}], Last][[All, 1]] // Timing // First


0.0812

0.437

0.2152

GatherBy wins, but perhaps more interesting the stable sort is now twice as efficient as the original version.

• please also see my answer. Sadly it removes different duplicates than the Gather function, but it is still correct I think. Jul 23, 2013 at 13:07

One way is to use the optional second argument of Union, which specifies what elements are to be considered the same. This tests to see if the second elements are less than 10^-4 apart, and then sorts the results.

union = Union[list, SameTest -> (Abs[#1[[2]] - #2[[2]]] < 10^-4 &)];
SortBy[union, #[[2]] &]

{{c, 3}, {b, 3.04}, {a, 3.1}}


Combining the two lines and testing for equality gives the same answer:

SortBy[Union[list, SameTest -> (#1[[2]] == #2[[2]] &)], #[[2]] &]

• I had originally posted that, but if you notice, it does not produce the order that the OP wants. Jun 19, 2013 at 20:11
• @rcollyer -- quoting the OP: "the first element doesn't matter much. So "d" is no better than "c". So it doesn't matter, to me, which of the two duplicates you choose." Jun 19, 2013 at 20:14
• well, I'll be. maybe I should have read it closer. (+1) Jun 19, 2013 at 20:15
• @rcollyer There is a more serious flaw here: Union with explicit test has a quadratic complexity on the size of the list. Besides, 10^-4 seems rather arbitrary. Jun 19, 2013 at 20:21
• Thanks a lot to all for your efforts. Apparently, it wasn't that trivial a problem then. Phew! 10^-4 seems arbitrary of course, but then we can change it. But for now I would use Leonid Shifrin's code as it relies on Mathematica's way of comparing two numbers rather than inserting our own tolerance.
– dbm
Jun 19, 2013 at 20:30

Since you're using Mathematica 7, you could use DeleteDuplicates, it's what it was made for.

SortBy[DeleteDuplicates[list, Last@#1 == Last@#2 &], Last]


Though I personally like @Simon Woods's answer better, for elegance.

Edit: to be clear, it sounds like you were only sorting as a prelude to a solution. If you don't actually need the sort, then it is just pure DeleteDuplicates.

• This is not just a question of elegance. DeleteDuplicates with an explicit test function (second argument) will use pairwise comparisons, which will lead to a quadratic time complexity in the size of the list. Simon's solution is linear complexity. Jun 19, 2013 at 21:48
• Cool. Makes sense. Jun 20, 2013 at 3:15

This is practically the same as Simon's solution, but it might be theoretically a bit more efficient:

SplitBy[SortBy[list, Last], Last][[All, 1]]


This is in fact what people used when Gather/GatherBy were not yet available. I believe SplitBy can be theoretically more efficient than GatherBy, but I have not benchmarked if this is indeed the case for the particular implementations in Mathematica.

Update According to Mr. Wizard's timings, the SplitBy approach is actually considerably slower than the GatherBy one.

• I added timings to my answer. Jun 25, 2013 at 22:18
• @Mr.Wizard Thanks for the timings and especially pointing out the difference between SortBy[...,f] and SortBy[..., {f}]. Since you posted a detailed benchmark, I won't remove the answer, but I put in a note saying that it's not fast. Jun 26, 2013 at 6:00

My solution:

If[SameQ @@ #[[All, 2]], Unevaluated[Sequence[]], First@#] & /@
Partition[SortBy[list, Last], 2, 1, {1, 1}, {{Null, Null}}]


Speed comparison

These comparisons were made using version 9.0.0. Things are different for version 7, as can be seen from Mr.Wizards speed comparisons (SplitBy is now faster). Anyway I think a comparison for version 9 may interesting as well.

a = RandomInteger[300000, {150000, 2}];

If[SameQ @@ #[[All, 2]], Unevaluated[Sequence[]], First@#] & /@
Partition[SortBy[a, Last], 2, 1, {1, 1}, {{Null, Null}}] //
Timing // First
GatherBy[a, Last][[All, 1]]~SortBy~Last // Timing // First
SplitBy[SortBy[a, Last], Last][[All, 1]] // Timing // First
TimeConstrained[
Reap[Sow @@@ a, _, {#2[[1]], #} &][[2]]~SortBy~Last // Timing //
First, 2, "takes too long"
]
Union@a[[All, 2]] /. Dispatch[#2 -> {##} & @@@ a] // Timing // First

SplitBy[SortBy[a, {Last}], Last][[All, 1]] // Timing // First (*by Mr.Wizard in the comments*)


1.048681 (mine)
0.924527 (Simon Woods)
0.616817 (Szabolcs's SplitBy)
"takes too long"
0.954735
0.551219 (Mr.Wizard SplitBy)

My solution has no practical use, but it is fun anyway. For lists with less duplicates it can actually outperform the other answers, except Szabolcs's.

If not all the answers delete the same duplicates, that is too bad, but it was not a requirement by the OP to delete specific duplicates.

I think Split was improved in version 9.

Side remarks

In the case where we have no pairs of elements, but just single numbers, ListConvolve gives a funky alternative

ListConvolve[{1, 1}, ints, {-1, -1}, {0}, #2 &,
If[SameQ[##], Unevaluated[Sequence[]], #] &]


But here DeleteDuplicates is ideal I think.

I have tried to make a version using ListConvolve for this Q&A but ListConvolve will interpret list as a tensor of rank two, which makes things more difficult.

Related question

• @Kuba thanks for editing :). Jul 23, 2013 at 13:50
• Jacob, you should try the stable SortBy[a, {Last}] as well. Jul 24, 2013 at 15:07
• @Mr.Wizard Wow, its faster :). Great! Jul 24, 2013 at 15:15