0

你还记得我之前的问题：是什么导致了std::async这里的数据竞争？
即使我成功地并行化了这个程序，它仍然运行得太慢而不实用。
所以我试图改进代表康威生命游戏模式的数据结构。
新结构的简要说明：

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 单元，以及每个具有 1 个或多个 ON 相邻单元的 OFF 单元。它还可以包含备用的 OFF 单元。
cells_coor通过使用它们的坐标作为键直接存储单元格，并将它们映射到它们的 ON 相邻单元格的数量（存储为int）以及它们是否为 ON（存储为bool）。

cells_neigh并cells_onoff通过迭代器将单元格间接存储为键。
一个单元的 ON 邻居数总是 0 或更大且 8 或更少，cells_neigh大小为 9 的数组也是如此。
cells_neigh[0]存储相邻单元格为 0 的单元格，cells_neigh[1]存储相邻单元格为 1 的单元格，依此类推。
同样，一个单元格总是关闭或打开，cells_onoff大小为 2 的数组也是如此。
cells_onoff[false]存储OFF单元，并cells_onoff[true]存储ON单元。
单元格必须插入或删除所有cells_coor,cells_neigh和cells_onoff。换句话说，如果一个单元格被插入其中一个或从其中一个中删除，那么其他的也必须如此。正因为如此，元素cells_neigh和cells_onoff是std::unordered_set将迭代器存储到实际单元中，从而通过邻居计数或关闭/开启状态快速访问单元。

如果这种结构有效，则插入函数的平均时间复杂度为O(1)，擦除也O(1)为 ，生成O(cells_coor.size())时间为 ，与之前的结构相比，时间复杂度有很大的提高。

但是如您所见，有一个问题：我如何散列 a std::unordered_map::const_iterator？
std::hash禁止对他们进行专业化，所以我必须定制一个。
获取他们的地址是行不通的，因为它们通常是作为右值或临时值获得的。
取消引用它们也不起作用，因为有多个单元格的相邻单元格为 0，或者多个单元格关闭，等等。
那我该怎么办？如果我不能做任何事情，cells_neigh并且cells_onoff将会std::vector或某事，会急剧降低时间复杂度。

4

1 回答 1

2

短篇小说：这行不通（真的很好）(*1)。您可能要在地图上执行的大多数操作都会使其元素的cells_coor任何迭代器（但不是指针，正如我所了解的）无效。

如果您想在某个集合上保留我所谓的不同“视图”，那么存储实际数据的底层容器需要不被修改或不能使其迭代器无效（例如链表）。

也许我遗漏了一些东西，但为什么不保留 9 组单元格用于邻居计数和 2 组单元格用于开/关？(*2)换一种说法：你真正需要这张地图是为了什么？(*3)

(*1)：映射仅在重新散列发生时使指针和迭代器无效。你可以检查一下：

// Before inserting
(map.max_load_factor() * map.bucket_count()) > (map.size() + 1)

(*2) : 9 组可以减少到 8 组：如果一个单元格 (x, y) 不在 8 组中，那么它将在第 9 组中。因此存储该信息是不必要的。开/关也一样：存储打开的单元格就足够了。其他都关了。

(*3) : 不使用地图而仅使用单元集访问邻居的数量，伪代码类型：

unsigned number_of_neighbours(Cell const & cell) {
  for (unsigned neighbours = 9; neighbours > 0; --neighbours) {
    if (set_of_cells_with_neighbours(neighbours).count() == 1) {
      return neighbours;
    }
  }
  return 0;
}

集合中的重复查找当然会破坏实际性能，您需要对其进行分析。（渐近运行时不受影响）

于 2017-03-04T13:46:50.000 回答