c – 将短列表合并成长向量的算法

发布时间：2020-12-16 02:58:59 所属栏目：百科来源：网络整理

导读：我有一个稀疏矩阵类,其非零和相应的列索引按行顺序存储,基本上是STL向量的容器.他们可能没有能力,像矢量;并且要插入/删除元素,必须移动现有元素. 说我有一个操作,insert_erase_replace或者简单的ier.给定一个位置p,一个列索引j和一个值v,可以执行以下操作：

我有一个稀疏矩阵类,其非零和相应的列索引按行顺序存储,基本上是STL向量的容器.他们可能没有能力,像矢量;并且要插入/删除元素,必须移动现有元素.

说我有一个操作,insert_erase_replace或者简单的ier.给定一个位置p,一个列索引j和一个值v,可以执行以下操作：

>如果v == 0,ier删除p中的条目,并左移所有后续条目.
>如果v！= 0,并且j已经存在于p,则用p替换p处的单元格内容.
>如果v！= 0,并且j不存在于p,则在右移所有后续条目之后,ier将条目v和列索引j插入p.

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

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

还是微不足道

但现在我们说我有ier3,它不仅仅是一个列表,如ier2,而是多个列表.这表示编辑稀疏矩阵的切片.

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

假设我的向量比列表的总长度大得多,是否有一个有效地将列表合并到向量中的算法？

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

>传递给ier3的每个列表表示条目的净删除(左移),净替换(无移动,因此便宜)或条目的净插入(右移).在那里也可能有一些重新安排的元素,但昂贵的部分是净删除和净插入.
>很难找出一种可以有效地执行网络插入或净删除的算法.
>当两者中的任何一个可能发生时,更难.

我唯一可以想到的是两次处理：

>擦除/更换
>插入/替换

我们先擦除,因为它使得任何插入更可能需要更少的副本.

这是正确的做法吗？有没有人知道更好的一个？

解决方法

好的,所以我想假设ier3中每个列表中包含的时间间隔是不相交的,并按顺序给你.如果这是用于编辑矩阵的切片,这似乎是合理的.我也假设你不需要调整矢量大小,因为这种情况是容易检测和可解决的.

初始化一个读取指针和一个写入指针,指向您正在编辑的向量的开头.还有一个指向ie3的指针,但为了清楚起见,我将忽略这一点.你也需要一个队列.在每一步,几件事情之一可能发生：

>默认值：读取和写入都不在ier3详细说明的位置.在这种情况下,将读取的元素添加到队列的后面,并将队列前面的元素写入到写入的单元格中.将两个指针向前移动一个.
>读取在需要删除的单元格上.在这种情况下,只需移动向前读取,而不向队列中添加任何内容.
>读取从一个单元格到下一个单元格的传递,以便插入应该在它们之间发生.在这种情况下,将插入添加到队列的后面,然后继续下一个相关的情况.
>读取在需要修改的单元格上.在这种情况下,将修改后的单元格插入队列后面,写入队列前面要写入的内容,然后将它们向前.
读取已经到达了矢量的未使用容量.在这种情况下,只需写入队列中剩下的任何东西.

这是基本的大纲,但可以进行几个优化：首先,如果队列为空,则将两个指针前进到ie3所详细说明的下一个位置,而不做任何事情.第二,当读取超过写入且队列非空时,通过执行额外的写入步骤来最小化缓冲区.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!