python - C++ - argsort 的 vector 版本实现与 numpy 中的相比效率低

Question

这是我做的比较。 np.argsort 在包含 1,000,000 个元素的 float32 ndarray 上计时。

In [1]: import numpy as np

In [2]: a = np.random.randn(1000000)

In [3]: a = a.astype(np.float32)

In [4]: %timeit np.argsort(a)
86.1 ms ± 1.59 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

这里是一个 C++ 程序执行相同的过程，但在引用 this answer 的 vector 上.

#include <iostream>
#include <vector>
#include <cstddef>
#include <algorithm>
#include <opencv2/opencv.hpp>
#include <numeric>
#include <utility>
int main()
{
  std::vector<float> numbers;
  for (int i = 0; i != 1000000; ++i) {
    numbers.push_back((float)rand() / (RAND_MAX));
  }

  double e1 = (double)cv::getTickCount();

  std::vector<size_t> idx(numbers.size());
  std::iota(idx.begin(), idx.end(), 0);

  std::sort(idx.begin(), idx.end(), [&numbers](const size_t &a, const size_t &b)
                                               { return numbers[a] < numbers[b];});

  double e2 = (double)cv::getTickCount();
  std::cout << "Finished in " << 1000 * (e2 - e1) / cv::getTickFrequency() << " milliseconds." << std::endl;
  return 0;
}

它打印 Finished in 525.908 milliseconds. 并且比 numpy 版本慢得多。那么谁能解释一下是什么让 np.argsort 如此之快？谢谢。

---

Edit1:np.__version__ 返回 1.15.0，它在 Python 3.6.6 |Anaconda 自定义(64 位) 和 g++ --version 打印 8.2.0。操作系统为 Manjaro Linux。

---

Edit2:我试图在 g++ 中使用 -O2 和 -O3 标志进行编译，我在 216.515 毫秒内得到了结果并且205.017 毫秒。这是一个改进，但仍然比 numpy 版本慢。 ( Referring to this question ) 这被删除是因为我错误地在我的笔记本电脑的直流适配器拔掉的情况下运行测试，这会导致它变慢。在公平竞争中，C 数组和 vector 版本的性能相当(大约需要 100 毫秒)。

---

Edit3:另一种方法是用 C 语言替换 vector ，例如数组:float numbers[1000000];。之后运行时间约为 100 毫秒(+/-5 毫秒)。完整代码在这里:

#include <iostream>
#include <vector>
#include <cstddef>
#include <algorithm>
#include <opencv2/opencv.hpp>
#include <numeric>
#include <utility>
int main()
{
  //std::vector<float> numbers;
  float numbers[1000000];
  for (int i = 0; i != 1000000; ++i) {
    numbers[i] = ((float)rand() / (RAND_MAX));
  }

  double e1 = (double)cv::getTickCount();

  std::vector<size_t> idx(1000000);
  std::iota(idx.begin(), idx.end(), 0);

  std::sort(idx.begin(), idx.end(), [&numbers](const size_t &a, const size_t &b)
                                               { return numbers[a] < numbers[b];});

  double e2 = (double)cv::getTickCount();
  std::cout << "Finished in " << 1000 * (e2 - e1) / cv::getTickFrequency() << " milliseconds." << std::endl;
  return 0;
}

Answer 1

我采用了您的实现并用 10000000 项对其进行了测量。大约用了 1.7 秒。

现在我介绍一个类

class valuePair {
  public:
    valuePair(int idx, float value) : idx(idx), value(value){};
    int idx;
    float value;
};

初始化为

std::vector<valuePair> pairs;
for (int i = 0; i != 10000000; ++i) {
    pairs.push_back(valuePair(i, (double)rand() / (RAND_MAX)));
}

排序是用

完成的

std::sort(pairs.begin(), pairs.end(), [&](const valuePair &a, const valuePair &b) { return a.value < b.value; });

此代码将运行时间减少到 1.1 秒。我认为这是由于更好的缓存一致性，但与 python 结果相去甚远。