这不是一个算法问题,而是一个实现问题.
我有一个看起来像这样的数据结构:
struct MyStruct {
float val;
float val2;
int idx;
}
我浏览了大约4000万个元素的数组,并将'val'字段指定为元素,并将'idx'字段指定为索引.
我接着说:
MyStruct* theElements = new MyStruct[totalNum];
qsort(theElements, totalNum, sizeof(MyStruct), ValOrdering);
然后,一旦我填写val2,逆转程序
qsort(theElements, totalNum, sizeof(MyStruct), IndexOrdering);
哪里
static int ValOrdering(const void* const v1, const void* const v2)
{
if (((struct MyStruct*) v1)->val < ((struct MyStruct*) v2)->val)
return -1;
if (((struct MyStruct*) v1)->val> ((struct MyStruct*) v2)->val)
return 1;
return 0;
}
和
static int IndexOrdering(const void* const v1, const void* const v2)
{
return ((struct MyStruct*) v1)->idx- ((struct MyStruct*) v2)->idx;
}
此设置需要4秒才能执行这两种排序.对于3Ghz i5处理器来说,4秒钟似乎需要很长时间才能使用4000万个元素.有更快的方法吗？我正在将vs2010与英特尔编译器一起使用(它有各种各样的结构,但我没有看到这样的结构).
更新:使用std :: sort刮掉大约0.4秒的运行时,称为:
std::sort(theElements, theElements + totalPixels, ValOrdering);
std::sort(theElements, theElements + totalPixels, IndexOrdering);
和
bool GradientOrdering(const MyStruct& i, const MyStruct& j){
return i.val< j.val;
}
bool IndexOrdering(const MyStruct& i, const MyStruct& j){
return i.idx< j.idx;
}
在谓词中添加'inline'关键字似乎并不重要.由于我有,并且规范允许,四核机器,我接下来将检查某种多线程排序.
更新2:关注@SirGeorge和@stark,我看了一下通过指针重定向完成的单一排序:
bool GradientOrdering(MyStruct* i, MyStruct* j){
return i->val< j->val;
}
bool IndexOrdering(MyStruct* i, MyStruct* j){
return i->idx< j->idx;
}
即使只有一个排序调用(对于GradientOrdering例程),生成的算法也需要5秒,比qsort方法长1秒.看起来std :: sort现在正在赢.
更新3:看起来英特尔tbb::parallel_sort是赢家,在我的系统上将单一运行时间降低到0.5秒(因此,对于两者都是1.0秒,这意味着它从两者的原始4.0开始很好地扩展).我试着去与微软提出的并行花式这里,但因为我已经使用TBB和语法parallel_sort是相同的语法std::sort,我可以用我以前的std::sort比较得到的一切完成.
我还使用了@ gbulmer的建议(实际上,击中了我头上的实现),我已经拥有原始的indeces,所以我只需要为第二个数组分配第二个数组,而不是第二个数组.回到排序顺序.我可以放弃这种内存使用,因为我只在具有至少4 GB RAM的64位机器上进行部署(很好地提前完成这些规范); 没有这方面的知识,第二种就是必要的.
@ gbulmer的建议提供了最快的速度,但最初的问题是关于最快的排序. std::sort是最快的单线程,parallel_sort是最快的多线程,但没有人给出答案,所以我给@gbulmer检查.
Bil*_*eal 14
一般来说,C++ std::sort位于其中algorithm将会失败qsort,因为它允许编译器优化对函数指针的间接调用,并使编译器更容易执行内联.然而,这只是一个恒定因素加速; qsort已经使用了非常快速的排序算法.
请注意,如果您决定切换到std::sort,则必须更改比较仿函数.std::sort接受一个简单的小于比较返回bool,同时std::qsort接受一个返回-1,0或1的仿函数,具体取决于输入.
与缓存相比，数据集是巨大的，因此缓存到内存是有限的。
使用间接会使情况变得更糟，因为指针有缓存，并且内存以更随机的顺序访问，即不与邻居进行比较。该程序正在对抗 CPU 中的任何预取机制
考虑将结构分成两个结构，在两个数组中。
作为一个实验，比较 pass 1 和 pass 1，其中结构只是 { float val; int idx; };
如果是缓存和带宽限制，它应该会产生显着差异。
如果缓存位置是一个关键问题，那么可能值得考虑多路合并或 Shell 排序；任何可以改善局部性的东西。
尝试对记录的缓存大小子集进行排序，然后进行多路合并排序（可能值得查看处理器缓存管理器规范，看看是否清楚尝试预期的预取流的数量。再次，减少通过减少从 RAM 流入的结构的大小，数据集的大小可能是赢家。
idx 字段是如何导出的？听起来像是数组中的原始位置。它是原始记录的索引吗？
如果是这种情况，只需分配第二个数组，然后将第一个数组复制到第二个数组中：
struct { float val; float val2; int idx } sortedByVal[40000000];
struct { float val; float val2 } sortedbyIdx[40000000];
for (int i=0; i<40000000; ++i) {
sortedbyIdx[sortedByVal[i].idx].val = sortedByVal[i].val;
sortedbyIdx[sortedByVal[i].idx].val2 = sortedByVal[i].val2;
}
没有第二类。如果是这种情况，请将 val2 值的分配与此传递合并。
编辑
我对相对性能很好奇，所以我编写了一个程序来比较“库”C 排序函数 qsort、mergesort、heapsort，并将排序与 idx 和复制到 idx 进行比较。它还对排序后的值进行重新排序，以对此进行处理。这也很有趣。我没有实现和测试 Shell 排序，它在实践中经常胜过 qsort。
该程序使用命令行参数来选择哪种排序方式，以及是按 idx 排序，还是仅复制。代码：http : //pastebin.com/Ckc4ixNp
运行时的抖动非常明显。我应该使用 CPU 时钟，进行多次运行，并提供更好的结果，但这是“读者练习”。
我在一台老式 MacBook Pro 2.2GHz Intel Core 2 Duo 上运行它。某些时间是 OS C 特定的。
时间（稍微重新格式化）：
qsort(data, number-of-elements=40000000, element-size=12)
Sorting by val - duration = 16.304194
Re-order to idx by copying - duration = 2.904821
Sort in-order data - duration = 2.013237
Total duration = 21.222251
User Time: 20.754574
System Time: 0.402959
mergesort(data, number-of-elements=40000000, element-size=12)
Sorting by val - duration = 25.948651
Re-order to idx by copying - duration = 2.907766
Sort in-order data - duration = 0.593022
Total duration = 29.449438
User Time: 28.428954
System Time: 0.973349
heapsort(data, number-of-elements=40000000, element-size=12)
Sorting by val - duration = 72.236463
Re-order to idx by copying - duration = 2.899309
Sort in-order data - duration = 28.619173
Total duration = 103.754945
User Time: 103.107129
System Time: 0.564034
警告：这些是单次运行。需要多次运行才能获得合理的统计数据。
pastebin 中的代码实际上对“减少大小”的 8 字节数组进行了排序。在第一遍时，只需要 val 和 idx，并且当添加 val2 时数组被复制，因此第一个数组中不需要 val2。这种优化会导致排序函数复制一个较小的结构体，并在缓存中放入更多的结构体，这是很好的。我很失望这让 qsort 有了几个百分点的改进。我将此解释为 qsort 快速将块排序为适合缓存的大小。
相同的缩减大小策略使堆排序提高了 25% 以上。
8 字节结构的时间，没有 val2：
qsort(data, number-of-elements=40000000, element-size=8)
Sorting by val - duration = 16.087761
Re-order to idx by copying - duration = 2.858881
Sort in-order data - duration = 1.888554
Total duration = 20.835196
User Time: 20.417285
System Time: 0.402756
mergesort(data, number-of-elements=40000000, element-size=8)
Sorting by val - duration = 22.590726
Re-order to idx by copying - duration = 2.860935
Sort in-order data - duration = 0.577589
Total duration = 26.029249
User Time: 25.234369
System Time: 0.779115
heapsort(data, number-of-elements=40000000, element-size=8)
Sorting by val - duration = 52.835870
Re-order to idx by copying - duration = 2.858543
Sort in-order data - duration = 24.660178
Total duration = 80.354592
User Time: 79.696220
System Time: 0.549068
警告：这些是单次运行。需要多次运行才能获得合理的统计数据。