我需要编写一个算法来以这种方式移动矩阵的汽车：
蓝色向下移动;
红色向右移动
有一个转向,所有的蓝色的移动和转动移动所有的红色.
在读取文件之前,我不知道矩阵大小,如果它是密集或稀疏的,那么我必须实现两个数据结构(一个用于密集,一个用于稀疏)和两个算法.
我需要达到最佳的时间和空间复杂性.
由于未知的矩阵大小,我认为将数据存储在堆上.
如果矩阵是密集的,我想使用像：
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
但是找到下一个位置的问题仍然存在.
可能这不是最好的方法,所以如何以有效的方式实现稀疏的情况？ (也为稀疏使用独特的结构)
解决方法
这样,您就不需要分配额外的内存并读取所有数据,并且可以使用M [i] [j]简单有效地访问数据.
跨越行将是L1缓存友好.
在非常稀疏的数据的情况下,您可以扫描数据一次,并保留内存中的空区域/块列表(只需要存储启动和大小),然后您可以在进一步的运行中跳过(并在需要时调整) .
使用内存映射,只有经常访问的页面才能保存在内存中.这意味着一旦扫描了空的区域,内存只会被分配给经常访问的非空区域(所有这些都将由内核自动完成 – 无需自己跟踪).
另一个好处是您正在直接访问操作系统磁盘缓存.因此,无需在内核空间和用户空间之间继续复制和移动数据.
为了进一步优化空间和内存使用,汽车可以存储在文件中的2位.
更新：
I’ll have to move cars with openMP and MPI… Will the memory mapping
work also with concurrent threads?
您当然可以使用多线程,但不能确定openMP是否是这里最好的解决方案,因为如果您同时处理数据的不同部分,则可能需要检查一些重叠的区域(即,汽车可以从一个块移动到另一个).
或者您可以让线程在块的中间部分工作,然后启动其他线程来执行边界(红色车辆将是一个字节,蓝色汽车全排).
您还需要一个锁定机制来调整稀疏区域的列表.我认为最好的方式是启动单独的线程(取决于当然数据的大小).
