密集和稀疏矩阵的高效（时间和空间复杂性）数据结构

  • Z时代
  • 2024-01-10
  • 分类：问答

我必须读取一个文件，其中存储有汽车矩阵（ 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]。

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

如果数据非常稀疏，您可以扫描一次数据并在内存中保留一个空区域/块的列表（仅需要存储startpos和大小），然后可以跳过（并在需要的地方进行调整）以进一步运行。

使用内存映射，仅将经常访问的页面保留在内存中。这意味着一旦您扫描了空白区域，内存将仅分配给经常访问的非空白区域（所有这些操作将由内核自动完成-

无需自己进行跟踪）。

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

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

：

我将不得不使用openMP和MPI来移动汽车…内存映射是否也可以用于并发线程？

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

或者，您可以让线程在块的中间部分工作，然后启动其他线程来做边界（红色小车为一个字节，蓝色小车为整行）。

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

以上是 密集和稀疏矩阵的高效（时间和空间复杂性）数据结构 的全部内容， 来源链接： utcz.com/qa/420349.html

回到顶部