MathGroup Archive 2009

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

Search the Archive

Re: Faster alternative to AppendTo?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg102925] Re: Faster alternative to AppendTo?
  • From: Sjoerd <s.c.devries at xs4all.nl>
  • Date: Wed, 2 Sep 2009 04:04:15 -0400 (EDT)
  • References: <h7ijtl$ibb$1@smc.vnet.net>

AppendTo is not very efficient for long lists, because it has to make
a complete copy of the list involved. Try a construction like orbit
 = {orbit,k = g[k]} and orbit = Flatten[orbit] at the end when you're
finished.

This is more efficient because lists that are element of a list are
stored in this list as a pointer only. So copying the list that
contains them involves copying the pointer only, not all the stuff
that is in the sublist.

The code would loook like:

a = {};
Do[
 k = m;
 orbit = {k};
 While[k > 1, orbit = {orbit, k = g[k]}];
 a = {a, Flatten[orbit]},
 {m, 2, 1000000}
 ];
a = Flatten[a];

Cheers--Sjoerd


On Sep 1, 9: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.



  • Prev by Date: Re: Faster alternative to AppendTo?
  • Next by Date: Re: Faster alternative to AppendTo?
  • Previous by thread: Re: Faster alternative to AppendTo?
  • Next by thread: Re: Faster alternative to AppendTo?