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

前端之家收集整理的这篇文章主要介绍了c – 将短列表合并成长向量的算法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我有一个稀疏矩阵类,其非零和相应的列索引按行顺序存储,基本上是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所详细说明的下一个位置,而不做任何事情.第二,当读取超过写入且队列非空时,通过执行额外的写入步骤来最小化缓冲区.

原文链接:https://www.f2er.com/c/112823.html

猜你在找的C&C++相关文章