Commits

Mark Shannon committed 30ccbfd Draft

Add some benchmarks from the computer language shootout game

  • Participants
  • Parent commits 8f0a612

Comments (0)

Files changed (8)

File benchmarks/shootout/binary_trees.py

+# The Computer Language Shootout Benchmarks
+# http://shootout.alioth.debian.org/
+#
+# contributed by Antoine Pitrou
+# modified by Dominique Wahli
+
+from sys import argv
+
+def make_tree(item, depth):
+    if depth > 0:
+        item2 = 2 * item
+        depth -= 1
+        return (item, make_tree(item2 - 1, depth), make_tree(item2, depth))
+    else:
+        return (item, None, None)
+
+def check_tree(node):
+    item, left, right = node
+    if left is not None:
+        return item + check_tree(left) - check_tree(right)
+    else:
+        return item
+
+def main():
+    min_depth = 4
+    max_depth =  int(argv[1]) # max(min_depth + 2, int(argv[1]))
+    stretch_depth = max_depth + 1
+
+    print ("stretch tree of depth %d\t check: %d" %
+            (stretch_depth, check_tree(make_tree(0, stretch_depth))))
+
+    long_lived_tree = make_tree(0, max_depth)
+
+    for depth in range(min_depth, stretch_depth, 2):
+        iterations = 2**(max_depth - depth + min_depth)
+
+        check = 0
+        for i in range(1, iterations + 1):
+            check += check_tree(make_tree(i, depth)) + check_tree(make_tree(-i, depth))
+
+        print ("%d\t trees of depth %d\t check: %d" %
+               (iterations * 2, depth, check))
+
+    print ("long lived tree of depth %d\t check: %d" %
+           (max_depth, check_tree(long_lived_tree)))
+
+if __name__ == '__main__':
+    main()
+
+

File benchmarks/shootout/fannkuch.py

+# The Computer Language Benchmarks Game
+# http://shootout.alioth.debian.org/
+#
+# contributed by Sokolov Yura
+# modified by Tupteq
+# 2to3
+# fixed by Daniele Varrazzo
+
+def fannkuch(n):
+    count = list(range(1, n+1))
+    max_flips = 0
+    m = n-1
+    r = n
+    check = 0
+    perm1 = list(range(n))
+    perm = list(range(n))
+    perm1_ins = perm1.insert
+    perm1_pop = perm1.pop
+
+    while 1:
+        if check < 30:
+            print("".join(str(i+1) for i in perm1))
+            check += 1
+
+        while r != 1:
+            count[r-1] = r
+            r -= 1
+
+        if perm1[0] != 0 and perm1[m] != m:
+            perm = perm1[:]
+            flips_count = 0
+            k = perm[0]
+            while k:
+                perm[:k+1] = perm[k::-1]
+                flips_count += 1
+                k = perm[0]
+
+            if flips_count > max_flips:
+                max_flips = flips_count
+
+        while r != n:
+            perm1_ins(r, perm1_pop(0))
+            count[r] -= 1
+            if count[r] > 0:
+                break
+            r += 1
+        else:
+            return max_flips
+
+def main():
+    from sys import argv
+    n = int(argv and argv[1] or 1)
+    print("Pfannkuchen(%d) = %d\n" % (n, fannkuch(n)), end='')
+
+if __name__=="__main__":
+    main()

File benchmarks/shootout/knucleotide.py

