Ruby and Python (was Re: Why is Python a good first scripting language?)

[Michael Hudson]

"Patrick Ellis" <pellis at tampabay.rr.com> writes:

> Note that removing the primes = None line results in settling around 8.9
> instead of 8.6. My guess is this has to do with allocating and deallocating
> millions of integer objects to put in the primes list.

And that WinME's memory management appears to suck harder than vacuum.
I haven't tried this, but I bet you wouldn't see that on almost any
other operating system (except possible classic macos).

> The 0.3 sec difference is how long it takes to deallocate the
> returned list. Python 2.3 does memory more efficiently and is why it
> runs faster.

Also, it does let Win32's malloc get near enough to the action to get
confused.

> I came up with a new version that uses the Numeric package. It is
> algorithmically identical, just with a few implementation changes.
> 
> def sieve(n):
>     if n < 2:
>         return []
>     limit = (int(math.sqrt(n)) / 2) + 1
>     primes = Numeric.arrayrange(1, n+1, 2)
>     n = len(primes)
>     for p in primes[1:limit]:
>         if p:
>             # note that p*p is odd, so no need to subtract 1
>             # before shifting right -- same thing in the end
>             primes[(p*p)>>1::p] = 0
>     return list(Numeric.nonzero(primes))
> 
> The same test as above results in:
> 
> Primes took   1.870 seconds
> Primes took   1.810 seconds
> Primes took   1.760 seconds
> Primes took   1.810 seconds
> Primes took   1.870 seconds
> Primes took   1.750 seconds
> Primes took   1.820 seconds
> Primes took   1.810 seconds
> Primes took   1.810 seconds
> Primes took   1.810 seconds

Impressive!

> Because it uses arrays that store the integers directly, instead of many
> tiny integer objects, it doesn't have the memory management overhead and
> resulting increasing runtime. The biggest speed increase is replacing the
> inner loop with an assignment statement to a slice (which doesn't work with
> lists).

It does in Python 2.3 though, and attempting to exploit that found a
bug in the extended slice support (that I wrote, oops).  Anyway, it
was fairly easy to fix, so you've helped Python development with this
post!  Bet you didn't expect that.

Helps the speed a bit, but not enormously (20% or so).

Cheers,
M.

-- 
  Just point your web browser at http://www.python.org/search/ and
  look for "program", "doesn't", "work", or "my". Whenever you find
  someone else whose program didn't work, don't do what they
  did. Repeat as needed.    -- Tim Peters, on python-help, 16 Jun 1998