Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #39117 > unrolled thread

Python 3.3 vs. MSDOS Basic

Back to article view | Back to comp.lang.python

Contents

  Python 3.3 vs. MSDOS Basic John Immarino <johimm@gmail.com> - 2013-02-18 11:13 -0800
    Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-19 08:55 +1100
    Re: Python 3.3 vs. MSDOS Basic Ian Kelly <ian.g.kelly@gmail.com> - 2013-02-18 14:54 -0700
      Re: Python 3.3 vs. MSDOS Basic Tim Daneliuk <tundra@tundraware.com> - 2013-02-19 08:46 -0600
        Re: Python 3.3 vs. MSDOS Basic Ian Kelly <ian.g.kelly@gmail.com> - 2013-02-19 11:31 -0700
          Re: Python 3.3 vs. MSDOS Basic Tim Daneliuk <tundra@tundraware.com> - 2013-02-20 08:21 -0600
            Re: Python 3.3 vs. MSDOS Basic Ian Kelly <ian.g.kelly@gmail.com> - 2013-02-20 11:38 -0700
              Re: Python 3.3 vs. MSDOS Basic Tim Daneliuk <tundra@tundraware.com> - 2013-02-20 16:49 -0600
                Re: Python 3.3 vs. MSDOS Basic Tim Daneliuk <tundra@tundraware.com> - 2013-02-20 16:59 -0600
        Re: Python 3.3 vs. MSDOS Basic Serhiy Storchaka <storchaka@gmail.com> - 2013-02-19 22:28 +0200
        Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-20 08:39 +1100
          Re: Python 3.3 vs. MSDOS Basic Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2013-02-20 18:32 +1300
    Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-19 08:56 +1100
    Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-19 08:58 +1100
      Re: Python 3.3 vs. MSDOS Basic John Immarino <johimm@gmail.com> - 2013-02-18 17:39 -0800
        Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-19 14:01 +1100
          Re: Python 3.3 vs. MSDOS Basic Nick Mellor <thebalancepro@gmail.com> - 2013-02-18 20:17 -0800
          Re: Python 3.3 vs. MSDOS Basic Nick Mellor <thebalancepro@gmail.com> - 2013-02-18 20:17 -0800
      Re: Python 3.3 vs. MSDOS Basic John Immarino <johimm@gmail.com> - 2013-02-18 17:39 -0800
        Re: Python 3.3 vs. MSDOS Basic Neil Cerutti <neilc@norwich.edu> - 2013-02-20 17:06 +0000
    Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-19 09:01 +1100
    Re: Python 3.3 vs. MSDOS Basic Ian Kelly <ian.g.kelly@gmail.com> - 2013-02-18 15:15 -0700
    Re: Python 3.3 vs. MSDOS Basic Alexander Blinne <news@blinne.net> - 2013-02-19 01:11 +0100
    Re: Python 3.3 vs. MSDOS Basic Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2013-02-18 19:36 -0500
      Re: Python 3.3 vs. MSDOS Basic John Immarino <johimm@gmail.com> - 2013-02-18 17:47 -0800
      Re: Python 3.3 vs. MSDOS Basic John Immarino <johimm@gmail.com> - 2013-02-18 17:47 -0800
    Re: Python 3.3 vs. MSDOS Basic Terry Reedy <tjreedy@udel.edu> - 2013-02-18 19:50 -0500
      Re: Python 3.3 vs. MSDOS Basic Piet van Oostrum <piet@vanoostrum.org> - 2013-02-19 12:42 +0100
        Re: Python 3.3 vs. MSDOS Basic Alexander Blinne <news@blinne.net> - 2013-02-20 01:23 +0100
          Re: Python 3.3 vs. MSDOS Basic Ian Kelly <ian.g.kelly@gmail.com> - 2013-02-19 18:04 -0700
    Re: Python 3.3 vs. MSDOS Basic Terry Reedy <tjreedy@udel.edu> - 2013-02-19 00:28 -0500
    Re: Python 3.3 vs. MSDOS Basic Anssi Saari <as@sci.fi> - 2013-02-19 12:52 +0200
    Re: Python 3.3 vs. MSDOS Basic Serhiy Storchaka <storchaka@gmail.com> - 2013-02-19 13:13 +0200
    Re: Python 3.3 vs. MSDOS Basic Olive <diolu.remove_this_part@bigfoot.com> - 2013-02-19 15:02 +0100

Page 1 of 2  [1] 2  Next page →

#39117 — Python 3.3 vs. MSDOS Basic

I coded a Python solution for Problem #14 on the Project Euler website. I was very surprised to find that it took 107 sec. to run even though it's a pretty simple program.  I also coded an equivalent solution for the problem in the old MSDOS basic. (That's the 16 bit app of 1980s vintage.)  It ran in 56 sec. Is there a flaw in my coding, or is Python really this slow in this particular application. MSDOS Basic usually runs at a snails pace compared to Python.

Below is the problem and the code:



The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.


max=0
m=0
while m<=1000000:
    m+=1
    count=0
    n=m
    while n!=1:
        count+=1
        if n%2==0:
            n=n//2
        else:
            n=3*n+1
    if count>max:
         max=count
         num=m
print(num,max)

[toc] | [next] | [standalone]

#39131

On Tue, Feb 19, 2013 at 6:13 AM, John Immarino <johimm@gmail.com> wrote:
> I coded a Python solution for Problem #14 on the Project Euler website. I was very surprised to find that it took 107 sec. to run even though it's a pretty simple program.  I also coded an equivalent solution for the problem in the old MSDOS basic. (That's the 16 bit app of 1980s vintage.)  It ran in 56 sec. Is there a flaw in my coding, or is Python really this slow in this particular application. MSDOS Basic usually runs at a snails pace compared to Python.

