Can I speed up this function?
I'm trying to write John Conway's life game in C, but I'm having trouble adding live cells to the board. The function I wrote to handle is very slow.
Thinking process: I want to add n live cells to the board randomly, so as long as the cells are alive, get a random (x, y) pair, and if it's dead, make it live. This way, I can guarantee that n cells will become alive.
Am I misunderstanding what the problem is, or am I just ineffective? Why is it so slow and how can I make it faster?
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--;
}
}
}
source to share
If we say that 70% of the cells are alive, then your program will have to find another cell 7 times out of 10, which makes unnecessary repetitions.
You can pull the selected cell out of the "remaining cells" array when you set it active, and randomly select a cell in that array. I suggest using a dynamically resizing container, so you don't have to manipulate the entire array of "leftover cells" every time you exit a cell. This should help you save more time.
source to share
If your board is contiguous in memory, you don't need to ring twice rand()
. You can just use 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;
}
}
}
source to share
There are several problems that may explain some of the slowness in your problem:
-
Is the board initialized to 0 before being called
add_cells()
? If there is random content on the board, finding dead cells can take an arbitrary long time, or potentially take an eternity if there are fewer dead cellsn
. -
Are you sure you are
board
correctly defined? A 2D array seems more natural if ity
is the first dimension and thex
second: usingint board[BOARD_HEIGHT][BOARD_WIDTH]
and replacing the index values forrandX
andrandY
. -
Testing for
(n > 0)
will guard against an infinite loop ifadd_cells()
ever called with negativen
. -
If
n
large, it can take a long time to find dead cells, as shooting at random has a small chance of hitting. -
If there are
n
more thanBOARD_WIDTH * BOARD_HEIGHT
, or if there are fewer dead cellsn
, the cycle will be named forever.
If it is n
large, or if there are only a few dead cells on the board, it would be more efficient to list the dead cells and select target cells at random from the dead cells. The disadvantage of this method will be slower if it n
is small, and there will be a lot of dead cells on the board.
The time complexity for n
is small compared to O (n) dead cells , which is hard to beat and should be very fast on current hardware, but it tends to be O (n * BOARD_WIDTH * BOARD_HEIGHT) if n
large or close to dead cells. which is much less efficient, and the function never ends if there is n
more than the number of dead cells.
-
If the board is known to be empty when called
add_cells()
, ifn
greater thanBOARD_WIDTH * BOARD_HEIGHT / 2
, it would be more efficient to set all cells alive and select cellsn
to kill. -
If the board is not necessarily empty passing this function, the number of live cells will help decide which approach is better, and if there are dead cells at least
n
, not requiring a long cycle to enumerate dead cells.
source to share