相关疑难解决方法(0)

回答另一个Stack Overflow问题(这个)我偶然发现了一个有趣的子问题.排序6个整数数组的最快方法是什么？

由于问题是非常低的水平:

• 我们不能假设库可用(并且调用本身有它的成本),只有普通的C.
• 避免排空指令流水线(具有非常高的成本),我们也许应该尽量减少分支机构,跳跃,和所有其他类型的控制流断裂的(像那些隐藏在背后的序列点&&或||).
• 房间受限制,最小化寄存器和内存使用是一个问题,理想情况下,排序可能是最好的.

真的这个问题是一种高尔夫,其目标不是最小化源长度而是执行时间.我把它叫做"Zening"代码在本书的标题中的代码优化禅由迈克尔·亚伯拉什及其续集.

至于为什么它很有趣,有几个层次:

• 这个例子很简单,易于理解和衡量,并没有太多的C技能
• 它显示了为问题选择好算法的效果,以及编译器和底层硬件的效果.

这是我的参考(天真的,未优化的)实现和我的测试集.

#include <stdio.h>

static __inline__ int sort6(int * d){

    char j, i, imin;
    int tmp;
    for (j = 0 ; j < 5 ; j++){
        imin = j;
        for (i = j + 1; i < 6 ; i++){
            if (d[i] < d[imin]){
                imin = i;
            }
        }
        tmp = d[j];
        d[j] = d[imin];
        d[imin] = …

上周我偶然发现了这篇论文,作者在第二页提到:

请注意,这会产生整数边权重的线性运行时间.

第三页上的内容相同:

这产生整数边缘权重的线性运行时间和基于比较的排序的O(m log n).

在第8页:

特别是,使用快速整数排序可能会显着加速GPA.

这是否意味着在特殊情况下存在整数值的O(n)排序算法？或者这是图论的专长？

PS:
可能参考文献[3]可能会有所帮助,因为在第一页上他们说:

[...]图表类已经实现了进一步的改进,例如整数边权重[3],[...]

但是我无法访问任何科学期刊.

我需要优化一些代码来排序a vector<pair<int, float >>需要在float值上排序的位置.该向量的长度介于0和5之间.我一直在谷歌搜索并阅读C++中的排序方法,但无法找到有关排序微小数据集的任何基准.对于系统来说,重要的是尽可能快,因为它用于实时blob跟踪系统.

亲切的问候,Pollux