+# The Computer Language Shootout
+# http://shootout.alioth.debian.org/
+#
+# submitted by Ian Osgood
+# modified by Sokolov Yura
+# modified by bearophile
+# 2to3
+
+from sys import stdin
+
+def gen_freq(seq, frame, frequences):
+    ns = len(seq) + 1 - frame
+    frequences.clear()
+    for ii in range(ns):
+        nucleo = seq[ii:ii + frame]
+        if nucleo in frequences:
+            frequences[nucleo] += 1
+        else:
+            frequences[nucleo] = 1
+    return ns, frequences
+
+
+def sort_seq(seq, length, frequences):
+    n, frequences = gen_freq(seq, length, frequences)
+
+    l = sorted(list(frequences.items()), reverse=True, key=lambda seq_freq: (seq_freq[1],seq_freq[0]))
+
+    print('\n'.join("%s %.3f" % (st, 100.0*fr/n) for st,fr in l))
+    print()
+
+
+def find_seq(seq, s, frequences):
+    n,t = gen_freq(seq, len(s), frequences)
+    print("%d\t%s" % (t.get(s, 0), s))
+
+
+def main():
+    frequences = {}
+    for line in stdin:
+        if line[0:3] == ">TH":
+            break
+
+    seq = []
+    for line in stdin:
+        if line[0] in ">;":
+            break
+        seq.append( line[:-1] )
+    sequence = "".join(seq).upper()
+
+    for nl in 1,2:
+        sort_seq(sequence, nl, frequences)
+
+    for se in "GGT GGTA GGTATT GGTATTTTAATT GGTATTTTAATTTATAGT".split():
+        find_seq(sequence, se, frequences)
+
+main()

File benchmarks/shootout/mandelbrot.py

+# The Computer Language Benchmarks Game
+# http://shootout.alioth.debian.org/
+#
+# contributed by Tupteq
+# 2to3 - fixed by Daniele Varrazzo
+
+import sys
+
+def main():
+    cout = sys.stdout.buffer.write
+    size = int(sys.argv[1])
+    xr_size = range(size)
+    xr_iter = range(50)
+    bit = 128
+    byte_acc = 0
+
+    cout(("P4\n%d %d\n" % (size, size)).encode('ascii'))
+
+    size = float(size)
+    for y in xr_size:
+        fy = 2j * y / size - 1j
+        for x in xr_size:
+            z = 0j
+            c = 2. * x / size - 1.5 + fy
+
+            for i in xr_iter:
+                z = z * z + c
+                if abs(z) >= 2.0:
+                    break
+            else:
+                byte_acc += bit
+
+            if bit > 1:
+                bit >>= 1
+            else:
+                cout((byte_acc,))
+                bit = 128
+                byte_acc = 0
+
+        if bit != 128:
+            cout((byte_acc,))
+            bit = 128
+            byte_acc = 0
+
+main()

File benchmarks/shootout/meteor.py

