c++ - 在数组中找到两个最小 int64 元素的最快方法

Question

我有大小从 1000 到 10000 (1k .. 10k) 的数组。每个元素都是 int64。我的任务是找到数组中的两个最小元素，即最小元素和剩余元素中的最小元素。

我想在 C++ 中为 Intel Core2 或 Corei7(cpu 模式为 64 位)获得最快的单线程代码。

这个函数(从数组中取最小的 2 个)是热点，它嵌套在两个或三个迭代次数巨大的 for 循环中。

当前代码如下:

int f()
{
    int best; // index of the minimum element
    int64 min_cost = 1LL << 61;
    int64 second_min_cost = 1LL << 62;
    for (int i = 1; i < width; i++) {
     int64 cost = get_ith_element_from_array(i); // it is inlined
     if (cost < min_cost) {
        best = i;
        second_min_cost = min_cost;
        min_cost = cost;
     } else if (cost < second_min_cost) {
        second_min_cost = cost;
     }
    }
    save_min_and_next(min_cost, best, second_min_cost);
}

Answer 1

看partial_sort和 nth_element

std::vector<int64_t> arr(10000); // large

std::partial_sort(arr.begin(), arr.begin()+2, arr.end());
// arr[0] and arr[1] are minimum two values

如果你只想要第二低的值，nth_element 就是你的选择