我可以加快這個功能嗎？

我想寫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--; 
     } 
    } 
}

來源

2017-04-15 MGStone

這是O（n），應該在負擔得起的時間內完成。 n有多大？ –

另請參閱https://stackoverflow.com/questions/40485/optimizing-conways-game-of-life –

如果讓我們說70％的細胞還活着，那麼這意味着您的代碼將不得不尋找其他細胞7次10個，這使得不必要的重複。如果您將單元格從「剩餘單元格」數組中取出時將其設置爲活動狀態，會發生什麼情況？ –

-2

模函數是相當緩慢的，儘量(float)rand()/RAND_MAX*BOARD_WIDTH + 0.5

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

來源

2017-04-15 05:01:50 yar

不，任何體面的編譯器[將一個常數轉換爲乘以它的乘法逆]（http://stackoverflow.com/q/41183935/995714） –

@LưuVĩnhPhúc：我必須有一個訣竅尋找不雅的人然後:( – doynax

海灣合作委員會，鐺，國際刑事法院，CL ...所有可以做到這一點[見此]（https://godbolt.org/g/0F5Agt），在任何編譯器中都沒有div指令 –

如果讓我們說細胞70％是活的，那麼就意味着你的程序將不得不在10次中找到其他小區7次，這會造成不必要的重複。

當您將其設置爲活動狀態時，您可以從「剩餘單元格」數組中彈出選定單元格，並在此數組中隨機選擇您的單元格。我建議使用動態可調整大小的容器，這樣每次彈出單元格時都不必操作整個「剩餘單元格」數組。這應該有助於節省更多時間。

來源

2017-04-15 05:22:49

如果您的主板在內存中連續存在，則無需撥打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; 
     } 
    } 
}

來源

2017-04-15 06:11:47 bitwise

請注意，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細胞殺死。
如果電路板不一定是空的，通過此功能，活細胞的數量將有助於確定哪種方法更好，以及是否至少存在死細胞而不需要漫長的循環來枚舉死細胞。

來源

2017-04-15 07:13:55 chqrlie

我可以加快這個功能嗎？

回答

相關問題