3
$\begingroup$

I am using

NestWhileList[
  f[#, elems]&, 
  pairs, 
  Length[#1]<Length[#2]&, 
  2, Infinity, -1
 ]

to generate all suitable subsets from pairs of elems;

f takes a list of subsets of length n and combines it with elems in order to pick appropriate subsets of length n+1. The process continues until the Length of the generated subsets doesn't change.

(note: each subset is of Length n-it is what Subsets[elems, {n}] would return if you could supply an additional function to select admissible subsets according to given criteria)

My question has to do with selecting an efficient stopping criterion.

If I am not mistaken, using NestWhileList with the same arguments and replacing the test with UnsameQ is equivalent to using FixedPointList.

If lists are somehow aware of their Length then using a criterion using lengths of successive lists may be efficient instead of checking for ===;

however that may not be the case if testing for === is somehow aware of the structure of the FullForm of the expressions and 'sameness' is equally efficiently evaluated.

So, the question is if using Length is more efficient than using ===, in the context of the discussion above.

$\endgroup$
  • 3
    $\begingroup$ Can't you just... you know... try it? :) I think a timing comparison of trying the two approaches would be much more substantial than people on this site arguing about it, no? $\endgroup$ – Marius Ladegård Meyer Feb 7 at 13:05
  • $\begingroup$ @MariusLadegårdMeyer sure, I did actually time it; on my limited test cases Length was a winner by a small margin; I was hopping there was a consensus on the issue since my function generates lists that get big really fast; any possible efficiency gains are welcome; issues that may be slowing down code are not visible at first glance (eg PackedArrays here and here) and simply timing it doesn't always settle it $\endgroup$ – yosimitsu kodanuri Feb 7 at 20:20
6
$\begingroup$

Yes, it is faster to use comparison by Length instead of UnsameQ, in particular, when two lists indeed coincide. (If the list do not coincide, methods like comparing few bits or hashing may provide an inexpensive test with a high probability of short-circuit.) Indeed, the internal data structures behind List contain a field that stores their Length; so Length[a] == Length[b] is an $O(1)$ operation. But comparison of whole lists of length $n$ should be $O(n)$ operations. Here is a timing experiment that illustrates what I said:

n = 10000000;
a = RandomSample[Range[1, n], n];
b = a;
b[[1]] = b[[1]];

a === b // RepeatedTiming
Length[a] == Length[b] // RepeatedTiming

{0.010, True}

{5.3*10^-7, True}

You might wonder why I used b[[1]] = b[[1]]; above. If I hadn't used it, SameQ would be at least as fast as the Length method! The reason is that due to lazy copying, the execution of b = a; itself will never kick off a copy operation. Instead, the pointer in the MTensor belonging to b in the C++-backend is simply set to the pointer of the MTensor of a. So SameQ has only to compare their pointers without even touching the memory that stores the actual values of the lists. Hence in this case, SameQ boils down to comparing of a single (long unsigned) integer, thus an $O(1)$ operation.

But b[[1]] = b[[1]]; manipulates b so that a separate copy has to be made in storage. Now the MTensor of b points to another memory location. Hence, SameQ has really to access all the memory for the entries of a and b which is obviously an $O(n)$ operation.

Hint

Never ever use a == {} in order to test whether a list a is empty. Because with a from above, we have:

a == {} // RepeatedTiming
a === {} // RepeatedTiming
Length[a] == 0 // RepeatedTiming

{0.42, False}

{1.8*10^-7, False}

{3.5*10^-7, False}

$\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.