# Filtering elements from a list that appear only once

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!

-
Here is one for fun, but it is no where as fast as Belisarius u = Union[lis]; Pick[u, Count[lis, #] & /@ u, 1]; –  Nasser Aug 17 '13 at 6:23
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 –  Nasser Aug 17 '13 at 6:25
Related: (18100) –  Mr.Wizard Aug 17 '13 at 15:50
Cases[Tally[yt], {a_, b_ /; b == 1} -> a] –  Rorschach Aug 18 '13 at 13:51

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.

-
Cases[Tally@yourList, {_, 1}][[All, 1]] is a bit faster for me. –  Mike Honeychurch Aug 17 '13 at 7:18
@MikeHoneychurch Thanks! Here too yours is a bit faster –  belisarius is forth Aug 17 '13 at 13:49

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.

-
The Listable attribute seems to interfere with this working with elements that are themselves lists. –  Michael E2 Aug 17 '13 at 15:51
@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 –  R. M. Aug 17 '13 at 16:59

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:

-
nice. But it slows down alot when the size of the list becomes large. see screen shot: !Mathematica graphics –  Nasser Aug 17 '13 at 7:39
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)"] –  Nasser Aug 17 '13 at 7:40
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. –  Nasser Aug 17 '13 at 10:17

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.

-
Nice idea. Shorter and faster: Cases[Split@Sort@list, {x_} :> x] –  Mr.Wizard Aug 17 '13 at 18:32
@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. –  Kuba Aug 17 '13 at 20:03
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. –  Mr.Wizard Aug 17 '13 at 20:05

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

-
You mean, like Mike's? –  R. M. Aug 17 '13 at 16:57
@rm-rf Well yes, but I prefer the rule form, at least visually. –  Mr.Wizard Aug 17 '13 at 16:59
@rm-rf Hopefully my extended answer is more pleasing to you. –  Mr.Wizard Aug 17 '13 at 20:34