4
$\begingroup$

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
$\endgroup$
  • $\begingroup$ What if you try Catch[Fold[If[#2 < Length[#1], Drop[#1, {#2, Length[#1], #2}], Throw[#1]] &, Range[max], Range[2, max]]]? $\endgroup$ – J. M. will be back soon May 8 '13 at 4:33
  • $\begingroup$ @J.M. Nice, but a little complicated. $\endgroup$ – expression May 8 '13 at 7:12
  • $\begingroup$ 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]]] $\endgroup$ – J. M. will be back soon May 8 '13 at 8:07
11
$\begingroup$

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}
*)
$\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.