python - C ++ - argsort 的矢量版本实现与 numpy 中的相比效率低
问题描述
这是我做的一个比较。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++ 程序执行相同的过程,但在引用此答案的向量上。
#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 custom (64-bit)
并g++ --version
打印 8.2.0。操作系统是 Manjaro Linux。
Edit2:我很想用这被删除了,因为我错误地在拔下笔记本电脑的直流适配器的情况下运行测试,这会导致它变慢。在公平竞争中,C 数组和向量版本的性能相同(大约需要 100 毫秒)。-O2
和-O3
标志编译g++
编译,我在 216.515 毫秒和 205.017 毫秒内得到了结果。这是一个改进,但仍然比 numpy 版本慢。(参考这个问题)
Edit3:另一种方法是将向量替换为 C 之类的数组: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;
}
解决方案
我采用了您的实现并用10000000
项目对其进行了测量。大约花了 1.7 秒。
现在我介绍了一个类
class valuePair {
public:
valuePair(int idx, float value) : idx(idx), value(value){};
int idx;
float value;
};
with 被初始化为
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 结果仍然相去甚远。
推荐阅读
- android - EditText & Button 的声明位置
- sql - 仅当存在一对值时,Postgres 才对来自 json 的值求和
- android - 将 Android AlertDialog 嵌入 UI 而不是弹出窗口
- c - 从文件读取时如何忽略多个输入?
- node.js - Redis 和 docker-compose 连接 127.0.0.1:6379
- google-apps-script - 通过使用一列工作表数据而不是硬编码的 ID 来提高 Apps 脚本的灵活性
- android - 如何使用 React Native IOS 和 Android 设备设置警报
- java - Java在迭代时将项目添加到ArrayList
- regex - 如何测试整个字符串是否仅包含一个特定字符
- html - 如何实现惊人的div?