# 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]},
Not[Or @@ MapThread[Equal, {Most[sorted], Rest[sorted]}]]
]


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. Oct 26, 2018 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. Oct 26, 2018 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). Oct 26, 2018 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. Oct 26, 2018 at 14:18 ## 2 Answers Is anything wrong with OrderedQ[Sort@N@data, Less]? SeedRandom 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! Oct 29, 2018 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. Oct 29, 2018 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 @ 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.