我必须读取一个文件，其中存储了一个带有汽车的矩阵（1=BlueCar，2=RedCar，0=Empty）。
我需要编写一个算法来以这种方式移动矩阵的汽车：
- 蓝色的向下移动
- 红色的向右移动
- 有一个转弯，所有蓝色的都移动，还有一个转弯移动所有红色的
在读取文件之前，我不知道矩阵大小，也不知道它是密集的还是稀疏的，所以我必须实现两个数据结构（一个用于密集，一个用于稀疏）和两个算法。
我需要尽可能达到最佳时间和空间复杂性。
由于矩阵大小未知，我想将数据存储在堆上。
如果矩阵密集，我想使用类似于的东西
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]访问也很简单。
现在的问题是为稀疏情况选择的结构，我还必须考虑如何以最简单的方式通过算法移动汽车：例如，当我评估一辆汽车时，我需要很容易地发现在下一个位置（向下或向右）是否有另一辆汽车或它是空的。
最初，我想定义从通用Car对象继承的BlueCar和RedCar对象。在这个对象中，我可以保存矩阵坐标，然后将它们放入：
std::vector<BluCar> sparseBlu;
std::vector<RedCar> sparseRed;
否则我可以做一些类似的事情：
vector< tuple< row, column, value >> sparseMatrix
但找到下一个位置的问题仍然存在。
这可能不是最好的方法，那么我如何以有效的方式实现稀疏情况呢？（也使用唯一的稀疏结构）
为什么不直接在文件上创建一个内存映射呢？（假设你的数据0,1,2存储在文件中的连续字节（或位）中，这些字节的位置也代表汽车的坐标）
这样，您就不需要分配额外的内存并读入所有数据，并且可以使用M[i][j]简单高效地访问数据。
遍历这些行将是一级缓存友好的。
在数据非常稀疏的情况下，您可以扫描一次数据，并在内存中保留一个空区域/块的列表（只需要存储startpos和大小），然后在进一步的运行中跳过（并在需要的地方进行调整）。
使用内存映射，只有频繁访问的页面才会保留在内存中。这意味着，一旦扫描了空区域，内存将只分配给频繁访问的非空区域（所有这些都将由内核自动完成，无需自己跟踪）。
另一个好处是您可以直接访问操作系统磁盘缓存。因此，无需在内核空间和用户空间之间不断复制和移动数据。
为了进一步优化空间和内存的使用，汽车可以存储在文件中的2位中。
更新：
我必须用openMP和MPI来移动汽车。。。内存映射还可以使用并发线程吗？
你当然可以使用多线程，但不确定openMP是否是最好的解决方案，因为如果你同时处理数据的不同部分，你可能需要检查一些重叠的区域（即汽车可能从一个块移动到另一个块）。
或者，您可以让线程处理块的中间部分，然后启动其他线程来处理边界（红色的车是一个字节，蓝色的车是整行）。
您还需要一个锁定机制来调整稀疏区域的列表。我认为最好的方法是启动单独的线程（当然，这取决于数据的大小）。
在一个类似的任务中，我只是使用了压缩行存储。
压缩行和列（在下一节中）存储格式是最普遍的：他们对矩阵的稀疏性结构，并且它们不存储任何不必要的元素。另一方面，他们的效率不是很高，需要中每个标量操作的间接寻址步骤矩阵向量乘积或预条件求解。
您需要更加具体地了解时间和空间的复杂性要求。CSR对于简单的操作需要一个额外的索引步骤，但如果您只是在做简单的矩阵操作，那么这只是一个很小的开销。
已经有一个现有的C++实现可以在线获得。