c++ - 密集和稀疏矩阵的高效(时间和空间复杂度)数据结构

Question

我必须读取一个文件，其中存储了一个包含汽车的矩阵(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

但是寻找下一个位置的内容的问题仍然存在。

这可能不是最好的方法，那么我怎样才能有效地实现稀疏情况呢？ (也使用稀疏的独特结构)

Answer 1

为什么不简单地创建一个 memory mapping直接在文件上？ (假设你的数据0,1,2是存储在文件中连续的字节(或位)，这些字节的位置也代表了汽车的坐标)

这样你就不需要分配额外的内存和读入所有的数据，并且可以使用M[i][j]简单高效地访问数据。

遍历行将是 L1 缓存友好的。

在数据非常稀疏的情况下，您可以扫描一次数据并在内存中保留一个空区域/ block 的列表(只需要存储 startpos 和大小)，然后您可以跳过(并在需要的地方进行调整)在进一步的运行中。

有了内存映射，只有经常访问的页面才会保存在内存中。这意味着一旦您扫描了空区域，内存将只分配给经常访问的非空区域(所有这些都将由内核自动完成 - 无需您自己跟踪)。

另一个好处是您可以直接访问操作系统磁盘缓存。因此无需继续在内核空间和用户空间之间复制和移动数据。

为了进一步优化空间和内存使用，汽车可以存储在文件中的 2 位中。

更新:

I'll have to move cars with openMP and MPI... Will the memory mapping work also with concurrent threads?

您当然可以使用多线程，但不确定 openMP 是否是这里的最佳解决方案，因为如果您同时处理数据的不同部分，您可能需要检查一些重叠区域(即汽车可能会移动从一个街区到另一个街区)。

或者您可以让线程在 block 的中间部分工作，然后启动其他线程来处理边界(红色汽车是一个字节，蓝色汽车是一整行)。

您还需要一个锁定机制来调整稀疏区域列表。我认为最好的方法是启动单独的线程(当然取决于数据的大小)。