Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
    
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 '13 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 '13 at 19:53

6 Answers 6

You could do this:

GatherBy[list, Last][[All, 1]] ~SortBy~ Last
(*  {{d, 3}, {b, 3.04}, {a, 3.1}}  *)
share|improve this answer
    
Ok, this is much more direct than what I had, using similar idea. +1. Will delete mine. –  Leonid Shifrin Jun 19 '13 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.

share|improve this answer
    
please also see my answer. Sadly it removes different duplicates than the Gather function, but it is still correct I think. –  Jacob Akkerboom Jul 23 '13 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]] &]
share|improve this answer
    
I had originally posted that, but if you notice, it does not produce the order that the OP wants. –  rcollyer Jun 19 '13 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." –  bill s Jun 19 '13 at 20:14
    
well, I'll be. maybe I should have read it closer. (+1) –  rcollyer Jun 19 '13 at 20:15
1  
@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. –  Leonid Shifrin Jun 19 '13 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 '13 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.

share|improve this answer
4  
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. –  Leonid Shifrin Jun 19 '13 at 21:48
    
Cool. Makes sense. –  Philip Maymin Jun 20 '13 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.

share|improve this answer
    
I added timings to my answer. –  Mr.Wizard Jun 25 '13 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. –  Szabolcs Jun 26 '13 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

share|improve this answer
    
@Kuba thanks for editing :). –  Jacob Akkerboom Jul 23 '13 at 13:50
1  
Jacob, you should try the stable SortBy[a, {Last}] as well. –  Mr.Wizard Jul 24 '13 at 15:07
    
@Mr.Wizard Wow, its faster :). Great! –  Jacob Akkerboom Jul 24 '13 at 15:15

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.