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 know that in Mathematica a functional programming style is often more efficient than procedural style programming using For loops. But the code shown below seems to be an exception, How to explain this?

del[ls_, k_] := Delete[ls, List /@ Range[k, Length@ls, k]]

max = 10^5;
r1 = Range[max];
For[i = 2, i <= Length[r1], i++, r1 = del[r1, i]]; // Timing

r2 = Range[max];
Do[r2 = del[r2, i], {i, 2, Length@r2}]; // Timing

r3 = Fold[del, Range[max], Range[2, max]]; // Timing

r1 == r2 == r3

Out:

{0.031200, Null}

{0.889206, Null}

{0.577204, Null}

True
share|improve this question
    
What if you try Catch[Fold[If[#2 < Length[#1], Drop[#1, {#2, Length[#1], #2}], Throw[#1]] &, Range[max], Range[2, max]]]? –  J. M. May 8 '13 at 4:33
    
@J.M. Nice, but a little complicated. –  expression May 8 '13 at 7:12
    
That can be decomposed, if you're so inclined: del[ls_, k_Integer] := Drop[ls, {k, Length[ls], k}]; Catch[Fold[If[#2 < Length[#1], del[#1, #2], Throw[#1]] &, Range[max], Range[2, max]]] –  J. M. May 8 '13 at 8:07
add comment

1 Answer

up vote 10 down vote accepted

In the first example, the list r1 is getting shorter each iteration, resulting in much fewer iterations overall:

max = 10^5;
r1 = Range[max];
c1 = 0;    
Timing[
 For[i = 2, i <= Length[r1], i++, c1++; r1 = del[r1, i]]; c1]

(*
==> {0.012426, 356}
*)

r2 = Range[max];
c2 = 0;
Timing[Do[c2++; r2 = del[r2, i], {i, 2, Length@r2}]; c2]

(*
==> {0.348965, 99999}
*)

c3 = 0;
Timing[r3 = Fold[(c3++; del[##]) &, Range[max], Range[2, max]]; c3]

(*
==> {0.417146, 99999}
*)
share|improve this answer
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.