BASIC does a lot less. If you wrote an 8086 assembly language
interpreter in Python, it'd run fairly slowly too :) Python isn't
really the world's best language for number crunching inside a machine
word; though if this were a major project, I would recommend looking
into Cython, as it lets you translate a few critical portions of your
code to C while leaving the rest in Python.

In order to get some useful stats, I added a little timing code to
your original; on my Windows XP laptop, running Python 3.3, your
version took 212.64 seconds to get to a result (namely, 837799 with a
count of 524).

Here's how I'd code it:

import time
start=time.time()
max=0
for m in range(1,1000001):
	n=m
	count=0
	while n>1:
		if n%2: n=3*n+1
		else: n//=2
		count+=1
	if count>max: max,num=count,m
	if not m&16383: print("->",m,count)
print(num,max)
print(time.time()-start)

(You'll see the same timing information that I added to yours. It adds
immeasurably to the run-time, and gives some early idea of how it's
going.)

Running under Python 2.6, both your version and mine take about 90
seconds to run. But under Python 3.3, where (among other things)
range() yields values lazily, my version is significantly faster than
yours. BUT! Both versions, under 3.3, are significantly *slower* than
under 2.6. My first thought is that it's because Py2 has different
types for 'int' and 'long', and Py3 doesn't (effectively, everything's
a long), so I added an L suffix to every number and ran each of them
under 2.6 again. Seems that was the bulk of the difference, though not
all.

Pythonistas, does this count as a regression, or is Python
sufficiently "not a number crunching language" that we don't care?

(range = my code, as above; while = original version with a C-style
loop counter)
range py3: 171.07846403121948
while py3: 212.64104509353638
range py2: 87.859000206
while py2: 86.4059998989
range py2 longs: 190.530999899
while py2 longs: 176.125999928

For comparison purposes, I also coded up the equivalent in Pike.
Pike's a very similar language to Python, but with a C-like syntax,
and certain optimizations - including, significantly to this exercise,
an integer type that sits within a machine word if it can (though
it'll happily go arbitrary precision when it's needed to). It pretends
to the programmer that it's a Py3-style "everything's an int", but
underneath, functions more like Py2 with separate short and long
types. The result: 22.649 seconds to reach the same conclusion.

How long did your BASIC version take, and how long did the Python
version on the same hardware?

This sort of pure number crunching isn't really where a modern high
level language shines. You'll come to *really* appreciate Python as
soon as you start working with huge arrays, dictionaries, etc. This is
a job for C, really.

ChrisA

[toc] | [prev] | [next] | [standalone]

#39132

On Mon, Feb 18, 2013 at 12:13 PM, John Immarino <johimm@gmail.com> wrote:
> I coded a Python solution for Problem #14 on the Project Euler website. I was very surprised to find that it took 107 sec. to run even though it's a pretty simple program.  I also coded an equivalent solution for the problem in the old MSDOS basic. (That's the 16 bit app of 1980s vintage.)  It ran in 56 sec. Is there a flaw in my coding, or is Python really this slow in this particular application. MSDOS Basic usually runs at a snails pace compared to Python.

Well, I don't see anything that looks especially slow in that code,
but the algorithm that you're using is not very efficient.  I rewrote
it using dynamic programming (details left as an exercise), which got
the runtime down to about 4 seconds.

[toc] | [prev] | [next] | [standalone]

#39227

On 02/18/2013 03:54 PM, Ian Kelly wrote:
> On Mon, Feb 18, 2013 at 12:13 PM, John Immarino <johimm@gmail.com> wrote:
>> I coded a Python solution for Problem #14 on the Project Euler website. I was very surprised to find that it took 107 sec. to run even though it's a pretty simple program.  I also coded an equivalent solution for the problem in the old MSDOS basic. (That's the 16 bit app of 1980s vintage.)  It ran in 56 sec. Is there a flaw in my coding, or is Python really this slow in this particular application. MSDOS Basic usually runs at a snails pace compared to Python.
>
> Well, I don't see anything that looks especially slow in that code,
> but the algorithm that you're using is not very efficient.  I rewrote
> it using dynamic programming (details left as an exercise), which got
> the runtime down to about 4 seconds.
>

Are you sure you wouldn't like to share with the class?  I'd be interested
in seeing your approach...



-- 
----------------------------------------------------------------------------
Tim Daneliuk     tundra@tundraware.com
PGP Key:         http://www.tundraware.com/PGP/

[toc] | [prev] | [next] | [standalone]

#39269

On Tue, Feb 19, 2013 at 7:46 AM, Tim Daneliuk <tundra@tundraware.com> wrote:
> Are you sure you wouldn't like to share with the class?  I'd be interested
> in seeing your approach...

Very well:

def collatz(n, memo):
    if n not in memo:
        if n % 2 == 0:
            next_n = n // 2
        else:
            next_n = 3 * n + 1
        memo[n] = collatz(next_n, memo) + 1
    return memo[n]

def run_collatz(upper):
    table = {1: 0}
    max_n = max(range(1, upper), key=lambda n: collatz(n, table))
    return max_n, table[max_n]

>>> run_collatz(1000000)
(837799, 524)

It could certainly be optimized further, but at about 4 seconds it's
already fast enough for most purposes.

[toc] | [prev] | [next] | [standalone]

#39362

