您是否還記得我之前的問題:What is causing data race in std::async
here?
即使我成功並行化了這個程序,它仍然仍然跑得太慢而不切實際。
所以我試圖改進代表康威的生命遊戲模式的數據結構。
新結構的簡要說明:如何散列std :: unordered_map :: const_iterator?
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, std::pair<int, bool>> cells_coor;
std::unordered_set<decltype(cells_coor)::const_iterator> cells_neigh[9];
std::unordered_set<decltype(cells_coor)::const_iterator> cells_onoff[2];
public:
void insert(int x, int y) {
// if coordinate (x,y) isn't already ON,
// turns it ON and increases the neighbor's neighbor count by 1.
}
void erase(int x, int y) {
// if coordinate (x,y) isn't already OFF,
// turns it OFF and decreases the neighbor's neighbor count by 1.
}
pattern generate(NDos::Liferule rule) {
// this advances the generation by 1, according to the rule.
// (For example here, B3/S23)
pattern result;
// inserts every ON cell with 3 neighbors to result.
// inserts every OFF cell with 2 or 3 neighbors to result.
return result;
}
// etc...
};
簡言之,pattern
包含細胞。它包含每個ON單元,以及每個OFF單元具有一個或多個ON鄰居單元。它也可以包含備用OFF單元。
cells_coor
通過使用它們的座標作爲關鍵字直接存儲單元格,並將它們映射到ON鄰居單元格的數目(存儲爲int
)以及它們是否爲ON(存儲爲bool
)。
cells_neigh
and cells_onoff
通過迭代器將它們作爲關鍵字間接存儲單元。
單元的ON鄰居數始終爲0或更大,8或更小,因此cells_neigh
是9號陣列。
cells_neigh[0]
用0 ON鄰居小區存儲小區,cells_neigh[1]
用1個ON鄰居小區存儲小區,依此類推。
同樣,單元總是OFF或ON,所以cells_onoff
是大小2的數組。
cells_onoff[false]
存儲OFF單元,並且cells_onoff[true]
存儲ON單元。
電池必須插入或擦除所有cells_coor
,cells_neigh
和cells_onoff
。換句話說,如果一個單元格被插入到其中一個單元格中或從其中刪除,那麼其他單元格也必須如此。因此,cells_neigh
和cells_onoff
的元素是std::unordered_set
將迭代器存儲到實際單元中,從而可以通過相鄰計數或OFF/ON狀態快速訪問單元。
如果這種結構工程,插入功能將有O(1)
平均時間複雜度,擦除也O(1)
,並且產生O(cells_coor.size())
,這是從現有結構的時間複雜度很大improval。
但正如你所看到的,有一個問題:如何散列std::unordered_map::const_iterator
?
std::hash
禁止爲他們專門化,所以我必須做一個自定義的。
考慮到他們的地址是行不通的,因爲他們通常是作爲右值或臨時對象獲得的。
取消引用它們也不起作用,因爲有多個單元格有0個ON鄰居單元,或多個單元關閉等。
那麼,我該怎麼做?如果我什麼都做不了,cells_neigh
和cells_onoff
會是std::vector
什麼的,大大降低了時間複雜度。
你認爲也許有一個原因'std :: hash'禁止他們的專業化?我想我可以明白爲什麼你想要這個,但是海事組織是另一個存儲迭代器並不總是最好的主意的證據。不過,我沒有替代品。順便說一句,你的地圖缺少一個值類型;你的意思是'unordered_set'嗎? –
@LightnessRacesinOrbit我不知道爲什麼'std :: hash'確實存在,但是,我想存儲迭代器,因爲它們之間必須有通信。如果一個單元格被插入到一個單元格中,它也必須被插入到其他單元格中,等等。 –
@Tony D抱歉,他們必須是'std :: unordered_set'。固定。 –