通过未排序的列表改进搜索

Question

我的代码花了40%的时间来搜索未分类的向量.更具体地,搜索功能my_search重复地接收单个未分类的长度矢量N,其中N可以取10到100,000之间的任何值.与每个元素相关联的权重具有相对小的方差(例如[0.8,0.81,0.85,0.78,0.8,0.7,0.84,0.82,...]).

该算法my_search首先对每个对象的所有权重求和,然后N用替换样本计算元素的平均值(与向量的长度一样多).该算法非常类似于

int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];
}

从这篇文章.

我可以在搜索之前对矢量进行排序,但是需要O(N log N)的顺序(取决于所使用的排序算法)并且我怀疑(但可能是错误的,因为我没有尝试过)我会获得很多时间特别是因为权重几乎没有变化.

另一种解决方案是存储在一系列点之前有多少重量的信息.例如,在对矢量求和时,每N/10个元素,我可以存储已经总和了多少权重的信息.然后,我可以首先与rnd这10个断点进行比较,并仅搜索向量总长度的十分之一.

• 这会是一个很好的解决方案吗？
• 我描述的流程有名称吗？
• 如何根据函数估计要存储的正确断点数N？
• 有更好的解决方案吗？

Answer 1

log(N) 解

{
    std::vector<double> sums;
    double sum_of_weight = 0;
    for(int i=0; i<num_choices; i++) {
       sum_of_weight += choice_weight[i];
       sums.push_back(sum_of_weight);
    }

    std::vector<double>::iterator high = std::upper_bound(sums.begin(), sums.end(), random(sum_of_weight));

    return std::distance(sums.begin(), high);
}

基本上你有一个更好的方法来解决它的想法,但不是只存储10个元素,存储所有元素并使用二进制搜索来找到最接近你的值的索引.

分析

即使这个解决方案是O(logN),你真的要问自己是否值得.是否值得创建一个额外的向量,从而累积额外​​的时钟周期来存储向量中的内容,向量调整大小所需的时间,调用函数执行二进制搜索所需的时间等等？

正如我上面写的那样,我意识到你可以使用一个deque代替,这几乎可以摆脱因为必须调整和复制向量内容而不影响向量的O(1)查找而导致的性能损失.

所以我想问题仍然存在,是否值得将元素复制到另一个容器中然后才进行O(logN)搜索？

结论

TBH,我不认为你从这个优化中获得了很多.事实上,我认为你获得了开销O(logN).