Do you remember my prior question: What is causing data race in std::async
here?
Even though I successfully parallelized this program, it still ran too slowly to be practical.
So I tried to improve the data structure representing a Conway's Game of Life pattern.
Brief explanation of the new structure:
class pattern {
// NDos::Lifecell represents a cell by x and y coordinates.
// NDos::Lifecell is equality comparable, and has std::hash specialization.
private:
std::unordered_map<NDos::Lifecell, const std::pair<int, bool>> cells_coor;
std::unordered_map<decltype(cells_coor)::const_iterator> cells_neigh[9];
std::unordered_map<decltype(cells_coor)::const_iterator> cells_onoff[2];
public:
// insertion function : makes a cell ON.
// erasure function : makes a cell OFF.
// generation function : advances the pattern to the next generation.
// etc...
};
In brief, pattern
contains the cells. It contains every ON cells, every OFF cells that has 1 or more ON neighbor cells. It can also contain spare OFF cells.
cells_coor
directly stores the cells, by using their coordinates as keys, and maps them to their number of ON neighbor cells (stored as int
) and whether they are ON (stored as bool
).
cells_neigh
and cells_onoff
indirectly stores the cells, by the iterators to them as keys.
cells_neigh[0]
stores the cells with 0 ON neighbor cells, cells_neigh[1]
stores the cells with 1 ON neighbor cell, and to on.
cells_onoff[false]
stores the OFF cells, and cells_onoff[true]
stores the ON cells.
If this structure works, the insertion function will have average time complexity of O(1)
, the erasure also O(1)
, and the generation O(cells_coor.size())
, which are great improval of time complexity from the prior structure.
But as you see, there is a problem: How can I hash a std::unordered_map::const_iterator
?
std::hash
prohibits a specialization for them, so I have to make a custom one.
Taking their address won't work, as they are usually acquired as rvalues or temporaries.
Dereferencing them also won't work, as there are multiple cells that have 0 ON neighbor cells, or multiple cells that is OFF, etc.
So what can I do? If I can't do anything, cells_neigh
and cells_onoff
will be std::vector
or something, sharply degrading the time complexity.
Aucun commentaire:
Enregistrer un commentaire