On 02/19/2013 12:31 PM, Ian Kelly wrote:
> On Tue, Feb 19, 2013 at 7:46 AM, Tim Daneliuk <tundra@tundraware.com> wrote:
>> Are you sure you wouldn't like to share with the class?  I'd be interested
>> in seeing your approach...
>
> Very well:
>
> def collatz(n, memo):
>      if n not in memo:
>          if n % 2 == 0:
>              next_n = n // 2
>          else:
>              next_n = 3 * n + 1
>          memo[n] = collatz(next_n, memo) + 1
>      return memo[n]
>
> def run_collatz(upper):
>      table = {1: 0}
>      max_n = max(range(1, upper), key=lambda n: collatz(n, table))
>      return max_n, table[max_n]
>
>>>> run_collatz(1000000)
> (837799, 524)
>
> It could certainly be optimized further, but at about 4 seconds it's
> already fast enough for most purposes.
>

Thanks.  I was specifically curious about your use of dynamic programming.
What about this algorithm makes it particularly an example of this?  Is
it your use of memoization or something other than this?



-- 
-----------------------------------------------------------------------
Tim Daneliuk

[toc] | [prev] | [next] | [standalone]

#39373

On Wed, Feb 20, 2013 at 7:21 AM, Tim Daneliuk <tundra@tundraware.com> wrote:
> Thanks.  I was specifically curious about your use of dynamic programming.
> What about this algorithm makes it particularly an example of this?  Is
> it your use of memoization or something other than this?

In retrospect, I was using the term overly broadly, as the algorithm
does not really use dynamic programming.  I should have written
"memoization" instead.

[toc] | [prev] | [next] | [standalone]

#39383

On 02/20/2013 12:38 PM, Ian Kelly wrote:
> On Wed, Feb 20, 2013 at 7:21 AM, Tim Daneliuk <tundra@tundraware.com> wrote:
>> Thanks.  I was specifically curious about your use of dynamic programming.
>> What about this algorithm makes it particularly an example of this?  Is
>> it your use of memoization or something other than this?
>
> In retrospect, I was using the term overly broadly, as the algorithm
> does not really use dynamic programming.  I should have written
> "memoization" instead.
>

That's why I asked.  Dynamic Programming itself is a sort of wide
term and I was curious which version of it you found useful.

Thanks for the discussion.

-- 
----------------------------------------------------------------------------
Tim Daneliuk     tundra@tundraware.com
PGP Key:         http://www.tundraware.com/PGP/

[toc] | [prev] | [next] | [standalone]

#39384

On 02/20/2013 04:49 PM, Tim Daneliuk wrote:
> On 02/20/2013 12:38 PM, Ian Kelly wrote:
>> On Wed, Feb 20, 2013 at 7:21 AM, Tim Daneliuk <tundra@tundraware.com> wrote:
>>> Thanks.  I was specifically curious about your use of dynamic programming.
>>> What about this algorithm makes it particularly an example of this?  Is
>>> it your use of memoization or something other than this?
>>
>> In retrospect, I was using the term overly broadly, as the algorithm
>> does not really use dynamic programming.  I should have written
>> "memoization" instead.
>>
>
> That's why I asked.  Dynamic Programming itself is a sort of wide
> term and I was curious which version of it you found useful.
>
> Thanks for the discussion.
>

One other point of interest:  The formal notion of Dynamic Program
is to decompose problems into potentially overlapping subproblems
and only solve each subproblem once, and reapply the results as
needed.  Hence, your use of memoization is indeed an example of
Dynamic Programming.

Notwithstanding the formal ideas of a Dynamic Program, my interest in this
context really had more to do with the word "dynamic".  Languages
like Python are "dynamic" in the sense that a running program can
actually generate new code as it runs.  This makes it possible to
write adaptive programs that morph as they run, typically in response
to their inputs and state.***  I was thinking that perhaps
you'd done something in this sense of the word in solving the OPs
problem.  


*** To be sure, you can do this in assembler too, it's just much
more convenient in dynamic languages like Python.

-- 
----------------------------------------------------------------------------
Tim Daneliuk     tundra@tundraware.com
PGP Key:         http://www.tundraware.com/PGP/

[toc] | [prev] | [next] | [standalone]

#39271

On 19.02.13 20:31, Ian Kelly wrote:
> On Tue, Feb 19, 2013 at 7:46 AM, Tim Daneliuk <tundra@tundraware.com> wrote:
>> Are you sure you wouldn't like to share with the class?  I'd be interested
>> in seeing your approach...
>
> Very well:
>
> def collatz(n, memo):
>      if n not in memo:
>          if n % 2 == 0:
>              next_n = n // 2
>          else:
>              next_n = 3 * n + 1
>          memo[n] = collatz(next_n, memo) + 1
>      return memo[n]
>
> def run_collatz(upper):
>      table = {1: 0}
>      max_n = max(range(1, upper), key=lambda n: collatz(n, table))
>      return max_n, table[max_n]
>
>>>> run_collatz(1000000)
> (837799, 524)
>
> It could certainly be optimized further, but at about 4 seconds it's
> already fast enough for most purposes.

10-15% faster:

def f(M):
     def g(n, cache = {1: 0}):
         if n in cache:
             return cache[n]
         if n % 2:
             m = 3 * n + 1
         else:
             m = n // 2
         cache[n] = count = g(m) + 1
         return count
     num = max(range(2, M + 1), key=g)
     return num, g(num)

print(*f(1000000))

[toc] | [prev] | [next] | [standalone]

#39280

On Wed, Feb 20, 2013 at 7:28 AM, Serhiy Storchaka <storchaka@gmail.com> wrote:
> 10-15% faster:
> ... num = max(range(2, M + 1), key=g) ...

