MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Faster alternative to AppendTo?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg102938] Re: [mg102886] Faster alternative to AppendTo?
  • From: Patrick Scheibe <pscheibe at trm.uni-leipzig.de>
  • Date: Wed, 2 Sep 2009 04:06:35 -0400 (EDT)
  • References: <200909010753.DAA18801@smc.vnet.net>

Hi,

yes there are better ways. First it is in most cases better to use
things like Nest, NestList, Table, Fold, Thread, Map, MapThread instead
of the imperative loops like Do, While. Here is your approach:

AbsoluteTiming[a = {};
 Do[k = m;
  orbit = {k};
  While[k > 1, AppendTo[orbit, k = g[k]]];
  AppendTo[a, orbit];, {m, 2, 30000}];]

Needs 36.375672 seconds on my system. If you just put the function g
into a pure function expression and use Table and NestWhileList you get

AbsoluteTiming[
 Table[NestWhileList[(If[EvenQ[#], #/2, 3 # + 1] &), 
    i, (# > 1 &)], {i, 2, 30000}];]

and this call needs 6.970204 sec here. In this case and on my system
with 4 cpu cores it is better to use all power, so I start 4 Kernels

LaunchKernels[4]

and evaluate it parallel

AbsoluteTiming[
 ParallelTable[
   NestWhileList[(If[EvenQ[#], #/2, 3 # + 1] &), i, (# > 1 &)], {i, 2,
     30000}];]

This needs only 3.684756 sec. Your original question with an upper limit
of 1000000 needs parallelized 133 seconds here.

Cheers
Patrick
 

On Tue, 2009-09-01 at 03:53 -0400, Dem_z 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.
> 



  • Prev by Date: Re: Question about SDTS format
  • Next by Date: Re: Faster alternative to AppendTo?
  • Previous by thread: Re: Faster alternative to AppendTo?
  • Next by thread: Re: Re: Faster alternative to AppendTo? --