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

Question

我的代码将 40% 的时间用于搜索未排序的 vector 。更具体地说，搜索函数 my_search 重复接收长度为 N 的单个未排序 vector ，其中 N 可以取 10 到 100,000 之间的任何值。与每个元素关联的权重具有相对较小的方差(例如 [0.8, 0.81, 0.85, 0.78, 0.8, 0.7, 0.84, 0.82, ...])。

my_search 算法首先对每个对象的所有权重求和，然后对 N 元素(与 vector 的长度一样多)进行替换采样。该算法非常类似于

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];
}

来自 this post .

我可以在搜索之前对 vector 进行排序，但需要花费 O(N log N) 的时间(取决于使用的排序算法)并且我怀疑(但可能是错误的，因为我没有尝试过)我会获得很多时间，尤其是因为权重几乎没有差异。

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

• 这是一个好的解决方案吗？
• 我描述的过程有名称吗？
• 如何根据 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);
}

本质上与您有更好的解决方法的想法相同，但不是只存储十分之一的元素，而是存储所有元素并使用二进制搜索找到最接近您的值的索引。

---

分析

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

当我写上面的时候，我意识到你可以使用 deque 来代替，这几乎可以消除因必须调整大小和复制 vector 内容而不影响O(1) vector 查找。

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

结论

TBH，我认为您从这次优化中获得的 yield 不多。事实上，我认为您获得了 O(logN) 的开销。