14
$\begingroup$

I want to be able to select elements from a list that only appear once. I originally had this:

Select[Table[Count[list, i], {i, list}], # == 1]

But the issue is that my list has about 60,000 elements, and it takes way too long. The only way I could think of speeding it up would be to make a function like Count, but that would return after seeing the same element twice, and I have no idea how to do that in Mathematica.

Also, I'm not sure if it's important, but the list is actually a list of lines (with a line defined by two 2D points). The goal is to find the edges that are only used by one triangle, hence making them a perimeter edge. Thanks!

Improve this question
$\endgroup$
4
  • $\begingroup$ Here is one for fun, but it is no where as fast as Belisarius u = Union[lis]; Pick[u, Count[lis, #] & /@ u, 1]; $\endgroup$
    – Nasser
    Commented Aug 17, 2013 at 6:23
  • $\begingroup$ Interesting thing is that Matlab has a build-in function for this exact thing. It is called unique() mathworks.com/help/matlab/ref/unique.html $\endgroup$
    – Nasser
    Commented Aug 17, 2013 at 6:25
  • 1
    $\begingroup$ Related: (18100) $\endgroup$
    – Mr.Wizard
    Commented Aug 17, 2013 at 15:50
  • $\begingroup$ Cases[Tally[yt], {a_, b_ /; b == 1} -> a] $\endgroup$
    – Pankaj Sejwal
    Commented Aug 18, 2013 at 13:51

9 Answers 9

Reset to default
18
$\begingroup$

The following isn't probably the fastest way, but fast enough for 60K elements:

yourList = RandomInteger[10000, 60000];

Select[Tally@yourList, #[[2]] == 1 &][[All, 1]]

The Timing in my machine is well under 0.1 sec.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Cases[Tally@yourList, {_, 1}][[All, 1]] is a bit faster for me. $\endgroup$
    – Mike Honeychurch
    Commented Aug 17, 2013 at 7:18
  • $\begingroup$ @MikeHoneychurch Thanks! Here too yours is a bit faster $\endgroup$
    – Dr. belisarius
    Commented Aug 17, 2013 at 13:49
7
$\begingroup$

Another possibility:

Flatten@Cases[Gather@yourList, {_}]


Edit 2. Just for Fun

Borrowing from the efficient method given above by belisarius

Pick[#[[All, 1]], #[[All, 2]], 1] &@Tally@yourList


Edit

@Nasser adds the following (surprising to my mind) timing results, comparing my original method (Gather) with that given by belisarius:

enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ nice. But it slows down alot when the size of the list becomes large. see screen shot: !Mathematica graphics $\endgroup$
    – Nasser
    Commented Aug 17, 2013 at 7:39
  • $\begingroup$ code for above: r = Flatten[Last@Reap[Do[ yourList = RandomInteger[10000, n]; Sow[{n, Timing[Select[Tally@yourList, #[[2]] == 1 &][[All, 1]]][[1]], Timing[Flatten@Cases[Gather@yourList, {_}]][[1]]}] , {n, 100000, 6000000, 100000} ]], 1]; ListLinePlot[{r[[All, 2]], r[[All, 3]]}, Joined -> True, PlotLegends -> {"Tally", "Gather"}, PlotLabel -> "CPU time (sec)"] $\endgroup$
    – Nasser
    Commented Aug 17, 2013 at 7:40
  • $\begingroup$ Please double check that the code that generated the plot is correct. The code is above. I did my best to make sure it is correct, and I was also surprised by the result. $\endgroup$
    – Nasser
    Commented Aug 17, 2013 at 10:17
7
$\begingroup$

This is certainly not fast, but is different from the ones previously posted:

onlyOnce[list_] := Block[{f},
    f[x_] := f[1, x] = If[f[1, x], False, False, True];

    Scan[f, list];
    Select[list, f[1, #] &]
]

belisarius' is about 10 times faster on my machine.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The Listable attribute seems to interfere with this working with elements that are themselves lists. $\endgroup$
    – Michael E2
    Commented Aug 17, 2013 at 15:51
  • $\begingroup$ @MichaelE2 Ah, that's the remains from an earlier Pick based version I had which did Pick[list, f[list];f[1,list],True]. I've removed it now $\endgroup$
    – rm -rf ♦
    Commented Aug 17, 2013 at 16:59
6
$\begingroup$

I've thought that the following method will be fun but not efficient alternative, but it looks like it can be useful:

Split@Sort@list /. {Repeated[n_, {2,Infinity}]} :> Sequence[] // Flatten

for @belisarius test I have the following timings:

0.053003 (*mine*)
0.034002 (*belisarius*)

but for case where there are less or no unique elements it is comparable or even a little bit faster.

Here is an improvement suggested by Mr. Wizard:

Cases[Split@Sort@list, {x_} :> x]

which makes this method two times faster than first approach with ReplaceAll.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Nice idea. Shorter and faster: Cases[Split@Sort@list, {x_} :> x] $\endgroup$
    – Mr.Wizard
    Commented Aug 17, 2013 at 18:32
  • $\begingroup$ @Mr.Wizard Yes, it is faster, thanks. Don't you think that Sort shouldn't be so fast in comparison with Tally? I was surprised after first timmings. Well, I know both have to scan repeatedly but I thought Tally will be much better. $\endgroup$
    – Kuba
    Commented Aug 17, 2013 at 20:03
  • $\begingroup$ I don't know; sorts are often very fast so it does not surprise me. I am also not surprised that different algorithm behind Tally is faster in some cases and not in others. $\endgroup$
    – Mr.Wizard
    Commented Aug 17, 2013 at 20:05
4
$\begingroup$

No fresh methods of my own but some improvements:

Same idea as belisarius, slightly different formulation:

Cases[Tally @ #, {x_, 1} :> x] &

Shorter version of Kuba's method using the same formulation:

Cases[Split @ Sort @ list, {x_} :> x]

A variation of rm -rf's method:

unique[a_List] :=
 Module[{f, g},
   _g = True;
   f[x_] /; g[x] := g[x] = False;
   Scan[f, a];
   Select[a, g]
 ]

Timings

Supporting function and data:

SetAttributes[timeAvg, HoldFirst]
timeAvg[func_] := 
 Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 15}]

test = RandomInteger[#, 2 #] &[125000];

Tests on version 7:

Select[Tally@test, #[[2]] == 1 &][[All, 1]] // timeAvg
Cases[Tally@test, {x_, 1} :> x]             // timeAvg

0.1902

0.1498

Split@Sort@test /. {Repeated[n_, {2, Infinity}]} :> Sequence[] // Flatten // timeAvg
Cases[Split@Sort@test, {x_} :> x]                                         // timeAvg

0.1216

0.0688

onlyOnce[test] // timeAvg
unique[test]   // timeAvg

0.749

0.609

Improve this answer
$\endgroup$
3
  • $\begingroup$ You mean, like Mike's? $\endgroup$
    – rm -rf ♦
    Commented Aug 17, 2013 at 16:57
  • $\begingroup$ @rm-rf Well yes, but I prefer the rule form, at least visually. $\endgroup$
    – Mr.Wizard
    Commented Aug 17, 2013 at 16:59
  • $\begingroup$ @rm-rf Hopefully my extended answer is more pleasing to you. $\endgroup$
    – Mr.Wizard
    Commented Aug 17, 2013 at 20:34
2
$\begingroup$

Borrowing data from Dr. belisarius:

SeedRandom[1];
yourList = RandomInteger[10000, 60000];

Using GroupBy: (* Timing 0.0156 *)

GroupBy[yourList, Identity, Length] // 
 KeyValueMap[If[#2 == 1, #1, Nothing] &]

Using PositionIndex: (* Timing 0.0312 *)

PositionIndex[yourList] // 
 KeyValueMap[If[Length@#2 == 1, #1, Nothing] &]

{5966, 7867, 5862, 5476, 4417, 446, 971, 6670, 3464, 5600, 5429,
4649, 850, 7912, 6186, 6028, 1567, 7918, 6915, 8541, 4273, 5071,
2436, 9569, 8069, 3315, 3260, 2260, 2472, 1158, 8655, 2526, 8280,
9760, 5055, 404, 9398, 2787, 4347, 5772, 1989, 5910, 7944, 4030,
8199, 7206, 9212, 716, 3757, 7360, 8984, 5067, 7994, 5718, 7045,
3822, 2737, 8907, 502, 1968, 7669, 7673, 6120, 2729, 6801, 7136,
5000, 6306, 8508, 7839, 2026, 7875, 7368, 8385, 4127, 7745, 9691,
5284, 7607, 5964, 3504, 6701, 3433, 1910, 7754, 3969, 6592, 8153,
1503, 5955, 3374, 153, 1022, 6884, 3445, 6490, 4317, 8323, 4951,
3734, 8455, 3132, 2793, 9162, 7370, 4949, 2960, 7246, 8494, 1034,
5704, 7527, 6800, 1582, 1496, 9405, 6016, 2150, 2874, 9232, 6, 9862,
8743, 5682, 8578, 160, 8103, 9294, 8716, 7177, 4775, 7671, 7719,
1666, 1942, 6486, 1670, 7396, 1523, 2322, 2279, 1432, 1202, 9215,
3201, 9204, 2591, 3142, 6944, 9360, 2652, 4765, 9185, 3791, 5548,
8197, 5199}

Improve this answer
$\endgroup$
2
$\begingroup$ 
SeedRandom[1];
yourList = RandomInteger[10000, 60000];

Pick[Keys[#], Values[#], 1] &@Counts[yourList]

(* {5966, 7867, 5862, 5476, 4417,  446,  971, 6670, 3464, 5600, 5429, 
    4649,  850, 7912, 6186, 6028, 1567, 7918, 6915, 8541, 4273, 5071, 
    2436, 9569, 8069, 3315, 3260, 2260, 2472, 1158, 8655, 2526, 8280, 
    9760, 5055,  404, 9398, 2787, 4347, 5772, 1989, 5910, 7944, 4030, 
    8199, 7206, 9212,  716, 3757, 7360, 8984, 5067, 7994, 5718, 7045, 
    3822, 2737, 8907,  502, 1968, 7669, 7673, 6120, 2729, 6801, 7136, 
    5000, 6306, 8508, 7839, 2026, 7875, 7368, 8385, 4127, 7745, 9691, 
    5284, 7607, 5964, 3504, 6701, 3433, 1910, 7754, 3969, 6592, 8153, 
    1503, 5955, 3374,  153, 1022, 6884, 3445, 6490, 4317, 8323, 4951, 
    3734, 8455, 3132, 2793, 9162, 7370, 4949, 2960, 7246, 8494, 1034, 
    5704, 7527, 6800, 1582, 1496, 9405, 6016, 2150, 2874, 9232,    6,
    9862, 8743, 5682, 8578,  160, 8103, 9294, 8716, 7177, 4775, 7671,   
    7719, 1666, 1942, 6486, 1670, 7396, 1523, 2322, 2279, 1432, 1202,
    9215, 3201, 9204, 2591, 3142, 6944, 9360, 2652, 4765, 9185, 3791,
    5548, 8197, 5199} *}

A point-free version

Pick[Through[Sequence[Keys, Values][Counts[yourList]]], 1]


(* {5966, 7867, 5862, 5476, 4417,  446,  971, 6670, 3464, 5600, 5429, 
    4649,  850, 7912, 6186, 6028, 1567, 7918, 6915, 8541, 4273, 5071, 
    2436, 9569, 8069, 3315, 3260, 2260, 2472, 1158, 8655, 2526, 8280, 
    9760, 5055,  404, 9398, 2787, 4347, 5772, 1989, 5910, 7944, 4030, 
    8199, 7206, 9212,  716, 3757, 7360, 8984, 5067, 7994, 5718, 7045, 
    3822, 2737, 8907,  502, 1968, 7669, 7673, 6120, 2729, 6801, 7136, 
    5000, 6306, 8508, 7839, 2026, 7875, 7368, 8385, 4127, 7745, 9691, 
    5284, 7607, 5964, 3504, 6701, 3433, 1910, 7754, 3969, 6592, 8153, 
    1503, 5955, 3374,  153, 1022, 6884, 3445, 6490, 4317, 8323, 4951, 
    3734, 8455, 3132, 2793, 9162, 7370, 4949, 2960, 7246, 8494, 1034, 
    5704, 7527, 6800, 1582, 1496, 9405, 6016, 2150, 2874, 9232,    6,
    9862, 8743, 5682, 8578,  160, 8103, 9294, 8716, 7177, 4775, 7671,   
    7719, 1666, 1942, 6486, 1670, 7396, 1523, 2322, 2279, 1432, 1202,
    9215, 3201, 9204, 2591, 3142, 6944, 9360, 2652, 4765, 9185, 3791,
    5548, 8197, 5199} *}
Improve this answer
$\endgroup$
1
$\begingroup$ 
SeedRandom[1];

list = RandomInteger[10000, 60000];

Keys @ Select[Counts @ list, # == 1 &]

{5966, 7867, 5862, 5476, 4417, 446, 971, 6670, 3464, 5600, 5429,
4649, 850, 7912, 6186, 6028, 1567, 7918, 6915, 8541, 4273, 5071,
2436, 9569, 8069, 3315, 3260, 2260, 2472, 1158, 8655, 2526, 8280,
9760, 5055, 404, 9398, 2787, 4347, 5772, 1989, 5910, 7944, 4030,
8199, 7206, 9212, 716, 3757, 7360, 8984, 5067, 7994, 5718, 7045,
3822, 2737, 8907, 502, 1968, 7669, 7673, 6120, 2729, 6801, 7136,
5000, 6306, 8508, 7839, 2026, 7875, 7368, 8385, 4127, 7745, 9691,
5284, 7607, 5964, 3504, 6701, 3433, 1910, 7754, 3969, 6592, 8153,
1503, 5955, 3374, 153, 1022, 6884, 3445, 6490, 4317, 8323, 4951,
3734, 8455, 3132, 2793, 9162, 7370, 4949, 2960, 7246, 8494, 1034,
5704, 7527, 6800, 1582, 1496, 9405, 6016, 2150, 2874, 9232, 6, 9862,
8743, 5682, 8578, 160, 8103, 9294, 8716, 7177, 4775, 7671, 7719,
1666, 1942, 6486, 1670, 7396, 1523, 2322, 2279, 1432, 1202, 9215,
3201, 9204, 2591, 3142, 6944, 9360, 2652, 4765, 9185, 3791, 5548,
8197, 5199}

Improve this answer
$\endgroup$
1
$\begingroup$ 
SeedRandom[1];

list = RandomInteger[10000, 60000];

A variant using the third argument of GroupBy:

Catenate@GroupBy[list, Repeated, If[Length@# == 1, #, {}] &]

{5966, 7867, 5862, 5476, 4417, 446, 971, 6670, 3464, 5600, 5429,
4649, 850, 7912, 6186, 6028, 1567, 7918, 6915, 8541, 4273, 5071,
2436, 9569, 8069, 3315, 3260, 2260, 2472, 1158, 8655, 2526, 8280,
9760, 5055, 404, 9398, 2787, 4347, 5772, 1989, 5910, 7944, 4030,
8199, 7206, 9212, 716, 3757, 7360, 8984, 5067, 7994, 5718, 7045,
3822, 2737, 8907, 502, 1968, 7669, 7673, 6120, 2729, 6801, 7136,
5000, 6306, 8508, 7839, 2026, 7875, 7368, 8385, 4127, 7745, 9691,
5284, 7607, 5964, 3504, 6701, 3433, 1910, 7754, 3969, 6592, 8153,
1503, 5955, 3374, 153, 1022, 6884, 3445, 6490, 4317, 8323, 4951,
3734, 8455, 3132, 2793, 9162, 7370, 4949, 2960, 7246, 8494, 1034,
5704, 7527, 6800, 1582, 1496, 9405, 6016, 2150, 2874, 9232, 6, 9862,
8743, 5682, 8578, 160, 8103, 9294, 8716, 7177, 4775, 7671, 7719,
1666, 1942, 6486, 1670, 7396, 1523, 2322, 2279, 1432, 1202, 9215,
3201, 9204, 2591, 3142, 6944, 9360, 2652, 4765, 9185, 3791, 5548,
8197, 5199}
Improve this answer
$\endgroup$

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.