我必须读取一个文件，其中存储了一个包含汽车的矩阵（1=蓝色汽车，2=红色汽车，0=空车).
我需要编写一个算法来移动汽车矩阵的这种方式：
- 蓝色的会动downward;
- 红色的移动向右;
- 有一个turn其中所有蓝色的都移动，然后轮流移动所有红色的。
在读取文件之前，我不知道矩阵大小以及它是密集还是稀疏，所以我必须实现两种数据结构（一种用于密集，一种用于稀疏）和两种算法。
我需要到达可能的最佳时间和空间复杂度.
由于未知矩阵大小，我认为将数据存储在堆上。
如果矩阵是dense，我想使用类似的东西：
short int** M = new short int*[m];
short int* M_data = new short int[m*n];
for(int i=0; i< m; ++i)
{
M[i] = M_data + i * n;
}
通过这个结构，我可以分配连续的内存空间，并且访问起来也很简单M[i][j].
现在的问题是选择的结构sparse情况下，我还必须考虑如何以最简单的方式通过算法移动汽车：例如，当我评估一辆车时，我需要轻松找到在下一个位置（向下或向右）是否有另一辆车或如果它是空的。
最初我想定义继承自通用 Car 对象的 BlueCar 和 RedCar 对象。在这个对象中，我可以保存矩阵坐标，然后将它们放入：
std::vector<BluCar> sparseBlu;
std::vector<RedCar> sparseRed;
否则我可以做类似的事情：
vector< tuple< row, column, value >> sparseMatrix
但找到下一个位置是什么的问题仍然存在。
可能这不是最好的方法，那么如何才能有效地实现稀疏情况呢？ （也使用独特的稀疏结构）
为什么不简单地创建一个内存映射直接在文件上？ （假设您的数据 0,1,2 存储在文件中的连续字节（或位）中，并且这些字节的位置也代表汽车的坐标）
这样你就不需要分配额外的内存并读入所有数据，并且可以简单有效地访问数据M[i][j].
遍历这些行对 L1 缓存是友好的。
如果数据非常稀疏，您可以扫描一次数据，并在内存中保留一个空区域/块的列表（仅需要存储起始位置和大小），然后您可以在进一步的运行中跳过（并在需要时调整） 。
通过内存映射，只有经常访问的页面才会保留在内存中。这意味着一旦您扫描了空区域，内存将只分配给经常访问的非空区域（所有这些都将由内核自动完成 - 无需自己跟踪）。
另一个好处是您可以直接访问操作系统磁盘缓存。因此无需在内核空间和用户空间之间不断复制和移动数据。
为了进一步优化空间和内存使用，汽车可以以 2 位的形式存储在文件中。
Update:
我必须用 openMP 和 MPI 来移动汽车...内存映射会吗
也可以使用并发线程吗？
您当然可以使用多线程，但不确定 openMP 是否是这里的最佳解决方案，因为如果您同时处理数据的不同部分，您可能需要检查一些重叠区域（即一辆车可以从一个街区移动）到另一个）。
或者，您可以让线程在块的中间部分工作，然后启动其他线程来处理边界（红色汽车为一个字节，蓝色汽车为一整行）。
您还需要一个锁定机制来调整稀疏区域的列表。我认为最好的方法是启动单独的线程（当然取决于数据的大小）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
