受到这个问题的启发。
我的决定
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
int main(int argc, char * argv[])
{
vector<int> v(36000000);
int k = 0;
for(int i = 1; i <= 6000; ++i)
for(int j = 6001; j <= 12000; ++j)
v[k++] = i*j;
sort(v.begin(),v.end());
long long s = 0;
for(int i = 0; i < 36000000; ++i) s += v[i];
cout << s;
}
工作原理与 Python 中最好的差不多,但速度稍慢。在我的机器上,这一切都计为大约 2.04±0.01 秒。好吧,这不可能是 C ++ 不如 Python :) - 我开始尝试以各种方式加速这段代码。
无法优化,一切都依赖于sort
. 带着悲伤,我把它换成了stable_sort
——看看会发生什么,然后——你瞧!— 时间下降到 1.30±0.03 秒。
似乎一直有人说,在一般情况下,由于更大的复杂性stable_sort
(不仅是算法,它等于O(N·log(N) 2)),它的效果更差sort
。但是,事实证明,至少并非总是如此?我知道常数可能会有很大的不同:),但是它什么时候小于常数sort
?
在 G++ 下进行了检查-差异略有不同,但通常相同:1和2。
没有人对此进行深入研究,无法发表评论,如果两种功能都适合您,什么时候应用更有效?
视觉 C++ 2019,Windows 10
所有最好的排序算法都有复杂性
O(N * log(N))
。Python 变得更快,因为它使用了 TimSort,并且当数组由排序的部分组成时,它的运行速度非常快。在上面的双循环中得到的正是这个数组。std::sort
通常在大型数组上使用 QuickSort。这种排序没有利用数组部分已经排序的事实,在第一次迭代时它会破坏数组的结构。std::stable_sort
通常使用 MergeSort,它O(n)
比 QuickSort 需要更多的内存。正是由于额外的内存,默认使用了不稳定的排序。也许在 MergeSort 的 C++ 实现中,有一个优化可以检查子数组是否已经排序。在这种情况下,InsertionSort 可能不适用于小型子数组(检查子数组是否已经排序需要时间
O(n)
,而 InsertionSort 需要O(n^2)
时间)。如果子数组大小小于某个长度,则所有 3 种排序(TimSort、QuickSort、MergeSort)在内部使用插入排序。
用于比较的基准,
sort
由stable_sort
@wololo 提供,并由我稍作修改:该函数
int rand(int bits)
生成一个随机数的bits
位长。出于某种原因,数字的长度会影响排序的速度。这是我得到的(Visual C++ 2019,Windows 10):