+# The Computer Language Benchmarks Game
+# http://shootout.alioth.debian.org/
+#
+# contributed by: Olof Kraigher
+# 2to3
+
+from sys import argv
+
+width = 5
+height = 10
+
+directions  = { "E" : 0, "NE" : 1, "NW" : 2, "W" : 3, "SW" : 4, "SE" : 5}
+rotate      = { "E" : "NE", "NE" : "NW", "NW" : "W", "W" : "SW", "SW" : "SE", "SE" : "E"}
+flip        = { "E" : "W", "NE" : "NW", "NW" : "NE", "W" : "E", "SW" : "SE", "SE" : "SW"}
+move        = { "E" : lambda x,y: (x+1,y),
+                "W" : lambda x,y: (x-1,y),
+                "NE" : lambda x,y: (x+(y%2),y-1),
+                "NW" : lambda x,y: (x+(y%2)-1,y-1),
+                "SE" : lambda x,y: (x+(y%2),y+1),
+                "SW" : lambda x,y: (x+(y%2)-1,y+1)}
+
+pieces =   [    ["E", "E", "E", "SE"],
+                ["SE", "SW", "W", "SW"],
+                ["W", "W", "SW", "SE"],
+                ["E",  "E", "SW", "SE"],
+                ["NW", "W", "NW", "SE", "SW"],
+                ["E",  "E", "NE", "W"],
+                ["NW", "NE", "NE", "W"],
+                ["NE", "SE", "E", "NE"],
+                ["SE", "SE", "E", "SE"],
+                ["E", "NW", "NW", "NW"]]
+
+solutions = []
+masks = [0 for i in range(10)]
+
+valid = lambda x,y: (0 <= x) and (x < width) and (0 <= y) and (y < height)
+legal = lambda mask,board: (mask & board) == 0
+zerocount = lambda mask: sum([((1<<x) & mask) == 0 for x in range(50)])
+
+def findFreeCell(board):
+    for y in range(height):
+        for x in range(width):
+            if board & (1 << (x + width*y)) == 0:
+                return x,y
+
+
+def floodFill(board, xxx_todo_changeme):
+    (x, y) = xxx_todo_changeme
+    if not valid(x,y):
+        return board
+    if board & (1 << (x + width*y)) != 0:
+        return board
+
+    board = board | (1 << (x + width*y))
+
+    for f in list(move.values()):
+        board = board | floodFill(board, f(x,y))
+
+    return board
+
+def noIslands(mask):
+    zeroes = zerocount(mask)
+
+    if zeroes < 5:
+        return False
+
+    while mask != 0x3FFFFFFFFFFFF:
+        mask = floodFill(mask, findFreeCell(mask))
+        new_zeroes = zerocount(mask)
+
+        if zeroes - new_zeroes < 5:
+            return False
+
+        zeroes = new_zeroes
+
+    return True
+
+def getBitmask(x,y,piece):
+    mask = (1 << (x + width*y))
+
+    for cell in piece:
+        x,y = move[cell](x,y)
+        if valid(x,y):
+            mask = mask | (1 << (x + width*y))
+        else:
+            return False, 0
+
+    return True, mask
+
+def allBitmasks(piece, color):
+    bitmasks = []
+    for orientations in range(2):
+        for rotations in range(6 - 3*(color == 4)):
+            for y in range(height):
+                for x in range(width):
+                    isValid, mask = getBitmask(x,y,piece)
+                    if isValid and noIslands(mask):
+                        bitmasks.append(mask)
+
+            piece = [rotate[cell] for cell in piece]
+        piece = [flip[cell] for cell in piece]
+
+
+    return bitmasks
+
+def generateBitmasks():
+
+    global masksAtCell
+
+    masksAtCell = [[[] for j in range(10)] for i in range(width*height)]
+
+    color = 0
+    for piece in pieces:
+        masks = allBitmasks(piece, color)
+        masks.sort()
+        cellMask = 1 << (width*height-1)
+        cellCounter = width*height-1
+
+        j = len(masks)-1
+
+        while (j >= 0):
+            if (masks[j] & cellMask) == cellMask:
+                masksAtCell[cellCounter][color].append(masks[j])
+                j = j-1
+            else:
+                cellMask = cellMask >> 1
+                cellCounter -= 1
+        color += 1
+
+
+def solveCell(cell, board, n):
+
+    global solutions, masks, masksAtCell
+
+    if len(solutions) >= n:
+        return
+
+    if board == 0x3FFFFFFFFFFFF:
+        # Solved
+        s = stringOfMasks(masks)
+        solutions.append(s);
+        solutions.append(inverse(s));
+        return
+
+    if board & (1 << cell) != 0:
+        # Cell full
+        solveCell(cell-1, board, n)
+        return
+
+    if cell < 0:
+        # Out of board
+        return
+
+    for color in range(10):
+        if masks[color] == 0:
+            for mask in masksAtCell[cell][color]:
+                if legal(mask, board):
+                    masks[color] = mask
+                    solveCell(cell-1, board | mask, n);
+                    masks[color] = 0
+
+def solve(n):
+    generateBitmasks()
+    solveCell(width*height-1, 0, n)
+
+
+def stringOfMasks(masks):
+    s = ""
+    mask = 1;
+    for y in range(height):
+        for x in range(width):
+            for color in range(10):
+                if (masks[color] & mask) != 0:
+                    s += str(color)
+                    break
+                elif color == 9:
+                    s += "."
+            mask = mask << 1
+    return s
+
+def inverse(s):
+    ns = [x for x in s]
+
+    for x in range(width):
+        for y in range(height):
+            ns[x + y*width] = s[width-x-1 + (width - y - 1)*width]
+
+    return s
+
+def printSolution(solution):
+    for y in range(height):
+        for x in range(width):
+            print(solution[x + y*width], end=' ')
+
+        if (y%2) == 0:
+            print("")
+            print("", end=' ')
+        else:
+            print("")
+
+if __name__ == "__main__":
+
+    if not len(argv) > 1:
+        exit()
+
+    solve(int(argv[1]))
+    print(len(solutions), "solutions found")
+    print()
+    printSolution(min(solutions))
+    print()
+    printSolution(max(solutions))
+    print()

