Оптимизирующий код (игра жизни Конвея)

Question

Я только что сделал эту консольную версию игры жизни Конвея. Он хорошо подходит для «маленьких» сеток, например, 100 х 100 пикселей, но для больших он ужасно медленный. Можете ли вы помочь мне оптимизировать его, чтобы он мог работать быстрее?

#define _WIN32_WINNT 0x0500 
#include <windows.h> 
#include <iostream> 
#include <cmath> 
#include <cstdlib> 
#include <ctime> 
#include <string> 
using namespace std; 

const int m = 100; 
const int n = 100; // size of the grid area 
const int num_iter = 1000; // number of iterations to run 

int main(){ 

    srand(time(0)); // the initial conditions of the grid should be random 
    int n_count = 0; // variable for counting the neighbors of a particular point 
    int iter = 0; // variable for counting the number of iterations done 
    int grid[m][n] = {0}; 
    int newgrid[m][n] = {0}; // arrays filled with 1's and 0's representing a living or dead cells respectively 

    HWND myconsole = GetConsoleWindow(); 
    HDC mydc = GetDC(myconsole); 
    COLORREF WHITE = RGB(255,255,255); 
    COLORREF BLACK = RGB(0,0,0); 

    for(long i=0;i<m;i++){ // this for initializes the grid with random 1's 
     for(long j=0;j<n;j++){ 
      if(rand()%2==0) grid[i][j] = 1; 
     } 
    } 

    while(iter < num_iter){ // while loop controlling the number of iterations to be done 
     for(long i=0;i<m;i++){ 
      for(long j=0;j<n;j++){ // nested for to count the number of neighbors of each cell 
       if(i-1>=0) if(grid[i-1][j]==1) n_count++; 
       if(j-1>=0) if(grid[i][j-1]==1) n_count++; 
       if(i+1<=n) if(grid[i+1][j]==1) n_count++; 
       if(j+1<=n) if(grid[i][j+1]==1) n_count++; 
       if((i-1>=0)&&(j-1>=0)) if(grid[i-1][j-1]==1) n_count++; 
       if((i-1>=0)&&(j+1<=n)) if(grid[i-1][j+1]==1) n_count++; 
       if((i+1<=n)&&(j-1>=0)) if(grid[i+1][j-1]==1) n_count++; 
       if((i+1<=n)&&(j+1<=n)) if(grid[i+1][j+1]==1) n_count++; // all possible 8 neighbors checked and counted by now 
       if(grid[i][j]==1){ // if the cell is alive and... 
        if(n_count<2) newgrid[i][j] = 0; // ...it has less than 2 neighbors, then it dies 
        else if(n_count>3) newgrid[i][j] =0; // ... it has more than 3 neighbors, then it dies 
        else if((n_count==2)||(n_count==3)) newgrid[i][j] = 1; // ... it has 2 or 3 neighbors, then it lives 
       } 
       else if(n_count==3) newgrid[i][j] = 1; // if the cell is dead and it has 3 neighbors, then it lives 
       n_count = 0; 
      } 
     } 
     for(long i=0;i<m;i++){ // nested for to display a white pixel if the cell is alive, or black if it is dead 
      for(long j=0;j<n;j++){ 
       grid[i][j] = newgrid[i][j]; 
       if(grid[i][j]==1) SetPixel(mydc,i+50,j+40,WHITE); 
       else SetPixel(mydc,i+50,j+40,BLACK); 
      } 
     } 
     Sleep(1); 
     iter++; 
    } 

    ReleaseDC(myconsole, mydc); 
    cin.ignore(); 
    return 0; 
} 

Answer 1

небось оптимизации игры Конвея жизни наука сама по себе, и я уверен, что это покрыто довольно хорошо в ссылке, предоставленной NPE, но если я могу предложить что-то, SetPixel это ужасно отходов времени.

Итак, два оптимизаций:

1. Только делать SetPixel для тех пикселей, которые фактически изменяются. Вместо этого:

    grid[i][j] = newgrid[i][j]; 
        if(grid[i][j]==1) SetPixel(mydc,i+50,j+40,WHITE); 
        else SetPixel(mydc,i+50,j+40,BLACK); 
   

   сделать это:

    if(grid[i][j] != newgrid[i][j]) 
        { 
         grid[i][j] = newgrid[i][j]; 
         if(grid[i][j]==1) SetPixel(mydc,i+50,j+40,WHITE); 
         else SetPixel(mydc,i+50,j+40,BLACK); 
        } 
   

2. Прекратите использование SetPixel в целом; попробуйте получить растровое изображение, заблокировав его, чтобы получить доступ к его буферу памяти, непосредственно манипулируя байтами буфера памяти, чтобы сохранить в нем ваши значения цвета, а затем в конце разблокировать его и перевести его в контекст устройства. Это может показаться большой работой, но поверьте мне, это на самом деле представляет собой улучшенную производительность по сравнению с gazillions вызовов SetPixel.