人生的游戏进展缓慢。

Question

我正在尝试模拟第一次t=6时间步骤的n维生命游戏。我的Nim代码是Python的一个简单的端口，它工作正常，但是对于n=4，t=6需要2秒才能运行，这比我的CPython版本慢了几个数量级，而不是预期的加速。为什么我的代码这么慢？我能做些什么来加快速度？我正在用-d:release和--opt:speed编译

我用一个64位整数表示空间中的每个点。也就是说，我将(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秒还快。你的结局肯定还有其他问题。很抱歉我没接电话。