Yes, but 20-30% less clear and readable. Though I do like the idea of
playing this code in the key of G Major.

ChrisA

[toc] | [prev] | [next] | [standalone]

#39315

Chris Angelico wrote:
> On Wed, Feb 20, 2013 at 7:28 AM, Serhiy Storchaka <storchaka@gmail.com> wrote:
> 
>>10-15% faster:
>>... num = max(range(2, M + 1), key=g) ...
> 
> Yes, but 20-30% less clear and readable. Though I do like the idea of
> playing this code in the key of G Major.

On the SmartStupid, presumably.

http://wordsmith.org/board/ubbthreads.php?ubb=showflat&Number=101906

-- 
Greg

[toc] | [prev] | [next] | [standalone]

#39133

On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico <rosuav@gmail.com> wrote:
> How long did your BASIC version take, and how long did the Python
> version on the same hardware?

Oops, my bad, you already posted the figures :) And I forgot to ask:
Which Python version didyou use?

ChrisA

[toc] | [prev] | [next] | [standalone]

#39134

On Tue, Feb 19, 2013 at 8:56 AM, Chris Angelico <rosuav@gmail.com> wrote:
> On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico <rosuav@gmail.com> wrote:
>> How long did your BASIC version take, and how long did the Python
>> version on the same hardware?
>
> Oops, my bad, you already posted the figures :) And I forgot to ask:
> Which Python version didyou use?
>
> ChrisA

Doh. I'm having a great day of not reading properly, today. (I blame
checking mail on the bus, it took me over an hour to read this one
message and I'd forgotten the subject line by the time I got to the
end.) Python 3.3, right there in the header. Disregard me!

ChrisA

[toc] | [prev] | [next] | [standalone]

#39160

On Monday, February 18, 2013 2:58:57 PM UTC-7, Chris Angelico wrote:
> On Tue, Feb 19, 2013 at 8:56 AM, Chris Angelico <rosuav@gmail.com> wrote:
> 
> > On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico <rosuav@gmail.com> wrote:
> 
> >> How long did your BASIC version take, and how long did the Python
> 
> >> version on the same hardware?
> 
> >
> 
> > Oops, my bad, you already posted the figures :) And I forgot to ask:
> 
> > Which Python version didyou use?
> 
> >
> 
> > ChrisA
> 
> 
> 
> Doh. I'm having a great day of not reading properly, today. (I blame
> 
> checking mail on the bus, it took me over an hour to read this one
> 
> message and I'd forgotten the subject line by the time I got to the
> 
> end.) Python 3.3, right there in the header. Disregard me!
> 
> 
> 
> ChrisA

Thanks,Chris. I'm a newbie to Python and didn't realize that it's not as good at number crunching as some of the others. It does seem to do better than Basic with numbers in lists as opposed to arrays in Basic.

[toc] | [prev] | [next] | [standalone]

#39176

On Tue, Feb 19, 2013 at 12:39 PM, John Immarino <johimm@gmail.com> wrote:
> On Monday, February 18, 2013 2:58:57 PM UTC-7, Chris Angelico wrote:
>> On Tue, Feb 19, 2013 at 8:56 AM, Chris Angelico <rosuav@gmail.com> wrote:
>>
>> > On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico <rosuav@gmail.com> wrote:
>>
>> >> How long did your BASIC version take, and how long did the Python
>>
>> >> version on the same hardware?
>>
>> >
>>
>> > Oops, my bad, you already posted the figures :) And I forgot to ask:
>>
>> > Which Python version didyou use?
>>
>> >
>>
>> > ChrisA
>>
>>
>>
>> Doh. I'm having a great day of not reading properly, today. (I blame
>>
>> checking mail on the bus, it took me over an hour to read this one
>>
>> message and I'd forgotten the subject line by the time I got to the
>>
>> end.) Python 3.3, right there in the header. Disregard me!
>>
>>
>>
>> ChrisA
>
> Thanks,Chris. I'm a newbie to Python and didn't realize that it's not as good at number crunching as some of the others. It does seem to do better than Basic with numbers in lists as opposed to arrays in Basic.

Yes, Python is excellent at data handling. I'll cheerfully use Python
to manipulate huge lists or arrays, and its performance at that is
usually well within the "good enough" range (for instance, anything
that manipulates the file system will be waiting on my disks, not on
Python). It's an excellent tool in the toolkit, just not the one
solution to everything. (Nothing's that!)

ChrisA

[toc] | [prev] | [next] | [standalone]

#39182

Hi John,

Thanks for the problem. I've been writing Python for about 4 years now and am beginning to feel like I'm writing much better Python code.

Python does fine on this problem if you play to its strengths. The following uses dictionary lookups to store previously computed sequence lengths, thus saving a lot of work. The problem is very "sparse", i.e. there are huge gaps between numbers that are actually used in the solution, making dictionaries a better fit than lists.

This code crosses the line in under 3s on a 64-bit laptop. MS-DOS BASIC anyone? :-)

I tried precomputing powers of 2 and multiples of 2, but to my surprise it made very little difference to timings. Even though precomputing n//2 is fast, I think again this is because the problem is sparse and the time the computer saves is not offset by the cost of precomputing many multiples of 2 that are never needed.

Best wishes,

Nick

