生命游戏运行慢

Question

我正在尝试模拟第一个 t=6 个时间步长的 n 维生活游戏。我的 Nim 代码是来自 Python 的直接端口，它工作正常但不是预期的加速，对于 n=4，t=6 它需要 2 秒到运行，这比我的 CPython 版本。为什么我的代码这么慢？我该怎么做才能加快速度？我正在编译 -d:release 和 --opt:speed

我用一个 64 位整数表示 space 中的每个点。也就是说，我将 (x_0, x_1, ..., x_{n-1}) 映射到总和 x_i * 32^i。我可以这样做，因为我知道在 6 个时间步之后每个坐标 -15<=x_i<=15 所以我没有溢出。

规则是：

alive - has 2 or 3 alive neigbours: stays alive
      - different number of them: becomes alive
dead - has 3 alive neighbours: becomes alive
     - else: stays dead

下面是我的代码。关键部分是 proc nxt，它获取一组活动单元格并在下一个时间步输出一组活动单元格。这个过程被调用了 6 次。我唯一感兴趣的是活细胞的数量。

我运行输入以下代码：

.##...#.
.#.###..
..##.#.#
##...#.#
#..#...#
#..###..
.##.####
..#####.

代码：

import sets, tables, intsets,  times, os, math

const DIM = 4
const ROUNDS = 6
const REG_SIZE = 5
const MAX_VAL = 2^(REG_SIZE-1)

var grid = initIntSet()

# Inits neighbours
var neigbours: seq[int]
proc initNeigbours(base,depth: int) =
    if depth == 0: 
        if base != 0:
            neigbours.add(base)
    else:
        initNeigbours(base*2*MAX_VAL-1, depth-1)
        initNeigbours(base*2*MAX_VAL+0, depth-1)
        initNeigbours(base*2*MAX_VAL+1, depth-1)
initNeigbours(0,DIM)
echo neigbours

# Calculates next iteration:
proc nxt(grid: IntSet): IntSet =
    var counting: CountTable[int]
    for x in grid:
        for dx in neigbours:
            counting.inc(x+dx)
    for x, count in counting.pairs:
        if count == 3 or (count == 2 and x in grid):
            result.incl(x)

# Loads input
var row = 0
while true:
    var line = stdin.readLine
    if line == "":
        break
    for col in 0..<line.len:
        if line[col] == '#':
            grid.incl((row-MAX_VAL)*2*MAX_VAL + col-MAX_VAL)
    inc row

# Run computation
let time = cpuTime()
for i in 1..ROUNDS:
    grid = nxt(grid) 

echo "Time taken: ", cpuTime() - time
echo "Result: ", grid.len
discard stdin.readLine

Answer 1

你的代码在我的电脑上运行大约 0.02:

Time taken: 0.020875947
Result: 2276

Time taken: 0.01853268
Result: 2276

Time taken: 0.021355269
Result: 2276

我将读取输入的部分更改为：

# Loads input
var row = 0
let input = open("input.txt")
for line in input.lines:
  for i, col in line:
    if col == '#':
      grid.incl((row-MAX_VAL)*2*MAX_VAL + i-MAX_VAL)
  inc row
input.close()

但这应该不会影响性能，只是在我看来它看起来更好。我编译了：

nim c -d:danger script.nim

使用 Nim 1.4.2。 -d:danger是进入更深水域前的最大速度标志。

但即使在调试模式下编译：

$ nim c -r script.nim

Time taken: 0.07699487199999999
Result: 2276

比 2 秒快得多。你这边肯定还有其他问题。很抱歉没有回答。

生命游戏运行慢

Game of life is running slow

nim-lang

生命游戏 运行 慢

Game of life is running slow

nim-lang

生命游戏运行慢