File benchmarks/shootout/nbody.py

+# The Computer Language Benchmarks Game
+# http://shootout.alioth.debian.org/
+#
+# originally by Kevin Carson
+# modified by Tupteq, Fredrik Johansson, and Daniel Nanz
+# modified by Maciej Fijalkowski
+# 2to3
+
+import sys 
+
+def combinations(l):
+    result = []
+    for x in range(len(l) - 1):
+        ls = l[x+1:]
+        for y in ls:
+            result.append((l[x],y))
+    return result
+
+PI = 3.14159265358979323
+SOLAR_MASS = 4 * PI * PI
+DAYS_PER_YEAR = 365.24
+
+BODIES = {
+    'sun': ([0.0, 0.0, 0.0], [0.0, 0.0, 0.0], SOLAR_MASS),
+
+    'jupiter': ([4.84143144246472090e+00,
+                 -1.16032004402742839e+00,
+                 -1.03622044471123109e-01],
+                [1.66007664274403694e-03 * DAYS_PER_YEAR,
+                 7.69901118419740425e-03 * DAYS_PER_YEAR,
+                 -6.90460016972063023e-05 * DAYS_PER_YEAR],
+                9.54791938424326609e-04 * SOLAR_MASS),
+
+    'saturn': ([8.34336671824457987e+00,
+                4.12479856412430479e+00,
+                -4.03523417114321381e-01],
+               [-2.76742510726862411e-03 * DAYS_PER_YEAR,
+                4.99852801234917238e-03 * DAYS_PER_YEAR,
+                2.30417297573763929e-05 * DAYS_PER_YEAR],
+               2.85885980666130812e-04 * SOLAR_MASS),
+
+    'uranus': ([1.28943695621391310e+01,
+                -1.51111514016986312e+01,
+                -2.23307578892655734e-01],
+               [2.96460137564761618e-03 * DAYS_PER_YEAR,
+                2.37847173959480950e-03 * DAYS_PER_YEAR,
+                -2.96589568540237556e-05 * DAYS_PER_YEAR],
+               4.36624404335156298e-05 * SOLAR_MASS),
+
+    'neptune': ([1.53796971148509165e+01,
+                 -2.59193146099879641e+01,
+                 1.79258772950371181e-01],
+                [2.68067772490389322e-03 * DAYS_PER_YEAR,
+                 1.62824170038242295e-03 * DAYS_PER_YEAR,
+                 -9.51592254519715870e-05 * DAYS_PER_YEAR],
+                5.15138902046611451e-05 * SOLAR_MASS) }
+
+
+SYSTEM = list(BODIES.values())
+PAIRS = combinations(SYSTEM)
+
+
+def advance(dt, n, bodies=SYSTEM, pairs=PAIRS):
+
+    for i in range(n):
+        for (([x1, y1, z1], v1, m1),
+             ([x2, y2, z2], v2, m2)) in pairs:
+            dx = x1 - x2
+            dy = y1 - y2
+            dz = z1 - z2
+            mag = dt * ((dx * dx + dy * dy + dz * dz) ** (-1.5))
+            b1m = m1 * mag
+            b2m = m2 * mag
+            v1[0] -= dx * b2m
+            v1[1] -= dy * b2m
+            v1[2] -= dz * b2m
+            v2[0] += dx * b1m
+            v2[1] += dy * b1m
+            v2[2] += dz * b1m
+        for (r, [vx, vy, vz], m) in bodies:
+            r[0] += dt * vx
+            r[1] += dt * vy
+            r[2] += dt * vz
+
+
+def report_energy(bodies=SYSTEM, pairs=PAIRS, e=0.0):
+
+    for (((x1, y1, z1), v1, m1),
+         ((x2, y2, z2), v2, m2)) in pairs:
+        dx = x1 - x2
+        dy = y1 - y2
+        dz = z1 - z2
+        e -= (m1 * m2) / ((dx * dx + dy * dy + dz * dz) ** 0.5)
+    for (r, [vx, vy, vz], m) in bodies:
+        e += m * (vx * vx + vy * vy + vz * vz) / 2.
+    print("%.9f" % e)
+
+def offset_momentum(ref, bodies=SYSTEM, px=0.0, py=0.0, pz=0.0):
+
+    for (r, [vx, vy, vz], m) in bodies:
+        px -= vx * m
+        py -= vy * m
+        pz -= vz * m
+    (r, v, m) = ref
+    v[0] = px / m
+    v[1] = py / m
+    v[2] = pz / m
+
+def main(n, ref='sun'):
+    offset_momentum(BODIES[ref])
+    report_energy()
+    advance(0.01, n)
+    report_energy()
+
+if __name__ == '__main__':
+    main(int(sys.argv[1]))

