C++ HashMap 或 Map 在时间复杂度和内存方面 space
C++ HashMap or Map in terms of time complexity and memory space
我要存储一个稀疏矩阵，其中的元素只是“1”或“2”（代表 BlueCar 和 RedCar）。
在读取带有逗号分隔值的 .csv 后，我只在运行时知道矩阵的大小。
我必须实施算法来移动汽车：
- 蓝色的移动向下;
- 红色的向右;
- 有一个转弯，其中所有蓝色的都移动，还有一个转弯所有红色的都移动（只有当目的地为空时才能移动汽车）。
所以算法必须：
- 循环遍历数据结构（向select红车或蓝车移动）
- 必须找到目标位置是否空闲。自由意味着'位置
不存在'，因为我只想保存现有的汽车
与他们的坐标相关联。
- 必须更新移动汽车的坐标或删除旧位置并插入新位置。
我必须选择在时间复杂度和内存使用方面高效的最佳数据结构来保存汽车和坐标。
详细来说，在接下来的实施步骤中，我必须处理 openMP 和 MPI。
最好使用带有键值对 (1) 的单一结构或每种车型一个结构 (2)我只需要保存坐标？
(1)我想了一个std::map<std::pair<row,column>,value>或std::unordered_map。
我不知道该选择什么，但我知道 map 访问是 O(logN) 而无序是 O(1)。我认为无序映射中的元素可以很容易地排序，因为我在读取文件时以有序的方式插入它们。
当汽车移动时，我必须更改它的坐标，这是 map/unordered_map 的关键。但现在的问题是：更改密钥（如果可能的话）还是删除并插入新的键值对更好？
(2) 如果在这种情况下第二种情况比第一种情况对我来说更好，我可以实现哪种数据结构？
因为，蓝车只是向下移动，所以，你只需要一个map< column, set<row>>来存储蓝车的位置。
同样，我们可以将红色汽车的位置存储为map< row, set<column>>
这将减少程序的内存使用，并可能加快查找性能。
案例map<column, set<row>>的查找性能会更好，因为我们知道map中使用的数据结构是二叉搜索树，所以map<pair<row, column> , value>，树的大小很大比前一种情况大。想象一下，您需要查找 <2,3>，因此，在后一种情况下，您可能需要遍历所有 <1,x> 对，直到到达 <2,x> 并最终到达目的地。
对于unordered_map，性能也更好，因为unordered_map使用散列，方法pair<row, column>需要将更多的项目映射到相同的[=33] =] 大小，与 map row 相比，因此碰撞次数要多得多。
此外，我们知道，最好是逐列处理蓝色汽车，然后逐行处理，因为这样的话，我们可以很容易地检测到有蓝色汽车的情况 (1, 1 ) 后面跟着 (2, 1) ，这可能会导致碰撞，所以用 unordered_map 存储蓝色汽车，然后按顺序集存储列可能会带来巨大的优势。因此，通过使用这种方法，我们可以根据需求和性能轻松地使用 map 或 unordered_map、set 或 unordered_set 进行交换。
我要存储一个稀疏矩阵，其中的元素只是“1”或“2”（代表 BlueCar 和 RedCar）。 在读取带有逗号分隔值的 .csv 后，我只在运行时知道矩阵的大小。 我必须实施算法来移动汽车：
- 蓝色的移动向下;
- 红色的向右;
- 有一个转弯，其中所有蓝色的都移动，还有一个转弯所有红色的都移动（只有当目的地为空时才能移动汽车）。
所以算法必须：
- 循环遍历数据结构（向select红车或蓝车移动）
- 必须找到目标位置是否空闲。自由意味着'位置 不存在'，因为我只想保存现有的汽车 与他们的坐标相关联。
- 必须更新移动汽车的坐标或删除旧位置并插入新位置。
我必须选择在时间复杂度和内存使用方面高效的最佳数据结构来保存汽车和坐标。
详细来说，在接下来的实施步骤中，我必须处理 openMP 和 MPI。
最好使用带有键值对 (1) 的单一结构或每种车型一个结构 (2)我只需要保存坐标？
(1)我想了一个std::map<std::pair<row,column>,value>或std::unordered_map。
我不知道该选择什么，但我知道 map 访问是 O(logN) 而无序是 O(1)。我认为无序映射中的元素可以很容易地排序，因为我在读取文件时以有序的方式插入它们。
当汽车移动时，我必须更改它的坐标，这是 map/unordered_map 的关键。但现在的问题是：更改密钥（如果可能的话）还是删除并插入新的键值对更好？
(2) 如果在这种情况下第二种情况比第一种情况对我来说更好，我可以实现哪种数据结构？
因为，蓝车只是向下移动，所以，你只需要一个map< column, set<row>>来存储蓝车的位置。
同样，我们可以将红色汽车的位置存储为map< row, set<column>>
这将减少程序的内存使用，并可能加快查找性能。
案例map<column, set<row>>的查找性能会更好，因为我们知道map中使用的数据结构是二叉搜索树，所以map<pair<row, column> , value>，树的大小很大比前一种情况大。想象一下，您需要查找 <2,3>，因此，在后一种情况下，您可能需要遍历所有 <1,x> 对，直到到达 <2,x> 并最终到达目的地。
对于unordered_map，性能也更好，因为unordered_map使用散列，方法pair<row, column>需要将更多的项目映射到相同的[=33] =] 大小，与 map row 相比，因此碰撞次数要多得多。
此外，我们知道，最好是逐列处理蓝色汽车，然后逐行处理，因为这样的话，我们可以很容易地检测到有蓝色汽车的情况 (1, 1 ) 后面跟着 (2, 1) ，这可能会导致碰撞，所以用 unordered_map 存储蓝色汽车，然后按顺序集存储列可能会带来巨大的优势。因此，通过使用这种方法，我们可以根据需求和性能轻松地使用 map 或 unordered_map、set 或 unordered_set 进行交换。