17
$\begingroup$

I thought I had a firm understanding of the differences between Equal and SameQ, but this has me puzzled:

test = RandomInteger[100000000, 10000000];
{} == test // AbsoluteTiming
{} === test // AbsoluteTiming

== takes a chunk of time, === is "instant". I can't fathom why the first is not short-circuited pronto. Explanations?

$\endgroup$
6
  • 2
    $\begingroup$ === tests whether the two arguments are identical. That can be determined "instantaneously." == is a logical test, and for that to be computed, the large set of random integers must be produced, and that takes time. $\endgroup$ Mar 25, 2015 at 1:16
  • $\begingroup$ @DavidG.Stork: reference? "A large set of random integers must be produced...". Please elucidate... $\endgroup$
    – ciao
    Mar 25, 2015 at 3:03
  • $\begingroup$ Note: the "big-list" tag was created for a different purpose as noted in its tag wiki. I removed it from this question. Given the confusion it seems to cause it may be removed entirely in the future. $\endgroup$
    – Mr.Wizard
    Mar 25, 2015 at 6:42
  • $\begingroup$ @rasher Your code requires the production of one million random integers. The simple logical test == must explore the full set. After all, suppose the rhs contained a very complicated logical operation on many values to test whether it was equal to the lhs. That would take time. There's no simple way for Mathematica to "know ahead of time" whether the rhs might contain such a function. $\endgroup$ Mar 25, 2015 at 14:34
  • $\begingroup$ @David Pardon me, but that is not correct. Please see the addendum to my answer. $\endgroup$
    – Mr.Wizard
    Mar 25, 2015 at 16:36

1 Answer 1

20
+500
$\begingroup$

Unless both lists given to Equal are packed arrays Equal will first unpack. Unfortunately for this case {} is not a packable expression, therefore list == {} will always unpack list, assuming it starts packed. That unpacking takes time:

test = RandomInteger[100000000, 10000000];

Developer`FromPackedArray[test]; // AbsoluteTiming
{0.207012, Null}

Turning On "Packing" messages illuminates this behavior:

On["Packing"]

a = Range[5];
b = a + 1;

a == b;

(No unpacking message)

a == {1, 2, 3, 4, 5};  (* direct List input is unpacked *)

Developer`FromPackedArray::punpack: Unpacking array with dimensions {5} in call to Equal. >>

a == {};

Developer`FromPackedArray::punpack: Unpacking array with dimensions {5} in call to Equal. >>

This edge case is not a serious limitation as one can use === as already noted.


David G. Stork asserted:

Your code requires the production of one million random integers. The simple logical test == must explore the full set. After all, suppose the rhs contained a very complicated logical operation on many values to test whether it was equal to the lhs. That would take time. There's no simple way for Mathematica to "know ahead of time" whether the rhs might contain such a function.

We can demonstrate that this is materially false by unpacking test in advance:

unpacked = List @@ test;  (* unpacks *)

{} == unpacked // AbsoluteTiming
{0., False}

Equal is not attempting an element-wise equivalency check here; it is sufficient that the two lists are of different length to return False:

short = Most @ test;  (* remains packed *)

short == test // AbsoluteTiming
{0., False}

Arguably it is a bug that this length-check is not performed before unpacking.

$\endgroup$
2
  • $\begingroup$ Ah, masterful! Thanks for illumination, as always my wizardy friend! +1, o/c, +10 if I could. $\endgroup$
    – ciao
    Mar 25, 2015 at 6:43
  • $\begingroup$ @rasher My pleasure. :-) $\endgroup$
    – Mr.Wizard
    Mar 25, 2015 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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