And the winner is 837799 with sequence length 524
Time (s):  2.924168109893799
Sequence is:
[837799, 2513398, 1256699, 3770098, 1885049, 5655148, 2827574, 1413787, 4241362, 2120681, 6362044, 3181022, 1590511, 4771534, 2385767, 7157302, 3578651, 10735954, 5367977, 16103932, 8051966, 4025983, 12077950, 6038975, 18116926, 9058463, 27175390, 13587695, 40763086, 20381543, 61144630, 30572315, 91716946, 45858473, 137575420, 68787710, 34393855, 103181566, 51590783, 154772350, 77386175, 232158526, 116079263, 348237790, 174118895, 522356686, 261178343, 783535030, 391767515, 1175302546, 587651273, 1762953820, 881476910, 440738455, 1322215366, 661107683, 1983323050, 991661525, 2974984576, 1487492288, 743746144, 371873072, 185936536, 92968268, 46484134, 23242067, 69726202, 34863101, 104589304, 52294652, 26147326, 13073663, 39220990, 19610495, 58831486, 29415743, 88247230, 44123615, 132370846, 66185423, 198556270, 99278135, 297834406, 148917203, 446751610, 223375805, 670127416, 335063708, 167531854, 83765927, 251297782, 125648891, 376946674, 188473337, 565420012, 282710006, 141355003, 424065010, 212032505, 636097516, 318048758, 159024379, 477073138, 238536569, 715609708, 357804854, 178902427, 536707282, 268353641, 805060924, 402530462, 201265231, 603795694, 301897847, 905693542, 452846771, 1358540314, 679270157, 2037810472, 1018905236, 509452618, 254726309, 764178928, 382089464, 191044732, 95522366, 47761183, 143283550, 71641775, 214925326, 107462663, 322387990, 161193995, 483581986, 241790993, 725372980, 362686490, 181343245, 544029736, 272014868, 136007434, 68003717, 204011152, 102005576, 51002788, 25501394, 12750697, 38252092, 19126046, 9563023, 28689070, 14344535, 43033606, 21516803, 64550410, 32275205, 96825616, 48412808, 24206404, 12103202, 6051601, 18154804, 9077402, 4538701, 13616104, 6808052, 3404026, 1702013, 5106040, 2553020, 1276510, 638255, 1914766, 957383, 2872150, 1436075, 4308226, 2154113, 6462340, 3231170, 1615585, 4846756, 2423378, 1211689, 3635068, 1817534, 908767, 2726302, 1363151, 4089454, 2044727, 6134182, 3067091, 9201274, 4600637, 13801912, 6900956, 3450478, 1725239, 5175718, 2587859, 7763578, 3881789, 11645368, 5822684, 2911342, 1455671, 4367014, 2183507, 6550522, 3275261, 9825784, 4912892, 2456446, 1228223, 3684670, 1842335, 5527006, 2763503, 8290510, 4145255, 12435766, 6217883, 18653650, 9326825, 27980476, 13990238, 6995119, 20985358, 10492679, 31478038, 15739019, 47217058, 23608529, 70825588, 35412794, 17706397, 53119192, 26559596, 13279798, 6639899, 19919698, 9959849, 29879548, 14939774, 7469887, 22409662, 11204831, 33614494, 16807247, 50421742, 25210871, 75632614, 37816307, 113448922, 56724461, 170173384, 85086692, 42543346, 21271673, 63815020, 31907510, 15953755, 47861266, 23930633, 71791900, 35895950, 17947975, 53843926, 26921963, 80765890, 40382945, 121148836, 60574418, 30287209, 90861628, 45430814, 22715407, 68146222, 34073111, 102219334, 51109667, 153329002, 76664501, 229993504, 114996752, 57498376, 28749188, 14374594, 7187297, 21561892, 10780946, 5390473, 16171420, 8085710, 4042855, 12128566, 6064283, 18192850, 9096425, 27289276, 13644638, 6822319, 20466958, 10233479, 30700438, 15350219, 46050658, 23025329, 69075988, 34537994, 17268997, 51806992, 25903496, 12951748, 6475874, 3237937, 9713812, 4856906, 2428453, 7285360, 3642680, 1821340, 910670, 455335, 1366006, 683003, 2049010, 1024505, 3073516, 1536758, 768379, 2305138, 1152569, 3457708, 1728854, 864427, 2593282, 1296641, 3889924, 1944962, 972481, 2917444, 1458722, 729361, 2188084, 1094042, 547021, 1641064, 820532, 410266, 205133, 615400, 307700, 153850, 76925, 230776, 115388, 57694, 28847, 86542, 43271, 129814, 64907, 194722, 97361, 292084, 146042, 73021, 219064, 109532, 54766, 27383, 82150, 41075, 123226, 61613, 184840, 92420, 46210, 23105, 69316, 34658, 17329, 51988, 25994, 12997, 38992, 19496, 9748, 4874, 2437, 7312, 3656, 1828, 914, 457, 1372, 686, 343, 1030, 515, 1546, 773, 2320, 1160, 580, 290, 145, 436, 218, 109, 328, 164, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Sparsity calculations...
Computed sequence lengths 2168611
Largest term:  56991483520
Test range:  1 1000000
Biggest gap:  4508198208
Sparsity: 0.00175%


# If True, will precompute powers of 2 and multiples of 2
# in practice this made little difference on 64-bit hardware
OPTIMISE = True

def build_sequence(n):
    """return sequence as a list given the starting number
    Uses the trail of data left by compute_sequence"""
    tmp = compute_sequence(n)
    sequence = []
    while n:
        sequence.append(n)
        n = next_num[n]
    return sequence

def compute_sequence(n):
    """lazily compute sequences for Collatz problem"""
    if n in seqlength:
        return seqlength[n]
    if n not in next_num:
        # NOTE: (some) evens are pre-computed
        next_num[n] = 3 * n + 1 if n % 2 else n // 2
    seqlength[n] = 1 + compute_sequence(next_num[n])
    return seqlength[n]

import time
start = time.time()

highest_number = int(1000000)
highest_term = highest_number * 3 + 1
highest_term += 1 if highest_term % 2 else 0

next_num = {2:1}
if OPTIMISE:
    # quickly pre-compute (some of) the evens (used for n = n//2 if n is even)
    # how many should we precompute? Any mathematicians?
    doubles = range(2, highest_term, 2)
    numbers = range(1, highest_term//2)
    next_num = dict(zip(doubles, numbers))
# mark 1 as the end-point of any sequence
next_num[1] = 0

# initialise the sequence lengths
seqlength = {}
seqlength[1] = 0
seqlength[2] = 1
if OPTIMISE:
    # powers of 2 are trivial: 2**n has sequence length n
    n = 2
    pwr = 4
    while pwr < highest_term:
        seqlength[pwr] = n
        pwr = pwr * 2
        n += 1
max_length = 0
for n in range(3, highest_number + 1):
    length = compute_sequence(n)
    if length > max_length:
        max_length = length
        winning_number = n
print ("And the winner is {0} with sequence length {1}".format(winning_number, max_length))
end = time.time()
print ("Time (s): ", (end-start))

print ("Sequence is:")
print (build_sequence(winning_number))

# Sparsity calculation
sorted_seqlengths = sorted(seqlength.keys())
print ("Sparsity calculations...")
print ("Computed sequence lengths", len(seqlength))
largest_term = sorted_seqlengths[-1]
print ("Largest term: ", largest_term)
print ("Test range: ", 1, highest_number)
gaps = (second - first for first, second in zip(sorted_seqlengths[0:-1], sorted_seqlengths[1:]))
biggest_gap = 0
for n in gaps:
    if biggest_gap < n:
        biggest_gap = n
print ("Biggest gap: ", n)
print ("Sparsity: {0:.5f}%".format(highest_number / largest_term * 100))


On Tuesday, 19 February 2013 14:01:31 UTC+11, Chris Angelico  wrote:
> On Tue, Feb 19, 2013 at 12:39 PM, John Immarino <johimm@gmail.com> wrote:
> 
> > On Monday, February 18, 2013 2:58:57 PM UTC-7, Chris Angelico wrote:
> 
> >> On Tue, Feb 19, 2013 at 8:56 AM, Chris Angelico <rosuav@gmail.com> wrote:
> 
> >>
> 
> >> > On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico <rosuav@gmail.com> wrote:
> 
> >>
> 
> >> >> How long did your BASIC version take, and how long did the Python
> 
> >>
> 
> >> >> version on the same hardware?
> 
> >>
> 
> >> >
> 
> >>
> 
> >> > Oops, my bad, you already posted the figures :) And I forgot to ask:
> 
> >>
> 
> >> > Which Python version didyou use?
> 
> >>
> 
> >> >
> 
> >>
> 
> >> > ChrisA
> 
> >>
> 
> >>
> 
> >>
> 
> >> Doh. I'm having a great day of not reading properly, today. (I blame
> 
> >>
> 
> >> checking mail on the bus, it took me over an hour to read this one
> 
> >>
> 
> >> message and I'd forgotten the subject line by the time I got to the
> 
> >>
> 
> >> end.) Python 3.3, right there in the header. Disregard me!
> 
> >>
> 
> >>
> 
> >>
> 
> >> ChrisA
> 
> >
> 
> > Thanks,Chris. I'm a newbie to Python and didn't realize that it's not as good at number crunching as some of the others. It does seem to do better than Basic with numbers in lists as opposed to arrays in Basic.
> 
> 
> 
> Yes, Python is excellent at data handling. I'll cheerfully use Python
> 
> to manipulate huge lists or arrays, and its performance at that is
> 
> usually well within the "good enough" range (for instance, anything
> 
> that manipulates the file system will be waiting on my disks, not on
> 
> Python). It's an excellent tool in the toolkit, just not the one
> 
> solution to everything. (Nothing's that!)
> 
> 
> 
> ChrisA

[toc] | [prev] | [next] | [standalone]

#39183

Hi John,

Thanks for the problem. I've been writing Python for about 4 years now and am beginning to feel like I'm writing much better Python code.

Python does fine on this problem if you play to its strengths. The following uses dictionary lookups to store previously computed sequence lengths, thus saving a lot of work. The problem is very "sparse", i.e. there are huge gaps between numbers that are actually used in the solution, making dictionaries a better fit than lists.

This code crosses the line in under 3s on a 64-bit laptop. MS-DOS BASIC anyone? :-)

