c++ - 为什么排序调用比较函数的频率低于线性最小搜索算法？

Question

我将从提供一些背景信息开始。我正在学习编写光线追踪器，一个非常简单的。我还没有任何加速结构，所以有问题的代码旨在找到射线击中的最近的对象。由于我还在学习，如果答案集中在我观察到的看似奇怪的问题上，我将不胜感激 - 我知道 RT 逻辑现在是非常错误的。无论如何，它会产生正确的结果。

1. 第一种方法:对于每次命中，将命中结果结构对象添加到列表中，然后应用std::sort。带有一个谓词，该谓词比较从命中点到射线原点的距离。应该是O(N log N)根据教科书，我认为它不是最优的，因为我只需要第一个结果，而不是整个排序列表。

2. 第二种方法:每当命中时，取距离并将其与最小值进行比较，该值首先被初始化为std::numeric_limits<float>::max()。 .那么，您的标准“在数组中查找最小值”算法。应该是O(N)从而更快。

这些代码片段驻留在一个递归函数中。在包含 10 个球体的相同场景中进行测试，1 的速度提高了一个数量级。距离函数的调用量比2少了好几倍。我错过了什么？ 我不确定是否需要上下文，如果这个问题有“要切断的分支”，请告诉我。

---

代码片段 1:

result rt_function(...) {
static int count{};
std::vector<result> hitList;
for(const auto& obj : objList) {
    const result res = obj->testOuter(ray);
    if ( res.hit ) {
        hitList.push_back(res);
    }
}
if (!hitList.empty()) {
    sort(hitList.begin(), hitList.end(), [=](result& hit1, result& hit2) -> bool {
            std::cerr << ++count << '\n';
            return cv::norm(hit1.point - ray.origin) <
                   cv::norm(hit2.point - ray.origin);
        });
    const result res = hitList.front();
    const SceneObject* near = res.obj;
    // the raytracing continues...

count == 180771

---

代码片段 2:

result rt_function(...) {
static int count{};
float min_distance = std::numeric_limits<float>::max(), distance{};
result closest_res{}; bool have_hit{};
for(const auto& obj : objList) {
    const result res = obj->testOuter(ray);
    if ( res.hit ) {
        have_hit = true;
        std::cerr << ++count << '\n';
        distance = cv::norm(res.point - ray.origin);
        if (distance < min_distance) {
            min_distance = distance; closest_res = res;
        }
    }
}
if (have_hit) {
    const result res = closest_res;
    const SceneObject* near = res.obj;
    // the raytracing continues...

count == 349633

我想(a)理解为什么比较少以及(b)瓶颈在哪里，因为运行时间明显更长，正如我如上所述。

Answer 1

像 O(N²) 这样的语句就像一个维度；双倍的点数和四倍的时间。对于较小的 N，O(log N) 算法可能会很慢，关键是如果 N 加倍或增加 10 倍运行时间则不会。

与在 1000 页字典中查找特定单词和在 20 个单词的句子中查找特定单词进行比较。在找到特定单词之前对 20 个单词的句子进行排序比直接通读一次要花费更长的时间。