How to remove duplicates from set of machine precision 2D points?

I have a set of 2D points with machine precision coordinates. I need to remove all duplicates. Performance is important.

This is the most obvious fast solution:

Union[points]


Unfortunately it turns out that unlike Equal and SameQ, Union has no tolerance for any difference with machine precision numbers, which makes it unusable for this purpose.

In[1]:=
a = 1.;
b = a + $MachineEpsilon; In[3]:= a == b Out[3]= True In[4]:= a === b Out[4]= True In[5]:= Union[{a, b}] Out[5]= {1., 1.}  Using the SameTest option of Union works, but it is not a good option because it makes the complexity$n^2$again. So what is the fastest way to get rid of duplicates while allowing for a tolerance of comparisons, and preferably being able to control it (Internal$EqualTolerance, Internal$SameQTolerance)? - A single argument DeleteDuplicates seems faster than single argument Union here – Rojo Mar 26 '13 at 2:03 @Rojo For a list of what size with how many duplicates? – Szabolcs Mar 26 '13 at 5:08 For the same test data of your answer. Union takes about 7 seconds and DeleteDuplicates slightly less than 3. So, 10000000 length and 3677844 duplicates this time – Rojo Mar 26 '13 at 5:21 Would you mind adding the test case in the question? For me, DeleteDuplicates is usually the fastest solution. There are some threads on mathgroup why this should be so, too... – Yves Klett Mar 26 '13 at 7:50 @Szabolcs a random comment - congratulations on getting the 1337th nice question badge! :) – Vincent Tjeng Mar 26 '13 at 15:28 4 Answers Here's another compiled implementation. It's only very slightly faster than the code of s0rce, which is due to this version making only one array access (rather than two) per inner loop iteration. It also uses the InternalBag, which may be advantageous for memory consumption in case there are many duplicates. It must be said that this is still not as fast as Union, but at least it acknowledges Internal$EqualTolerance while being faster than Split. The value of Internal$EqualTolerance is actually hard-coded into the bytecode on compilation, so it will be necessary to recompile if a different tolerance is required. compiledUnion = Compile[{{r, _Real, 2}}, Block[{ sorted = Sort[r], output, seen, current }, output = InternalBag[seen = First[sorted], 1]; Do[ If[i != seen, InternalStuffBag[output, seen = i, 1]], {i, sorted} ]; Partition[InternalBagPart[output, All], Length[seen]] ], RuntimeOptions -> {"Speed", "CompareWithTolerance" -> True}, CompilationTarget -> "C" ];  Test case, with the default value of Internal$EqualTolerance == 7 Log[2]/Log[10]:

compiledUnion[{
{1., 1., 1.}, {1. + $MachineEpsilon, 1., 1.}, {1., 1. +$MachineEpsilon, 1.},
{2., 1., 1.}
}]
(* -> {{1., 1., 1.}, {2., 1., 1.}} *)


Performance comparison, in ascending order of run-time:

r = RandomReal[1, {10000000, 2}];
r = RandomChoice[r, 10000000];

DeleteDuplicates[r]; (* 1.813 seconds; incorrect result (no tolerance) *)
DeleteDuplicates[r, Equal]; (* same timing and result--incorrect special-casing *)
Sort[r]; (* 4.297 seconds; base case for Union-like approaches *)
Union[r]; (* 4.609 seconds; incorrect result (no tolerance) *)

compiledUnion[r]; (* 5.875 seconds *)
With[{sorted = Sort[r]}, Pick[sorted, deleteDuplicatesC[sorted], 1]]; (* 6.109 seconds *)

