在数组中查找两个最小 int64 元素的最快方法

Question

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

我想为 Intel Core2 或 Corei7（CPU 模式为 64 位）获得最快的 C++ 单线程代码。

这个函数（从数组中获取 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 为你的家伙

Answer 2

尝试反转 if：

if (cost < second_min_cost) 
{ 
    if (cost < min_cost) 
    { 
    } 
    else
    {
    }
} 

并且您可能应该使用相同的值初始化 min_cost 和 secondary_min_cost ，使用 int64 的最大值（或者更好地使用 qbert220 的建议）

Answer 3

一些小事情（可能已经发生了，但我想可能值得尝试）。

1. 稍微展开循环 - 比如说以 8 的步幅进行迭代（即一次缓存行），预取主体中的下一个缓存行，然后处理 8 个项目。为了避免大量检查，请确保结束条件是 8 的倍数，并且应在循环外部处理剩余的项目（少于 8） - 展开...

2. 对于不感兴趣的项目，您是在身体里做两次检查，也许你可以修剪到1？ ，如果 cost 小于 second_min，则也检查 min - 否则无需打扰...

Answer 4

您最好先检查 secondary_min_cost，因为它是唯一需要修改结果的条件。这样，您将在主循环中获得一个分支，而不是两个。这应该有很大帮助。

除此之外，几乎没有什么需要优化的，你已经接近最佳状态了。展开可能会有所帮助，但我怀疑它在这种情况下会带来任何显着的优势。

所以，它变成：

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 < second_min_cost)
    {
      if (cost < min_cost) 
      {
        best = i;
        second_min_cost = min_cost;
        min_cost = cost;
      } 
      else second_min_cost = cost;
    }
    save_min_and_next(min_cost, best, second_min_cost);
}

Answer 5

确保您的数组读取是自愿的，这样就不会引入不必要的缓存未命中。

假设数组读取很简单，这段代码可能应该非常接近现代 CPU 上的带宽限制。您需要分析和/或计算它是否仍有 CPU 优化的空间。

Answer 6

您所拥有的是 O(n) 并且对于随机数据来说是最佳的。这意味着，您已经拥有最快的了。

改进这一点的唯一方法是为数组赋予某些属性，例如，始终保持其排序或将其设为堆。

Answer 7

优点是您的算法会扫描一次数字。你是最理想的。

缓慢的一个重要原因可能来自元素的排列方式。如果它们在一个数组中，我的意思是一个 C 数组（或 C++ 向量），其中所有元素都是连续的，并且您向前扫描它们，那么从内存角度来看，您也是最佳的。否则，你可能会有一些惊喜。例如，如果您的元素位于链表中或分散聚集，那么您可能会因内存访问而受到惩罚。