我有一个类似这样的数据结构:
struct X {
float value;
int id;
};
一个由大小为N(约100,000)的元素组成的向量,按值排序(在程序执行期间保持不变):
std::vector<X> values;
现在,我想编写一个函数。
void subvector(std::vector<X> const& values,
std::vector<int> const& ids,
std::vector<X>& out /*,
helper data here */);
该函数填充传递的“ids”参数指定的值的已排序子集到“out”参数中(大小为Mvalues中偏移量的查找表lut(预处理,因此运行时间恒定)2.创建std::vector tmp,大小为N,填充无效ids(线性N)3.对于每个id,将values[lut[id]]复制到tmp[lut[id]](线性M)4.循环遍历tmp,将项复制到out中(线性N)。尽管这是线性的,但是临时变量和重复复制会导致问题。是否有比这更快的方法?请注意,M将接近N,因此O(MlogN)的事情是不利的。
编辑:http://ideone.com/xR8Vp 是所提到算法的一个示例实现,以使期望输出更加清晰,并证明它可以在线性时间内完成 - 问题在于是否有可能避免临时变量或以其他方式加速它,任何不是线性的都不会更快 :)。
tmp
的目的是什么?它最初来自哪里?为什么不直接在out
中构建输出,而不需要任何中间临时变量? - AnT stands with Russiaid
排序的第二个向量,可以通过使用equal_range
、copy
和最终按值排序sort
来获得M log N
的复杂度。 - clstrfsckvector
吗,特别是out
吗? - Wyatt Andersonvalues
中恰好有一个元素。 - etarion