Speed

[Gareth McCaughan]

Janos Blazi wrote:

> global r
> r=[]
> 
> def neue_zeile(z):
>     global r
>     z.reverse();
>     r=[]
>     last=-1
>     for x in z:
>         if x==last: cnt=cnt+1
>         else:
>             if last != -1:
>                 r = [cnt,last] + r
>             last=x
>             cnt=1
>     r = [cnt,last] + r
> 
> l=[1]
> for i in range(0,41):
>     print i,len(l)
>     neue_zeile(l)
>     l=r
> print i,len(l)
> 
> print "*done*"
..
> Now it is clear that C is faster than Python, so the C program will have a
> shorter execution time.
> But I cannot believe that C can be hundreds of times faster (The C code need
> less than 2 seconds on my NT machine and the Python code more than 17
> minutes.)
> 
> Is my Python code stupid? Can I improve it?

Here's a more idiomatic Python version.

def successor(s):
  result = []
  last,n = s[0],0
  for x in s:
    if x==last:
      n=n+1
    else:
      result.extend([n,last])
      last,n = x,1
  result.extend([n,last])
  return result

l=[1]
for i in range(41):
  print i, len(l)
  l = successor(l)
print i, len(l)

print "done"

On my machine, this takes about 3.3s.

(Have you encountered Conway's work on the problem this
little program is investigating?)

-- 
Gareth McCaughan  Gareth.McCaughan at pobox.com
sig under construction