10

我有一个稀疏矩阵类，其非零和相应的列索引按行顺序存储在基本上类似于 STL 向量的容器中。它们可能具有未使用的容量，例如向量；要插入/删除元素，必须移动现有元素。

假设我有一个手术insert_erase_replace，或ier简称。ier在给定位置p、列索引j和值的情况下，可以执行以下操作v：

  • 如果v==0，则ier删除 at 的条目p并左移所有后续条目。
  • 如果v!=0并且j已经存在于p，ier则将 处的单元格内容替换p为v。
  • 如果v!=0并且j不存在于 处p，则在右移所有后续条目之后ier插入条目v和列索引。jp

所以这一切都是微不足道的。

现在假设我有ier2，它做同样的事情，除了它需要一个包含多个列索引j和相应值的列表v。它还有一个 size n，它指示列表中存在多少索引/值对。但由于向量只存储非零，有时实际插入大小小于n.

还是微不足道的。

但是现在假设我有ier3，它不仅需要一个类似的列表ier2，而且还需要多个列表。这表示编辑稀疏矩阵的一部分。

在某些时候，遍历向量、逐个复制它们并ier2在到达每个插入点时插入/替换/擦除列表索引/值样式会变得更有效。如果总插入大小会导致我的向量无论如何都需要调整大小，那么我们就这样做。

鉴于我的向量比列表的总长度大得多，是否有一种算法可以有效地将列表合并到向量中？

到目前为止，这就是我所拥有的：

  • 传递给的每个列表ier3代表条目的净删除（左移）、净替换（不移动，因此便宜）或条目的净插入（右移）。那里可能还会对元素进行一些重新排列，但代价高昂的部分是净删除和净插入。

  • 找出一种算法来有效地只进行净插入或净删除并不难。

  • 当两者中的任何一个可能发生时，情况就会变得更加困难。

我唯一能想到的就是分两遍处理它：

  1. 擦除/替换
  2. 插入/替换

我们首先擦除，因为它更有可能任何插入都需要更少的副本。

这是正确的方法吗？有谁知道更好的吗？

4

4 回答 4

1

好的，所以我将假设每个列表中涵盖的间隔ier3是不相交的，并按顺序提供给您。如果它用于编辑矩阵的切片，这似乎是合理的。我还假设您不需要调整向量的大小，因为这种情况很容易检测和解决。

初始化一个read指针和一个write指向您正在编辑的向量开头的指针。也会有一个instruction指针ie3，但为了清楚起见，我将在这里忽略它。你还需要一个队列。在每个步骤中，可能会发生以下几种情况之一：

  • 默认值：既不在read也不write在由 详述的位置ier3。在这种情况下，将 under 的元素添加read到队列的后面，并将队列前面的元素写入到 under 的单元格中write。将两个指针向前移动一个。

  • read位于需要删除的单元格上。在这种情况下，只需向前移动read一个而不向队列中添加任何内容。

  • read从一个单元格传递到下一个单元格，以便在它们之间发生插入。在这种情况下，将插入添加到队列的后面，然后继续下一个相关案例。

  • read位于需要修改的单元格处。在这种情况下，将修改后的单元格插入队列的后面，将队列前面的任何内容写入write，然后将它们都向前推进。

  • read已达到向量的未使用容量。在这种情况下write，队列中只剩下任何东西。

这是基本大纲，但可以进行一些优化：首先，如果队列为空，则将两个指针向前移动到下一个位置，ie3而不做任何事情。其次，只要read在前面write且队列非空时，通过执行额外的写入步骤来最小化缓冲区。

于 2013-09-23T11:52:15.387 回答
0

我会按照您的计划进行，并突出显示一些要点。

擦除/替换步骤应从左侧开始，仅移动受影响范围内的点 - 它可以留下“间隙”。它应该确定最终向量的大小。在这一步结束时，使用确定的大小根据需要移动向量的“尾部”，留下插入所需的确切空间量。

插入应该从右侧开始，并通过将每个点复制到其最终位置来填补我们在步骤 1 中留下的空白。

这将永远不会移动主向量一次，并且永远不会复制任何点（从现有切片或插入集）超过两次，因此它本质上是线性的。

其他数据结构也可能有帮助 - 在前端和末端保留空间，或者将其构建为多个部分，因此调整大小不会强制完整复制。

进一步的优化是允许在步骤 1 中进行一些插入。如果您已经擦除了一些，则立即完成您遇到的任何插入直到它平衡将防止您需要移动任何点，直到您到达另一个擦除。

于 2013-09-12T22:56:03.947 回答
0

我可以为稀疏矩阵建议一种不同的设计，它应该可以帮助您实现大型稀疏矩阵的性能和低内存占用。为什么不使用 2D 哈希表而不是向量。类似的东西（没有 std:: 对于较小的代码）：

typedef unordered_map< unsigned /* index */, int /* value */ > col_type;
unordered_map< unsigned /* index */, col_type*>; // may need to define hash function for col_type

外部类 (sparse_matrix) 在 O(1) 中搜索列。如果没有找到，它会分配一个新列。然后在 O(1) 中搜索列类型以查找列索引，并根据原始逻辑进行删除/替换或插入。它可以查看该列现在是否为空并将其从“行”哈希映射中删除。

所有基本操作添加/删除/替换都是 O(1)。如果您需要矩阵的快速有序迭代，可以将 unordered_map 替换为“map”。如果矩阵非常稀疏，则 O(nlog(n)) 复杂度将类似于 hash_map 的。顺便说一句，我在钱包上使用了指向 col_type 的指针，外部哈希映射以这种方式增长得更快（很多！）。

于 2013-11-21T18:27:05.887 回答
0

设n为列表m的大小， 为向量的大小。听起来好像每次都ier进行二进制搜索，所以搜索部分是.jO(n*log(m))

假设列表中的元素已排序，一旦找到第一个元素，向上导航以查找下一个元素会更快。这样搜索就变成了O(log(m) + n) = O(n)。

此外，首先进行一次干传递以计算净删除/插入，然后进行第二次传递以实际应用更改。我认为这两个通行证会比您描述的两个通行证运行得更快。

于 2013-10-31T00:40:56.030 回答