Doc*_*awk 10 c++ algorithm vector sparse-matrix
我有一个稀疏矩阵类,它的非零和相应的列索引按行顺序存储在基本上类似STL-vector的容器中.他们可能有未使用的容量,如矢量; 要插入/删除元素,必须移动现有元素.
说我有手术insert_erase_replace,或ier简称.ier给定位置p,列索引j和值,可以执行以下操作v:
v==0,ier删除条目p并左移所有后续条目.v!=0和j已经存在的p,ier在替换单元格内容p有v.v!=0,并且j不存在p,ier则在右移所有后续条目后插入条目v和列索引.jp所以这一切都是微不足道的.
现在让我说我有ier2,它做了同样的事情,除了它采用包含多个列索引j和相应值的列表v.它还有一个大小n,表示列表中存在多少个索引/值对.但由于向量仅存储非零,有时实际插入大小小于n.
仍然微不足道.
但现在让我说我有ier3,不仅仅是一个列表ier2,而是多个列表.这表示编辑稀疏矩阵的切片.
在某些时候,迭代遍历向量,逐个复制它们并ier2在我们到达每个插入点时插入/替换/删除列表索引/值- 样式变得更有效.如果总插入大小会导致我的向量无论如何都需要调整大小,那么我们就这样做了.
鉴于我的向量比列表的总长度大得多,是否有一种算法可以有效地将列表合并到向量中？
到目前为止,这就是我所拥有的:
传递给每个列表ier3表示条目的净删除(左移),净替换(没有移动,因此便宜)或条目的净插入(右移).那里可能还有一些元素的重新安排,但昂贵的部分是净删除和净插入.
要弄清楚有效地进行网络插入或净删除的算法并不难.
当两者中的任何一个发生时,它会更难.
我唯一能想到的就是两次通过:
我们首先擦除因为它使得任何插入更有可能需要更少的副本.
这是正确的方法吗？有谁知道更好的一个？
我会同意你的计划，并强调一些要点。
擦除/替换步骤应从左侧开始，并且仅移动受影响范围内的点 - 它可能会留下“间隙”。它应该确定最终向量的大小。在此步骤结束时，使用确定的大小根据需要移动向量的“尾部”，留下插入所需的确切空间量。
插入应该从右侧开始，并通过将每个点复制到其最终位置来填补我们在步骤 1 中留下的空白。
这永远不会将主向量移动一次，并且永远不会将任何点（从现有切片或插入集）复制超过两次，因此它本质上是线性的。
其他数据结构也可能会有帮助 - 在前端和末尾保留空间，或者从多个部分构建它，这样调整大小就不会强制完整复制。
进一步的优化是在步骤 1 中允许进行一些插入。如果您删除了一些插入，则立即完成您遇到的任何插入直到其平衡，这将防止您需要移动任何点，直到到达另一次删除。