Sort+Union on a list

Question

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?

Answer 1

You could do this:

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

Answer 2

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]] &]

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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