Computer Language Shootout

igouy at yahoo.com igouy at yahoo.com
Tue Nov 29 23:08:12 CET 2005


We don't scrape programs from news-groups, if you'd like the program to
be shown on the shootout then please attach the source code to a
tracker item.

Please follow the FAQ instructions
http://shootout.alioth.debian.org/faq.php#contribute


bearophileHUGS at lycos.com wrote:
> This is a direct translation of the D code, maybe it's not the faster
> Python implementation, and surely it's not the shorter one. But Psyco
> makes it much faster (Psyco likes "low level" style code).
> ShedSkink is (almost) able to compile it too, producing a really fast
> executable (with some "smart attentions" this SS version becomes only
> 17% slower than the D version for a given n=11 (26.66 sec instead of
> 22.70 sec of total running time on a PIII 500 MHz)).
>
>
> ! import sys
> !
> ! def fannkuch(n):
> !   perm = [0] * n
> !   perm1 = range(n)
> !   count = [0] * n
> !   m = n - 1
> !   r = n
> !   maxFlipsCount = 0
> !
> !   while True:
> !     while r != 1:
> !       count[r-1] = r
> !       r -= 1
> !
> !     # SS v.0.0.5 has a problem with this line:
> !     if not (perm1[0]==0 or perm1[m]==m):
> !       #perm = list(perm1)
> !       # to not produce memory garbage
> !       for i in xrange(n):
> !         perm[i] = perm1[i]
> !
> !       i = perm[0]
> !       flips = 0
> !       while i:
> !         temp = perm[i]
> !         perm[i] = i
> !         i = temp
> !         j = 1
> !         k = i - 1
> !         while j < k:
> !           temp = perm[j]
> !           perm[j] = perm[k]
> !           perm[k] = temp
> !           j += 1
> !           k -= 1
> !         flips += 1
> !
> !       if flips > maxFlipsCount:
> !         maxFlipsCount = flips
> !
> !     while True:
> !       if r == n:
> !         return maxFlipsCount
> !       temp = perm1[0]
> !       i = 0
> !       while i < r:
> !         j = i + 1
> !         perm1[i] = perm1[j]
> !         i = j
> !       perm1[r] = temp
> !
> !       count[r] -= 1
> !       if count[r] > 0:
> !         break
> !       r += 1
> !
> !
> ! #import psyco
> ! #psyco.bind(fannkuch)
> !
> ! if len(sys.argv) > 1:
> !   n = int(sys.argv[1])
> ! else:
> !   n = 1
> ! print "Pfannkuchen(%d) = %ld" % (n, fannkuch(n))
> 
> 
> Bye,
> bearophile




More information about the Python-list mailing list