我可以加快这个功能吗？

问题描述：

我想写C约翰康威的生命游戏，但我在添加活细胞到板上时遇到了麻烦。我写的处理它的功能非常慢。思考过程：我想随机添加n个活细胞到板子上，所以当细胞离开设置活着时，得到一个随机的（x，y）对，如果它已经死了，就让它活着。这样我可以保证n个细胞活着。我可以加快这个功能吗？

我对这个问题的理解不正确，还是我只是低效？为什么这么慢，我怎样才能让它更快？

void add_cells(int board[BOARD_WIDTH][BOARD_HEIGHT], int n) 
{ 
    // Randomly set n dead cells to live state. 
    while (n) 
    { 
     int randX = rand() % BOARD_WIDTH; 
     int randY = rand() % BOARD_HEIGHT; 

     if(board[randX][randY] == 0) 
     { 
      board[randX][randY] = 1; 
      n--; 
     } 
    } 
}

这是O（n），应该在负担得起的时间内完成。 n有多大？ –

另请参阅https://stackoverflow.com/questions/40485/optimizing-conways-game-of-life –

如果让我们说70％的细胞还活着，那么这意味着您的代码将不得不寻找其他细胞7次10个，这使得不必要的重复。如果您将单元格从“剩余单元格”数组中取出时将其设置为活动状态，会发生什么情况？ –

答

模函数是相当缓慢的，尽量(float)rand()/RAND_MAX*BOARD_WIDTH + 0.5

你也可以使用更快的兰特，看到here

不，任何体面的编译器[将一个常数转换为乘以它的乘法逆]（http://stackoverflow.com/q/41183935/995714） –

@LưuVĩnhPhúc：我必须有一个诀窍寻找不雅的人然后:( – doynax

海湾合作委员会，铛，国际刑事法院，CL ...所有可以做到这一点[见此]（https://godbolt.org/g/0F5Agt），在任何编译器中都没有div指令 –

答

如果让我们说细胞70％是活的，那么就意味着你的程序将不得不在10次中找到其他小区7次，这会造成不必要的重复。

当您将其设置为活动状态时，您可以从“剩余单元格”数组中弹出选定单元格，并在此数组中随机选择您的单元格。我建议使用动态可调整大小的容器，这样每次弹出单元格时都不必操作整个“剩余单元格”数组。这应该有助于节省更多时间。

答

如果您的主板在内存中连续存在，则无需拨打rand()两次。您只能使用rand() % (BOARD_WIDTH * BOARD_HEIGHT)。

void add_cells(uint8_t board[BOARD_WIDTH][BOARD_HEIGHT], int n) 
{ 
    std::mt19937 eng; 
    uniform_int_distribution<int> dist(0, BOARD_WIDTH * BOARD_HEIGHT - 1); 

    while(n) 
    { 
     int index = dist(eng); 

     uint8_t* cell = (uint8_t*)board + index; 
     if(*cell == 0) 
     { 
      *cell = 1; 
      --n; 
     } 
    } 
}

请注意，RAND_MAX可能小于BOARD_WIDTH * BOARD_HEIGHT' –

变量板是连续的，因为它是二维整数数组。 –

这当然更快。虽然不是相同的，但原始版本发现并设置了“n”个明确的单元格。因此，一个常数因子的改进在这里没有多大帮助，它确实需要一个改进的数据结构来跟踪空白单元以随机设置，而不是盲目地搜索剩余的空白。 – doynax

答

有可能解释一些缓慢在你的问题的几个问题：

被初始化为0董事会调用add_cells()过吗？如果董事会有随机内容，寻找死亡细胞可能需要很长时间，或者如果少于n细胞死亡，则可能需要永久保存。
您确定board被正确定义？ 2D阵列看起来更自然，其中y是第一维，x第二维：使用int board[BOARD_HEIGHT][BOARD_WIDTH]并交换randX和randY的索引值。
对于(n > 0)的测试将防止无限循环，如果add_cells()被称为负数n。
如果n很大，寻找死细胞可能需要很长时间，因为随机拍摄有很小的几率击中一个。
如果n大于BOARD_WIDTH * BOARD_HEIGHT或者如果存在的死细胞数少于n，则循环将永久迭代。

如果n较大，或者如果董事会只有少数的死细胞，它会更有效枚举死细胞和选择的靶细胞从只死细胞随机的。缺点是如果n很小并且板上有许多死单元，这种方法会更慢。

的时间复杂度n小相比，死细胞的数量是为O（n），这是很难被击败，应该是非常快于当前的硬件，但它向O（往往N * BOARD_WIDTH * BOARD_HEIGHT）如果n很大或接近死亡单元的数量，这是太多效率较低，并且如果n大于死亡单元的数量，该功能永远不会结束。

如果电路板被称为是空当add_cells()被调用时，如果n比BOARD_WIDTH * BOARD_HEIGHT/2较大，这将是更有效地将所有细胞存活和选择n细胞杀死。
如果电路板不一定是空的，通过此功能，活细胞的数量将有助于确定哪种方法更好，以及是否至少存在死细胞而不需要漫长的循环来枚举死细胞。

我可以加快这个功能吗？

相关推荐