I have an ordered list of $N$ numbers, and I want to find out whether adjacent numbers are SameQ
or not, returning a list of 0s and 1s of length $N-1$. One approach is something like:
pairwiseBoole[y_] := Boole[SameQ @@@ Transpose[{Rest[y],Most[y]}]]
but this is extremely slow:
data = Union @ RandomReal[E + {0, 10^-7}, 10^6];
Length[data]
res = pairwiseBoole[data]; //AbsoluteTiming
Count[res, 0]
997747
{0.640326, Null}
993254
If I naively compile this, I can increase the speed by an order of magnitude, but I think it should be possible to write a function that is still faster, since:
Rest[y] - Most[y]; //AbsoluteTiming
{0.009215, Null}
and SameQ
is true as long as they only differ in their last binary digit (note that one might need to know about Internal`$SameQTolerance
).
How can I perform this computation as quickly as possible?
Update
Based on the answers/comments, I should have provided a better example, one where the fact that SameQ
uses a relative and not absolute tolerance plays a more important role. So, the kind of data I'm using is more similar to the following (corrected to output a packed array thanks to @Szabolcs):
data = Developer`ToPackedArray @ Union[
RandomChoice[100 Sin[Subdivide[0, 7, 40]], 10^6] +
RandomReal[{0, 10^-7}, 10^6]
];
And, it is vital that the output is the same as what one would get using pairwise SameQ
on list elements. Only results that produce the same output as pairwiseBoole are acceptable.
My compiled version
By the way, here is the compiled version that I had come up with:
pairwiseBooleC = Compile[{{x,_Real,1}},
Table[Boole[SameQ[x[[i]], x[[i+1]]]], {i, Length[x]-1}]
];
and a comparison with my pairwiseBoole
:
r1 = pairwiseBoole[data]; //RepeatedTiming
r2 = pairwiseBooleC[data]; //RepeatedTiming
r1 === r2
{0.63, Null}
{0.042, Null}
True
Some background, I am writing a RegionMember
type function that can handle multiple regions, returning which region a point belongs to. In order to get edge cases correct it is vital that I use something equivalent to SameQ
when comparing adjacent elements.
Boole[Developer`PartitionMap[Apply[SameQ], y, 2, 1]]
? $\endgroup$BoolEval[Rest[data] == Most[data]]
, with minimal performance degradation. Also, I just realize that the difference based method can't easily reproduce the tolerance behaviour ofSameQ
(because it uses relative, not absolute tolerances). $\endgroup$==
or>
). Mathematica cannot do this. The algorithmically equivalent constructs (e.g.MapThread[compare, {arr1, arr2}]
) are much slower in Mathematica. A workaround is to translate the comparisons into vector arithmetic (Subtract
,Unitize
,UnitStep
, etc.), which is just as fast in Mathematica as in MATLAB/numpy. Unfortunately, such code is both hard to read and write. My BoolEval package tries to fix this ... $\endgroup$==
,>
, and translating that into arithmetic transparently. But your example shows that arithmetic isn't really a good replacement for such tasks: it changes the tolerance behaviour. I think the lack of vectorized comparisons is a significant handicap for Mathematica. Years ago I sent suggestions to support to improve this situation, but I don't really have any hope that anything will happen ... $\endgroup$data
you provided is not packed, which causesRest[data] - Most[data];
to be slower thanpairwiseBooleC
on this. (This really confused me.) This gives a marginal speedup compared topairwiseBooleC
:cf = Compile[{{x, _Real}, {y, _Real}}, Boole[x === y], RuntimeAttributes -> {Listable}, Parallelization -> True]; cf[Rest[data], Most[data]]
$\endgroup$