生命游戏中的循环和复杂性

Question

在尝试优化 C 代码的性能时（4 支滑翔机枪，在生活游戏中每个角落各一支），我不得不在两种情况之间做出选择：

int M = (int) DIM / 2 + 1;
for (int y = 1; y < M; y += TILE_SIZE)
  for (int x = 1; x < M; x += TILE_SIZE)
  {
    change |= do_tile(x, y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
    change |= do_tile(DIM - x, y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
    change |= do_tile(x, DIM - y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
    change |= do_tile(DIM - x, DIM - y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
  }

和

for (int y = 1; y < DIM - 1; y += TILE_SIZE)
  for (int x = 1; x < DIM - 1; x += TILE_SIZE)
    change |= do_tile(x, y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());

如果我们以复杂的方式考虑它，我们会得到它们都具有相同的时间复杂度：

(DIM/2) * (DIM/2) * 4 = 昏暗 * 昏暗

但是当我执行它们时，第一个总是在不到 600 毫秒内完成，而第二个总是在 650 毫秒左右完成。这怎么可能？ game of life这个配置有没有更好的优化？

Answer 1

正如奥本上面所说，我给出的复杂度只是一个估计值（ O(DIM * DIM) ).而且由于处理器不喜欢循环内的跳转，所以更少的迭代意味着更少的时间。

生命游戏中的循环和复杂性

For loop and complexity in game of life

c

time-complexity

conways-game-of-life