Re: Faster alternative to AppendTo?
- To: mathgroup at smc.vnet.net
- Subject: [mg102924] Re: Faster alternative to AppendTo?
- From: Ray Koopman <koopman at sfu.ca>
- Date: Wed, 2 Sep 2009 04:04:04 -0400 (EDT)
- References: <h7ijtl$ibb$1@smc.vnet.net>
g[n_] := If[Mod[n, 2] == 0, n/2, 3 n + 1]
Timing[a = {}; Do[k = m; orbit = {k};
While[k > 1, AppendTo[orbit, k = g[k]]];
AppendTo[a, orbit], {m,2,10^4}]]
{25.11 Second, Null}
InputForm[ gc = Compile[{{m,_Integer}}, NestWhileList[If[EvenQ
[#],Quotient[#,2],3#+1]&, m, #>1&]] ]
CompiledFunction[{_Integer}, {{2, 0, 0}, {2, 1, 0}},
{2, 7, 2, 0, 1}, {{1, 5}, {92, 2, 1}, {4, 0, 2},
{93, 2, 1, 0, 0, 2}, {9, 0, 2}, {9, 2, 3}, {4, 1, 4},
{48, 4, 3, 0}, {41, 0, 20}, {9, 2, 3}, {4, 2, 4},
{89, 271, 2, 0, 3, 2, 0, 4, 2, 0, 5}, {4, 0, 4}, {44, 5, 4, 1},
{41, 1, 5}, {4, 2, 5}, {89, 262, 2, 0, 3, 2, 0, 5, 2, 0, 4},
{9, 4, 6}, {42, 6}, {4, 3, 5}, {28, 5, 3, 5}, {4, 1, 6},
{24, 5, 6, 5}, {9, 5, 6}, {9, 6, 2}, {4, 0, 6},
{93, 2, 1, 0, 2, 6}, {42, -22}, {94, 2, 1, 2, -1, 0}, {2}},
Function[{m}, NestWhileList[If[EvenQ[#1], Quotient[#1, 2],
3*#1 + 1] & , m, #1 > 1 & ]], Evaluate]
Timing[a == Table[ gc[m], {m,2,10^4}]]
{1.03 Second, True}
Note on compiling: It's a good idea to always look at the InputForm
of a compiled function, to make sure that there are only numbers in
the body of the function, before the final Function[...],Evaluate].
If there are any words then the compiled code will usually be slower
than the uncompiled code.
On Sep 1, 12:53 am, Dem_z <de... at hotmail.com> wrote:
> Hey, sorry I'm really new. I only started using mathematica recently, so I'm not that savvy.
>
> Anyways, I wrote some code to calculate (and store) the orbits around numbers in the Collatz conjecture.
>
> "Take any whole number n greater than 0. If n is even, we halve it (n/2), else we do "triple plus one" and get 3n+1. The conjecture is that for all numbers this process converges to 1. "
> http://en.wikipedia.org/wiki/Collatz_conjecture
>
> (*If there's no remainder, divides by 2, else multiply by 3 add 1*)
> g[n_] := If[Mod[n, 2] == 0, n/2, 3 n + 1]
>
> (*creates an empty list a. Loops and appends the k's orbit into variable "orbit", which then appends to variable "a" after the While loop is completed. New m, sets new k, which restarts the While loop again.*)
> a = {};
> Do[
> k = m;
> orbit = {k};
> While[k > 1, AppendTo[orbit, k = g[k]]];
> AppendTo[a, orbit];
> , {m, 2,1000000}];
>
> Anyways it seems that the AppendTo function gets exponentially slower, as you throw more data into it. Is there a way to make this more efficient? To calculate a million points takes days with this method.