# Why is this code in functional style is slower than procedural style?

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

-
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

## 1 Answer

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}
*)

-