Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I would like to understand the implementation that allows MemberQ and FreeQ to be as fast as they are.

I noticed this thanks to this fine answer.

I start with a list of True|False values:

lst = Insert[Table[True, {500000}], False, 499000];

It is not packed:

Developer`PackedArrayQ[lst]

False

I compare timings:

Scan[Identity, lst] ~Do~ {100} // Timing
MemberQ[lst, False] ~Do~ {100} // Timing
FreeQ[lst, False]   ~Do~ {100} // Timing

{4.93, Null}

{0.405, Null}

{0.25, Null}

What allows these functions to be more than an order of magnitude faster than simply Scanning the list?

share|improve this question
add comment

1 Answer

up vote 22 down vote accepted

What you observed seems to be an instance of the general behavior of the pattern-matcher when used with what I call "syntactic patterns" - patterns which only reflect the rigid structure of an expression, like e.g. _f. The speed-up with respect to the scanning is because the main evaluation loop is avoided - for FreeQ and MemberQ, the scannng is done all inside the pattern-matcher, which is lower-level compared to the main evaluator.

In this answer, and also here, there are some examples of this behavior, and further discussion. I think that a good rule of thumb is that you gain an orderor an order and a half of magnitude speed-up by clever use of syntactic patterns in place of top-level scanning code (pushing all work into the pattern-matcher), and you gain 2-3 orders of magnitude speed-up if you manage to recast the problem as a vectorized numerical problem on packed arrays.

share|improve this answer
    
Would you add some examples to this, please? –  Mr.Wizard Feb 6 '12 at 22:05
1  
@Spartacus I added links to two relevant questions / answers, containing some examples - will this satisfy you? I am afraid that otherwise right now I'd have to just copy those example and paste here, which doesn't make much sense IMO. –  Leonid Shifrin Feb 6 '12 at 22:12
1  
@Spartacus Most functions that do their job "in one go" (Union, Split, etc.) seems to be fast too. –  Szabolcs Feb 6 '12 at 22:13
    
@Szabolcs they are only fast with default comparison etc. functions, and that is also because they bypass the main evaluator with default functions (not to mention that Union switched to a pairwise comparisons for explicit comparison function, which leads to a quadratic-time algorithm, so Union, as well as DeleteDuplicates, are bad examples here. Sort and Split are good examples). This is probably what you meant by "in one go" - they don't have to oscillate between the kernel code and high-level evaluations. It is these oscillations that kill the performance. –  Leonid Shifrin Feb 6 '12 at 22:17
    
@Leonid, it is good. Szabolcs yes I suppose so. I guess I saw FreeQ / MemberQ (in the basic form) as more general than e.g. DeleteDuplicates (also in the basic form). Perhaps that was a mistake. I would not have posted this question except that it seemed like a slow day, but I did not honestly know the answer beforehand. –  Mr.Wizard Feb 6 '12 at 22:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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