# Robust DuplicateFreeQ for numerical data

I am looking for a fast and robust DuplicateFreeQ equivalent for numerical data. Floating point numbers should normally be compared with some tolerance, as Equal and SameQ do.

Has anyone implemented such a function and considered all the edge cases?

Here's a slow but simple implementation to get the ball rolling:

numericDuplicateFreeQ[data_] :=
With[{sorted = Sort@N[data]},
]


The function should be capable of at least the following:

• If there are any two 'equal' list elements, return False. Otherwise, return True.
• Work with any ArrayQ[#, _, NumericQ]& data (although a version that only works with lists of numbers is already useful).
• Compare like Equal does (or in a similar way), with adjustable tolerance (see Internal$EqualTolerance). • It must work with at least machine precision numbers. Ideally, it would work with any exact, arbitrary precision or machine precision numbers, but this may be more difficult to implement. • Why is this difficult? The data may contain exact or floating point numbers, equality needs to be handled properly. The data may contain machine precision or arbitrary precision numbers. – Szabolcs Oct 26 '18 at 10:43 • Even if we restrict the data to machine precision floating point only, we need to compute some sort of relative difference. There is an edge case for near-zero numbers. Better, we need to compute a difference in ulps. Doing that with good performance is not trivial. – Szabolcs Oct 26 '18 at 10:45 • I haven't done any performance tests, but maybe something that uses LengthWhile and Sort would work? E.g., Block[{x}, LengthWhile[Sort[data], Not[TrueQ[x == (x = #)]] &]] (and then testing if it's the same length as data, of course). – Sjoerd Smit Oct 26 '18 at 13:37 • Never mind, LengthWhile is actually slower than MapThread here. I can beat MapThread by about a factor of 2 on machine precision arrays with either Split or a compiled Do loop (using Catch/Throw or Break to abort once a duplicate is found). That's the best I managed. A rather substantial portion of the time goes into sorting the list, but I don't know of a good method that can skip the sorting step. – Sjoerd Smit Oct 26 '18 at 14:18 ## 2 Answers Is anything wrong with OrderedQ[Sort@N@data, Less]? SeedRandom[0] data = RandomReal[1, 10^6]; Internal$EqualTolerance = 2;
OrderedQ[Sort@N@data, Less] // RepeatedTiming

Internal\$EqualTolerance = 7;
OrderedQ[Sort@N@data, Less] // RepeatedTiming

{0.3581, True}

{0.1785, False}

• This is actually pretty good! – Szabolcs Oct 29 '18 at 6:18
• One issue is that it only uses machine precision. Now that is not an issue for the specific application I had in mind, but it would be nice to handle arbitrary precision numbers too. That can actually be done by removing N and replacing Less with TrueQ @* Less, at the cost of a 2x slowdown. The assumption is still that we have NumericQ data. – Szabolcs Oct 29 '18 at 6:41

This has 0 problems, but for vectors maybe you could do something like:

dupFreeQ[d_, tol_] := With[{s = Sort @ N @ d},
FreeQ[0] @ Chop[Rest[s]/Most[s] - 1, tol]
]


Example:

data = RandomReal[{1, 1 + 10^-3}, 10^6];

dupFreeQ[data, 10^-14] //AbsoluteTiming
numericDuplicateFreeQ[data] //AbsoluteTiming


{0.246441, False}

{0.525652, False}

dupFreeQ[data, 5 10^-16] //AbsoluteTiming


{0.274373, True}

Another idea is to use Nearest:

Nearest[N @ data -> "Index", data] //OrderedQ //AbsoluteTiming


{0.278319, True}

vs:

data = RandomReal[{1, 1 + 10^-5}, 10^6];

Nearest[N @ data -> "Index", data] //OrderedQ //AbsoluteTiming
`

{0.519298, False}

although this will be slow if there are lots of duplicates, and there is no tolerance control. On the other hand, I think this kind of approach will be more robust for higher order arrays.