如何快速从已排序的向量中获取已排序的子向量

Question

我有这样的数据结构:

struct X {
  float value;
  int id;
};

那些矢量(大小为N(思考100000),按值排序(在程序执行期间保持不变):

std::vector<X> values;

现在,我想写一个函数

void subvector(std::vector<X> const& values, 
               std::vector<int> const& ids, 
               std::vector<X>& out /*, 
               helper data here */);

填充所述出用的排序子集的参数值由所传递的给定的,IDS(大小中号 < Ñ(约0.8倍Ñ)),快速(存储器是不是一个问题,这将被重复进行的,因此构建lookuptables(该来自函数参数的辅助数据)或只做一次的其他东西完全没问题.

到目前为止我的解决方案:
构建可查找的lut包含id - > offset in values(准备,所以常量运行时)
创建std::vector<X> tmp,大小N,填充 每个id的无效ID(线性为N)
,复制values[lut[id]]到tmp[lut[id]](M中的线性)
循环tmp,将项目复制到输出(N中的线性)

这在N中是线性的(因为它大于M),但临时变量和重复复制会让我感到困惑.有没有办法比这更快？注意,M将接近N,因此O(M log N)是不利的.

编辑:http://ideone.com/xR8Vp是上述算法的示例实现,以使所需的输出清晰并证明它在线性时间内是可行的 - 问题是关于避免临时变量或加速它的可能性其他一些方式,不是线性的东西不是更快:).

Answer 1

您可以尝试的另一种方法是使用哈希表而不是向量来查找 id：

void subvector(std::vector<X> const& values, 
               std::unordered_set<int> const& ids, 
               std::vector<X>& out) {

    out.clear();
    out.reserve(ids.size());
    for(std::vector<X>::const_iterator i = values.begin(); i != values.end(); ++i) {
        if(ids.find(i->id) != ids.end()) {
            out.push_back(*i);
        }
    }
}

这以线性时间运行，因为unordered_set::find预期时间是恒定的（假设我们对整数进行哈希处理没有问题）。但是我怀疑它在实践中可能不如您最初描述的使用向量的方法那么快。