I tried precomputing powers of 2 and multiples of 2, but to my surprise it made very little difference to timings. Even though precomputing n//2 is fast, I think again this is because the problem is sparse and the time the computer saves is not offset by the cost of precomputing many multiples of 2 that are never needed.

Best wishes,

Nick

And the winner is 837799 with sequence length 524
Time (s):  2.924168109893799
Sequence is:
[837799, 2513398, 1256699, 3770098, 1885049, 5655148, 2827574, 1413787, 4241362, 2120681, 6362044, 3181022, 1590511, 4771534, 2385767, 7157302, 3578651, 10735954, 5367977, 16103932, 8051966, 4025983, 12077950, 6038975, 18116926, 9058463, 27175390, 13587695, 40763086, 20381543, 61144630, 30572315, 91716946, 45858473, 137575420, 68787710, 34393855, 103181566, 51590783, 154772350, 77386175, 232158526, 116079263, 348237790, 174118895, 522356686, 261178343, 783535030, 391767515, 1175302546, 587651273, 1762953820, 881476910, 440738455, 1322215366, 661107683, 1983323050, 991661525, 2974984576, 1487492288, 743746144, 371873072, 185936536, 92968268, 46484134, 23242067, 69726202, 34863101, 104589304, 52294652, 26147326, 13073663, 39220990, 19610495, 58831486, 29415743, 88247230, 44123615, 132370846, 66185423, 198556270, 99278135, 297834406, 148917203, 446751610, 223375805, 670127416, 335063708, 167531854, 83765927, 251297782, 125648891, 376946674, 188473337, 565420012, 282710006, 141355003, 424065010, 212032505, 636097516, 318048758, 159024379, 477073138, 238536569, 715609708, 357804854, 178902427, 536707282, 268353641, 805060924, 402530462, 201265231, 603795694, 301897847, 905693542, 452846771, 1358540314, 679270157, 2037810472, 1018905236, 509452618, 254726309, 764178928, 382089464, 191044732, 95522366, 47761183, 143283550, 71641775, 214925326, 107462663, 322387990, 161193995, 483581986, 241790993, 725372980, 362686490, 181343245, 544029736, 272014868, 136007434, 68003717, 204011152, 102005576, 51002788, 25501394, 12750697, 38252092, 19126046, 9563023, 28689070, 14344535, 43033606, 21516803, 64550410, 32275205, 96825616, 48412808, 24206404, 12103202, 6051601, 18154804, 9077402, 4538701, 13616104, 6808052, 3404026, 1702013, 5106040, 2553020, 1276510, 638255, 1914766, 957383, 2872150, 1436075, 4308226, 2154113, 6462340, 3231170, 1615585, 4846756, 2423378, 1211689, 3635068, 1817534, 908767, 2726302, 1363151, 4089454, 2044727, 6134182, 3067091, 9201274, 4600637, 13801912, 6900956, 3450478, 1725239, 5175718, 2587859, 7763578, 3881789, 11645368, 5822684, 2911342, 1455671, 4367014, 2183507, 6550522, 3275261, 9825784, 4912892, 2456446, 1228223, 3684670, 1842335, 5527006, 2763503, 8290510, 4145255, 12435766, 6217883, 18653650, 9326825, 27980476, 13990238, 6995119, 20985358, 10492679, 31478038, 15739019, 47217058, 23608529, 70825588, 35412794, 17706397, 53119192, 26559596, 13279798, 6639899, 19919698, 9959849, 29879548, 14939774, 7469887, 22409662, 11204831, 33614494, 16807247, 50421742, 25210871, 75632614, 37816307, 113448922, 56724461, 170173384, 85086692, 42543346, 21271673, 63815020, 31907510, 15953755, 47861266, 23930633, 71791900, 35895950, 17947975, 53843926, 26921963, 80765890, 40382945, 121148836, 60574418, 30287209, 90861628, 45430814, 22715407, 68146222, 34073111, 102219334, 51109667, 153329002, 76664501, 229993504, 114996752, 57498376, 28749188, 14374594, 7187297, 21561892, 10780946, 5390473, 16171420, 8085710, 4042855, 12128566, 6064283, 18192850, 9096425, 27289276, 13644638, 6822319, 20466958, 10233479, 30700438, 15350219, 46050658, 23025329, 69075988, 34537994, 17268997, 51806992, 25903496, 12951748, 6475874, 3237937, 9713812, 4856906, 2428453, 7285360, 3642680, 1821340, 910670, 455335, 1366006, 683003, 2049010, 1024505, 3073516, 1536758, 768379, 2305138, 1152569, 3457708, 1728854, 864427, 2593282, 1296641, 3889924, 1944962, 972481, 2917444, 1458722, 729361, 2188084, 1094042, 547021, 1641064, 820532, 410266, 205133, 615400, 307700, 153850, 76925, 230776, 115388, 57694, 28847, 86542, 43271, 129814, 64907, 194722, 97361, 292084, 146042, 73021, 219064, 109532, 54766, 27383, 82150, 41075, 123226, 61613, 184840, 92420, 46210, 23105, 69316, 34658, 17329, 51988, 25994, 12997, 38992, 19496, 9748, 4874, 2437, 7312, 3656, 1828, 914, 457, 1372, 686, 343, 1030, 515, 1546, 773, 2320, 1160, 580, 290, 145, 436, 218, 109, 328, 164, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Sparsity calculations...
Computed sequence lengths 2168611
Largest term:  56991483520
Test range:  1 1000000
Biggest gap:  4508198208
Sparsity: 0.00175%


# If True, will precompute powers of 2 and multiples of 2
# in practice this made little difference on 64-bit hardware
OPTIMISE = True

def build_sequence(n):
    """return sequence as a list given the starting number
    Uses the trail of data left by compute_sequence"""
    tmp = compute_sequence(n)
    sequence = []
    while n:
        sequence.append(n)
        n = next_num[n]
    return sequence

def compute_sequence(n):
    """lazily compute sequences for Collatz problem"""
    if n in seqlength:
        return seqlength[n]
    if n not in next_num:
        # NOTE: (some) evens are pre-computed
        next_num[n] = 3 * n + 1 if n % 2 else n // 2
    seqlength[n] = 1 + compute_sequence(next_num[n])
    return seqlength[n]

import time
start = time.time()

highest_number = int(1000000)
highest_term = highest_number * 3 + 1
highest_term += 1 if highest_term % 2 else 0

next_num = {2:1}
if OPTIMISE:
    # quickly pre-compute (some of) the evens (used for n = n//2 if n is even)
    # how many should we precompute? Any mathematicians?
    doubles = range(2, highest_term, 2)
    numbers = range(1, highest_term//2)
    next_num = dict(zip(doubles, numbers))
# mark 1 as the end-point of any sequence
next_num[1] = 0

# initialise the sequence lengths
seqlength = {}
seqlength[1] = 0
seqlength[2] = 1
if OPTIMISE:
    # powers of 2 are trivial: 2**n has sequence length n
    n = 2
    pwr = 4
    while pwr < highest_term:
        seqlength[pwr] = n
        pwr = pwr * 2
        n += 1
max_length = 0
for n in range(3, highest_number + 1):
    length = compute_sequence(n)
    if length > max_length:
        max_length = length
        winning_number = n
print ("And the winner is {0} with sequence length {1}".format(winning_number, max_length))
end = time.time()
print ("Time (s): ", (end-start))

print ("Sequence is:")
print (build_sequence(winning_number))

# Sparsity calculation
sorted_seqlengths = sorted(seqlength.keys())
print ("Sparsity calculations...")
print ("Computed sequence lengths", len(seqlength))
largest_term = sorted_seqlengths[-1]
print ("Largest term: ", largest_term)
print ("Test range: ", 1, highest_number)
gaps = (second - first for first, second in zip(sorted_seqlengths[0:-1], sorted_seqlengths[1:]))
biggest_gap = 0
for n in gaps:
    if biggest_gap < n:
        biggest_gap = n
print ("Biggest gap: ", n)
print ("Sparsity: {0:.5f}%".format(highest_number / largest_term * 100))


On Tuesday, 19 February 2013 14:01:31 UTC+11, Chris Angelico  wrote:
> On Tue, Feb 19, 2013 at 12:39 PM, John Immarino <johimm@gmail.com> wrote:
> 
> > On Monday, February 18, 2013 2:58:57 PM UTC-7, Chris Angelico wrote:
> 
> >> On Tue, Feb 19, 2013 at 8:56 AM, Chris Angelico <rosuav@gmail.com> wrote:
> 
> >>
> 
> >> > On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico <rosuav@gmail.com> wrote:
> 
> >>
> 
> >> >> How long did your BASIC version take, and how long did the Python
> 
> >>
> 
> >> >> version on the same hardware?
> 
> >>
> 
> >> >
> 
> >>
> 
> >> > Oops, my bad, you already posted the figures :) And I forgot to ask:
> 
> >>
> 
> >> > Which Python version didyou use?
> 
> >>
> 
> >> >
> 
> >>
> 
> >> > ChrisA
> 
> >>
> 
> >>
> 
> >>
> 
> >> Doh. I'm having a great day of not reading properly, today. (I blame
> 
> >>
> 
> >> checking mail on the bus, it took me over an hour to read this one
> 
> >>
> 
> >> message and I'd forgotten the subject line by the time I got to the
> 
> >>
> 
> >> end.) Python 3.3, right there in the header. Disregard me!
> 
> >>
> 
> >>
> 
> >>
> 
> >> ChrisA
> 
> >
> 
> > Thanks,Chris. I'm a newbie to Python and didn't realize that it's not as good at number crunching as some of the others. It does seem to do better than Basic with numbers in lists as opposed to arrays in Basic.
> 
> 
> 
> Yes, Python is excellent at data handling. I'll cheerfully use Python
> 
> to manipulate huge lists or arrays, and its performance at that is
> 
> usually well within the "good enough" range (for instance, anything
> 
> that manipulates the file system will be waiting on my disks, not on
> 
> Python). It's an excellent tool in the toolkit, just not the one
> 
> solution to everything. (Nothing's that!)
> 
> 
> 
> ChrisA

[toc] | [prev] | [next] | [standalone]

#39170

On Monday, February 18, 2013 2:58:57 PM UTC-7, Chris Angelico wrote:
> On Tue, Feb 19, 2013 at 8:56 AM, Chris Angelico <rosuav@gmail.com> wrote:
> 
> > On Tue, Feb 19, 2013 at 8:55 AM, Chris Angelico <rosuav@gmail.com> wrote:
> 
> >> How long did your BASIC version take, and how long did the Python
> 
> >> version on the same hardware?
> 
> >
> 
> > Oops, my bad, you already posted the figures :) And I forgot to ask:
> 
> > Which Python version didyou use?
> 
> >
> 
> > ChrisA
> 
> 
> 
> Doh. I'm having a great day of not reading properly, today. (I blame
> 
> checking mail on the bus, it took me over an hour to read this one
> 
> message and I'd forgotten the subject line by the time I got to the
> 
> end.) Python 3.3, right there in the header. Disregard me!
> 
> 
> 
> ChrisA

Thanks,Chris. I'm a newbie to Python and didn't realize that it's not as good at number crunching as some of the others. It does seem to do better than Basic with numbers in lists as opposed to arrays in Basic.

[toc] | [prev] | [next] | [standalone]

#39367

On 2013-02-19, John Immarino <johimm@gmail.com> wrote:
> Thanks,Chris. I'm a newbie to Python and didn't realize that
> it's not as good at number crunching as some of the others. It
> does seem to do better than Basic with numbers in lists as
> opposed to arrays in Basic.

Python is good enough at number crunching for Project Euler. Its
data types and library make a few of the problems otherwise
uninteresting, in fact.

Sometimes, as in this case, memoization is good enough (a quick
look at my own code for this shows that's what I did, too). But
when it's a particularly good example of a Project Euler problem,
you'll need to do some mathematical analysis to improve your
approach, first.

But yeah, do not get in the habit of comparing your times to,
say, C++ programs. ;)

-- 
Neil Cerutti

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web