DeleteDuplicates[r, Equal[##] &]; (* 294.8 days; unpacks *)

-
Also including the DeleteDuplicates timing would be great. – Yves Klett Mar 26 '13 at 16:31
@YvesKlett okay, I will add it later. However, it should be noted that DeleteDuplicates, while faster, does not actually produce the correct result. – Oleksandr R. Mar 26 '13 at 16:33
Oleksandr, any info on that would also be welcome. I did a run that matched the result of Union (after being sorted). – Yves Klett Mar 26 '13 at 16:50
@YvesKlett yes--contrast e.g. DeleteDuplicates[{1., 1. + $MachineEpsilon}, SameQ[##] &]. From this we can see that SameQ is special-cased internally by DeleteDuplicates, but not correctly so. – Oleksandr R. Mar 27 '13 at 7:51 @YvesKlett I added the DeleteDuplicates timings. I couldn't be bothered to wait for 9 months for the last one to finish, so that's an extrapolation. – Oleksandr R. Mar 27 '13 at 9:12 How about a compiled solution. I think this solves the transitivity issues with Split. deleteDuplicatesC = Compile[{{v, _Real, 2}}, Block[{i, len = Length[v], output = Table[1, {i, len}]}, Do[If[CompileGetElement[v, i] == CompileGetElement[v, i - 1], output[[i]] = 0], {i, 2, len}]; output], RuntimeOptions -> {"Speed", "CompareWithTolerance" -> True}, CompilationTarget -> "C"]; r = RandomReal[1, {10000000, 2}]; r = RandomChoice[r, 10000000]; selected = With[{sorted = Sort[r]}, Pick[sorted, deleteDuplicatesC[sorted], 1]]; // AbsoluteTiming (* {4.033231, Null} *)  Looks like it works: a = 1.; b = a +$MachineEpsilon;
test = {{a, a}, {b, b}, {b, a}, {a, b}};
Pick[test, deleteDuplicatesC[test], 1]

(* {{1., 1.}} *)

-
Compiled Equal is a call to InternalCompareNumeric. The tolerance is $InternalEqualTolerance (7 bits) if RuntimeOptions -> "CompareWithTolerance" -> True is set and zero otherwise. It seems like it would be possible to set the tolerance explicitly either by changing Internal$EqualTolerance before compiling the code or by editing the compiled bytecode directly. Note that you must manually set "CompareWithTolerance" -> True here because the default for RuntimeOptions -> "Speed" is "CompareWithTolerance" -> False! – Oleksandr R. Mar 25 '13 at 23:28
Thanks @OleksandrR. Once you posted your first comment I found in the docs that I couldn't specify "Speed" think this works for the example given now. – s0rce Mar 25 '13 at 23:39
You actually can specify RuntimeOptions -> {"Speed", "CompareWithTolerance" -> True}, FWIW. – Oleksandr R. Mar 25 '13 at 23:42

One possible solution is using Split, which obeys Internal$SameQTolerance r = RandomReal[1, {10000000, 2}]; r = RandomChoice[r, 10000000]; Split[Sort[r]][[All, 1]]; // AbsoluteTiming (* ==> {12.756712, Null} *)  This is about 3-4 times slower than Union: Union[r]; // AbsoluteTiming (* ==> {4.306363, Null} *)  - Since Split only compares adjacent elements, it is not obvious to me that one iteration will always be enough. You may need something like FixedPoint[Split[#][[All,1]]&,Sort[r]]. – Leonid Shifrin Mar 25 '13 at 22:00 @LeonidShifrin If I have {a,b,c,d,e} and a == band b==c, then Split will give {{a,b,c}, ...}, so it should be fine. The problem could be that it removes a bit too much because comparison with tolerance is not transitive, so it's possible that a==b and b==c but a != c. – Szabolcs Mar 25 '13 at 22:02 Actually, yes, I meant this non-transitivity, but did not make the right conclusion. – Leonid Shifrin Mar 25 '13 at 22:04 I might not get it, but for this one DeleteDuplicates is about 2.5 times faster than Union... – Yves Klett Mar 26 '13 at 7:55 @Szabolcs, Split has the disadvantage that it unpacks and thus needs more memory. Why exactly can you not use DeleteDuplicates? Seems faster. – user21 Mar 26 '13 at 11:09 Tally also obeys Internal$SameQTolerance:

a = RandomReal[{-1, 1}, 100000];

Tally[a][[All, 1]] // Length

100000

Internal\$SameQTolerance = 12.0;
Tally[a][[All, 1]] // Length

33818
`

I have used this to handle such problems in the past, but be aware that there remains a kind of instability.

-