8
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Szabolcs Oct 26 '18 at 10:43
  • $\begingroup$ 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. $\endgroup$ – Szabolcs Oct 26 '18 at 10:45
  • $\begingroup$ 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). $\endgroup$ – Sjoerd Smit Oct 26 '18 at 13:37
  • $\begingroup$ 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. $\endgroup$ – Sjoerd Smit Oct 26 '18 at 14:18
5
$\begingroup$

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}
$\endgroup$
  • $\begingroup$ This is actually pretty good! $\endgroup$ – Szabolcs Oct 29 '18 at 6:18
  • 1
    $\begingroup$ 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. $\endgroup$ – Szabolcs Oct 29 '18 at 6:41
5
$\begingroup$

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}

Adjusting the tolerance:

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.