performance measurements

Each table row shows performance measurements for this Cython program with a particular command-line input value N.

 N  CPU secs Elapsed secs Memory KB Code B ≈ CPU Load
2,0983.673.8310,9561334  3% 93% 4% 10%
2,0983.663.6711,0641334  100% 9% 3% 1%
2,0983.693.8611,0161334  2% 100% 4% 2%

Read the ↓ make, command line, and program output logs to see how this program was run.

Read meteor-contest benchmark to see what this program should do.

 notes

 meteor-contest Cython #3 program source code

# The Computer Language Benchmarks Game
# http://benchmarksgame.alioth.debian.org/
#
# contributed by Daniel Nanz, 2008-08-21
# 2to3

import sys
from bisect import bisect

w, h = 5, 10
dir_no = 6
S, E = w * h, 2
SE = S + (E / 2)
SW = SE - E
W, NW, NE = -E, -SE, -SW


def rotate(ido, rd={E: NE, NE: NW, NW: W, W: SW, SW: SE, SE: E}):
    return [rd[o] for o in ido]

def flip(ido, fd={E: E, NE: SE, NW: SW, W: W, SW: NW, SE: NE}):
    return [fd[o] for o in ido]


def permute(ido, r_ido, rotate=rotate, flip=flip):

    ps = [ido]
    for r in range(dir_no - 1):
        ps.append(rotate(ps[-1]))
        if ido == r_ido:                 # C2-symmetry
            ps = ps[0:dir_no//2]
    for pp in ps[:]:
        ps.append(flip(pp))
    return ps


def convert(ido):
    '''incremental direction offsets -> "coordinate offsets" '''
    out = [0]
    for o in ido:
        out.append(out[-1] + o)
    return list(set(out))


def get_footprints(board, cti, pieces):

    fps = [[[] for p in range(len(pieces))] for ci in range(len(board))]
    for c in board:
        for pi, p in enumerate(pieces):
            for pp in p:
                fp = frozenset(cti[c + o] for o in pp if (c + o) in cti)
                if len(fp) == 5:
                    fps[min(fp)][pi].append(fp)
    return fps


def get_senh(board, cti):
    '''-> south-east neighborhood'''
    se_nh = []
    nh = [E, SW, SE]
    for c in board:
        se_nh.append(frozenset(cti[c + o] for o in nh if (c + o) in cti))
    return se_nh


def get_puzzle(w=w, h=h):

    board = [E*x + S*y + (y%2) for y in range(h) for x in range(w)]
    cti = dict((board[i], i) for i in range(len(board)))

    idos = [[E, E, E, SE],         # incremental direction offsets
            [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]]

    perms = (permute(p, idos[3]) for p in idos)    # restrict piece 4
    pieces = [[convert(pp) for pp in p] for p in perms]
    return (board, cti, pieces)


def print_board(board, w=w, h=h):

    for y in range(h):
        for x in range(w):
            print(board[x + y * w], end=' ')
        print('')
        if y % 2 == 0:
            print('', end=' ')
    print()


board, cti, pieces = get_puzzle()
fps = get_footprints(board, cti, pieces)
se_nh = get_senh(board, cti)


def solve(n, i_min, free, curr_board, pieces_left, solutions,
          fps=fps, se_nh=se_nh, bisect=bisect):

    fp_i_cands = fps[i_min]
    for p in pieces_left:
        fp_cands = fp_i_cands[p]
        for fp in fp_cands:
            if fp <= free:
                n_curr_board = curr_board[:]
                for ci in fp:
                    n_curr_board[ci] = p
                if len(pieces_left) > 1:
                    n_free = free - fp
                    n_i_min = min(n_free)
                    if len(n_free & se_nh[n_i_min]) > 0:
                        n_pieces_left = pieces_left[:]
                        n_pieces_left.remove(p)
                        solve(n, n_i_min, n_free, n_curr_board,
                              n_pieces_left, solutions)
                else:
                    s = ''.join(map(str, n_curr_board))
                    solutions.insert(bisect(solutions, s), s)
                    rs = s[::-1]
                    solutions.insert(bisect(solutions, rs), rs)
                    if len(solutions) >= n:
                        return
        if len(solutions) >= n:
            return
    return

def main(n):

    free = frozenset(range(len(board)))
    curr_board = [-1] * len(board)
    pieces_left = list(range(len(pieces)))
    solutions = []
    solve(n, 0, free, curr_board, pieces_left, solutions)
    print(len(solutions),  'solutions found\n')
    for i in (0, -1): print_board(solutions[i])

main(int(sys.argv[1]))

 make, command-line, and program output logs

Mon, 15 Oct 2018 12:14:58 GMT

MAKE:
make[1]: Vstupuje se do adresáře „/home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp“
cp meteor.cython-3.cython `echo meteor.cython-3.cython | sed 's/cython-..//' | sed 's/.cython//'`.pyx
cythonize -3 -bi `echo meteor.cython-3.cython | sed 's/cython-..//' | sed 's/.cython//'`.pyx
Compiling /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/meteor.pyx because it changed.
[1/1] Cythonizing /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/meteor.pyx
running build_ext
building 'meteor' extension
creating /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/tmpru41zta9/home
creating /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/tmpru41zta9/home/dundee
creating /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/tmpru41zta9/home/dundee/workspace
creating /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/tmpru41zta9/home/dundee/workspace/benchmarksgame
creating /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/tmpru41zta9/home/dundee/workspace/benchmarksgame/bencher
creating /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/tmpru41zta9/home/dundee/workspace/benchmarksgame/bencher/tmp
creating /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/tmpru41zta9/home/dundee/workspace/benchmarksgame/bencher/tmp/meteor
creating /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/tmpru41zta9/home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp
gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -march=x86-64 -mtune=generic -O3 -pipe -fstack-protector-strong -fno-plt -flto=4 -fuse-linker-plugin -ffat-lto-objects -flto-partition=none -march=x86-64 -mtune=generic -O3 -pipe -fstack-protector-strong -fno-plt -march=x86-64 -mtune=generic -O3 -pipe -fstack-protector-strong -fno-plt -fPIC -I/usr/include/python3.7m -c /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/meteor.c -o /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/tmpru41zta9/home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/meteor.o
gcc -pthread -shared -Wl,-O1,--sort-common,--as-needed,-z,relro,-z,now -flto=4 -fuse-linker-plugin -ffat-lto-objects -flto-partition=none -Wl,-O1,--sort-common,--as-needed,-z,relro,-z,now /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/tmpru41zta9/home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/meteor.o -L/usr/lib -lpython3.7m -o /home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp/meteor.cpython-37m-x86_64-linux-gnu.so
make[1]: Opouští se adresář „/home/dundee/workspace/benchmarksgame/bencher/tmp/meteor/tmp“
7.40s to complete and log all make actions

COMMAND LINE:
/usr/bin/python3 -c "import meteor" 2098

PROGRAM OUTPUT:
2098 solutions found

0 0 0 0 1 
 2 2 2 0 1 
2 6 6 1 1 
 2 6 1 5 5 
8 6 5 5 5 
 8 6 3 3 3 
4 8 8 9 3 
 4 4 8 9 3 
4 7 4 7 9 
 7 7 7 9 9 

9 9 9 9 8 
 9 6 6 8 5 
6 6 8 8 5 
 6 8 2 5 5 
7 7 7 2 5 
 7 4 7 2 0 
1 4 2 2 0 
 1 4 4 0 3 
1 4 0 0 3 
 1 1 3 3 3 

Revised BSD license

  Home   Conclusions   License   Play