File benchmarks/shootout/pidigits.py

+import sys
+from itertools import islice, count
+
+def gen_x():
+    return map(lambda k: (k, 4*k + 2, 0, 2*k + 1), count(1))
+
+def compose(xxx_todo_changeme, xxx_todo_changeme1):
+    (aq, ar, as_, at) = xxx_todo_changeme
+    (bq, br, bs, bt) = xxx_todo_changeme1
+    return (aq * bq,
+            aq * br + ar * bt,
+            as_ * bq + at * bs,
+            as_ * br + at * bt)
+
+def extract(xxx_todo_changeme2, j):
+#    print(xxx_todo_changeme2)
+    (q, r, s, t) = xxx_todo_changeme2
+    return (q*j + r) // (s*j + t)
+
+def pi_digits():
+    z = (1, 0, 0, 1)
+    x = gen_x()
+    while 1:
+        y = extract(z, 3)
+        while y != extract(z, 4):
+            z = compose(z, next(x))
+            y = extract(z, 3)
+        z = compose((10, -10*y, 0, 1), z)
+        yield y
+
+def main():
+    n = int(sys.argv[1])
+    digits = pi_digits()
+    width = 10
+    for i in range(width, n+1, width):
+        print("%s\t:%d" % ("".join(map(str, islice(digits, width))), i))
+    if n % width > 0:
+        sl = islice(digits, n % width)
+        print("%s\t:%d" % ("".join(map(str, sl)).ljust(width), n))
+
+
+main()
+

File benchmarks/shootout/spectralnorm.py

+# The Computer Language Benchmarks Game
+# http://shootout.alioth.debian.org/
+#
+# Contributed by Sebastien Loisel
+# Fixed by Isaac Gouy
+# Sped up by Josh Goldfoot
+# Dirtily sped up by Simon Descarpentries
+# Used list comprehension by Vadim Zelenin
+# 2to3
+
+from math      import sqrt
+from sys       import argv
+
+
+def eval_A(i, j):
+    ij = i+j
+    return 1.0 / (ij * (ij + 1) / 2 + i + 1)
+
+
+def eval_A_times_u(u):
+    local_eval_A = eval_A
+
+    return [ sum([ local_eval_A(i, j) * u_j
+                   for j, u_j in enumerate(u)
+                 ]
+                )
+             for i in range(len(u))
+           ]
+
+
+def eval_At_times_u(u):
+    local_eval_A = eval_A
+
+    return [ sum([ local_eval_A(j, i) * u_j
+                   for j, u_j in enumerate(u)
+                 ]
+                )
+             for i in range(len(u))
+           ]
+
+
+def eval_AtA_times_u(u):
+    return eval_At_times_u(eval_A_times_u(u))
+
+
+def main():
+    n = int(argv[1])
+    u = [1] * n
+    local_eval_AtA_times_u = eval_AtA_times_u
+
+    for dummy in range(10):
+        v = local_eval_AtA_times_u(u)
+        u = local_eval_AtA_times_u(v)
+
+    vBv = vv = 0
+
+    for ue, ve in zip(u, v):
+        vBv += ue * ve
+        vv  += ve * ve
+
+    print("%0.9f" % (sqrt(vBv/vv)))
+
+main()