3

我有大小从 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);
}
4

7 回答 7

8

看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 就是你的人

于 2011-10-17T12:08:36.447 回答
5

尝试反转 if：

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

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

于 2011-10-17T12:14:17.333 回答
3

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

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

  2. 对于不感兴趣的项目，您在体内进行了两次检查，可以修剪到1吗？即如果cost小于second_min，那么也要检查min- 否则不需要打扰......

于 2011-10-17T12:17:47.693 回答
2

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

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

所以，它变成：

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);
}
于 2011-10-26T14:04:03.857 回答
1

您在那里拥有的东西O(n)对于随机数据是最优的。这意味着，你已经拥有最快的了。

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

于 2011-10-17T12:02:48.723 回答
1

好处是您的算法会扫描数字一次。你是最优的。

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

于 2011-10-17T12:08:14.020 回答
1

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

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

于 2011-10-17T12:10:29.647 回答