#include <iostream>
#include <algorithm>
#include <random>
//return the index of the minimum element in array a
int min(const int * const a) {
int m = a[0];
int indx = 0;
#define TEST(i) (m > a[i]) && (m = a[i], indx = i );
//see http://stackoverflow.com/a/7074042/2140449
TEST(1);
TEST(2);
TEST(3);
TEST(4);
TEST(5);
TEST(6);
TEST(7);
TEST(8);
TEST(9);
#undef TEST
return indx;
}
void sort( int * const a ){
int work[10];
int indx;
#define GET(i) indx = min(a); work[i] = a[indx]; a[indx] = 2147483647;
//get the minimum, copy it to work and set it at max_int in a
GET(0);
GET(1);
GET(2);
GET(3);
GET(4);
GET(5);
GET(6);
GET(7);
GET(8);
GET(9);
#undef GET
#define COPY(i) a[i] = work[i];
//copy back to a
COPY(0);
COPY(1);
COPY(2);
COPY(3);
COPY(4);
COPY(5);
COPY(6);
COPY(7);
COPY(8);
COPY(9);
#undef COPY
}
int main() {
//generating and printing a random array
int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
std::random_device rd;
std::mt19937 g(rd());
std::shuffle( a, a+10, g);
for (int i = 0; i < 10; i++) {
std::cout << a[i] << ' ';
}
std::cout << std::endl;
//sorting and printing again
sort(a);
for (int i = 0; i < 10; i++) {
std::cout << a[i] << ' ';
}
return 0;
}
作为一名软件和硬件工程师,这对我来说绝对是尖叫 . 我不知道你需要从排序的数字集中得出什么样的结论或数据的来源,但我知道在"sort-and-analyze"这些"sort-and-analyze"之间的某个地方进行处理几乎是微不足道的 . 当问题非常适合这种类型的解决方案时,我就是've done FPGA-assisted DNA sequencing work in the past. It is nearly impossible to beat the massive processing power of FPGA' .
请注意,要排序 int x[10] ,调用是 insert_sort<int, 9>::sort(x); ,因为该类使用最后一项的索引 . 这可以包装,但这将是更多的代码来阅读 .
template <class T, int NUM>
class insert_sort;
template <class T>
class insert_sort<T,0>
// stop template recursion
// sorting 1 item is a no-op
{
public:
static void place(T *x) {}
static void sort(T * x) {}
};
template <class T, int NUM>
class insert_sort
// use template recursion to do insertion sort
// NUM is the index of the last item, eg. for x[10] call <9>
{
public:
static void place(T *x)
{
T t1=x[NUM-1];
T t2=x[NUM];
if (t1 > t2)
{
x[NUM-1]=t2;
x[NUM]=t1;
insert_sort<T,NUM-1>::place(x);
}
}
static void sort(T * x)
{
insert_sort<T,NUM-1>::sort(x); // sort everything before
place(x); // put this item in
}
};
{
final int a=in[0]<in[1]?in[0]:in[1];
final int b=in[0]<in[1]?in[1]:in[0];
in[0]=a;
in[1]=b;
}
for(int x=2;x<10;x+=2)
{
final int a=in[x]<in[x+1]?in[x]:in[x+1];
final int b=in[x]<in[x+1]?in[x+1]:in[x];
int y= x-1;
while(y>=0&&in[y]>b)
{
in[y+2]= in[y];
--y;
}
in[y+2]=b;
while(y>=0&&in[y]>a)
{
in[y+1]= in[y];
--y;
}
in[y+1]=a;
}
10 回答
插入排序平均需要29,6个比较来排序10个输入,最佳情况为9,最差情况为45(给定输入的顺序相反) .
{9,6,1}炮弹将平均需要25.5个比较来排序10个输入 . 最好的情况是14次比较,最差的是34次,并且对反向输入进行排序需要22次 .
因此,使用shellsort而不是插入排序可以将平均情况减少14% . 尽管最佳情况增加了56%,但最坏情况下减少了24%,这对于保持最坏情况性能得到控制的应用非常重要 . 相反的情况减少了51% .
由于您似乎熟悉插入排序,因此您可以将算法实现为{9,6}的排序网络,然后在插入排序({1})之后执行:
由于类似于我描述here的原因,以下排序函数
sort6_iterator()
和sort10_iterator_local()
应该运行良好,其中排序网络取自here:为了调用这个函数,我传递了一个
std::vector
迭代器 .(跟进HelloWorld的建议,研究排序网络 . )
似乎29比较/交换网络是进行10输入排序的最快方法 . 我使用了Waksman在1969年发现的网络,用于Javascript中的这个例子,它应该直接转换为C,因为它只是
if
语句,比较和交换的列表 .这是网络的图形表示,分为独立的阶段 .
为了利用并行处理,可以将5-4-3-4-4-4-3-2分组改为4-4-4-4-4-4-3-2分组 .
使用具有4个组比较的排序网络,因此您可以在SIMD寄存器中执行此操作 . 一对压缩的最小/最大指令实现了压缩比较器功能 . 抱歉,我现在没有时间寻找一个我记得看过这个页面的页面,但希望在SIMD或SSE排序网络上搜索会有所改变 .
对于四个32位整数的向量,x86 SSE确实具有打包的32位整数最小和最大指令 . AVX2(Haswell和更高版本)具有相同的但是对于具有8个整数的256b向量 . 还有有效的随机指示 .
如果你有很多独立的小分类,可能可以使用向量并行进行4或8种分类 . ESP . 如果你随机选择元素(所以要分类的数据无论如何都不会在内存中连续),你可以避免随机播放,只需按照你需要的顺序进行比较 . 10个寄存器用于保存4个(AVX2:8)10个整数列表中的所有数据,但仍有6个reg用于暂存空间 .
如果您还需要对关联数据进行排序,则向量排序网络效率较低 . 在这种情况下,最有效的方法似乎是使用packed-compare来获取哪些元素已更改的掩码,并使用该掩码来混合(引用)关联数据的向量 .
那么展开的无分支选择排序怎么样?
http://coliru.stacked-crooked.com/a/71e18bc4f7fa18c6
唯一相关的行是前两个
#define
.它使用两个列表并完全重新检查第一个十次,这将是一个糟糕实现的选择排序,但它避免了分支和可变长度循环,这可以补偿现代处理器和如此小的数据集 .
基准
我对排序网络进行了基准测试,我的代码似乎更慢 . 但是我试图删除展开和副本 . 运行此代码:
与分拣网络相比,我一直得到 better result for the branch-less selection sort .
问题并不是说这是某种基于Web的应用程序 . 引起我注意的一件事是:
作为一名软件和硬件工程师,这对我来说绝对是尖叫 . 我不知道你需要从排序的数字集中得出什么样的结论或数据的来源,但我知道在"sort-and-analyze"这些"sort-and-analyze"之间的某个地方进行处理几乎是微不足道的 . 当问题非常适合这种类型的解决方案时,我就是've done FPGA-assisted DNA sequencing work in the past. It is nearly impossible to beat the massive processing power of FPGA' .
在某种程度上,唯一的限制因素是您可以多快地将数据转换为FPGA以及如何将数据转换为FPGA很快你就可以把它拿出来 .
作为参考,我设计了一个高性能的实时图像处理器,以每秒约3亿像素的速率接收32位RGB图像数据 . 在从另一端出来之前,数据通过FIR滤波器,矩阵乘法器,查找表,空间边缘检测块和许多其他操作流式传输 . 所有这一切都在一个相对较小的Xilinx Virtex2 FPGA上,内部时钟频率从大约33MHz到如果我没记错,400MHz . 哦,是的,它还有一个DDR2控制器实现并运行了两组DDR2内存 .
FPGA可以在每个时钟转换时输出一个10位32位数,同时工作在数百MHz . 当数据填满处理管道时,操作开始时会有短暂的延迟 . 之后,您应该能够每个时钟获得一个结果 . 或者更多,如果可以通过复制排序和分析管道来并行化处理 . 原则上,解决方案几乎是微不足道的 .
重点是:如果应用程序不受PC限制,并且数据流和处理与FPGA解决方案“兼容”(独立或作为机器中的协处理器卡),那么您无法继续使用无论算法如何,用任何语言编写的软件都能够达到可达到的性能水平 .
EDIT:
只是快速搜索并找到了一篇可能对你有用的论文 . 看起来它可以追溯到2012年 . 今天你可以做得更好(甚至当时) . 这里是:
Sorting Networks on FPGAs
我最近写了一个little class,它使用Bose-Nelson算法在编译时生成一个排序网络 .
它可用于为10个数字创建非常快速的排序 .
请注意,我们为min和max明确编写了三元运算符,而不是
if (compare) swap
语句 . 这有助于推动编译器使用无分支代码 .基准
下面的基准测试用clang -O3编译,并在我2012年中期的macbook air上运行 .
对随机数据进行排序
将它与DarioP的代码进行比较,下面是对100万个大小为10的32位int数组进行排序所需的毫秒数:
Hardcoded Sort Net 10 : 88.774 ms
Templated Bose-Nelson sort 10 : 27.815毫秒
使用这种模板化方法,我们还可以在编译时为其他数量的元素生成排序网络 .
分类100万个不同大小的数组的时间(以毫秒为单位) .
大小为2,4,8的数组的毫秒数分别为1.943,8.655,20.246 .
对于展开的插入排序,Glenn Teitelbaum的积分 .
以下是6个元素的小数组的每种平均时钟数 . 可以在此问题中找到基准代码和示例:
Fastest sort of fixed length 6 int array
它的性能与6个元素的问题中最快的例子一样快 .
用于排序已排序数据的性能
通常,输入数组可能已经排序或大部分排序 .
在这种情况下,插入排序可能是更好的选择 .
您可能希望根据数据选择合适的排序算法 .
用于基准测试的代码可以在here找到 .
你可以完全展开
insertion sort
为了使这更容易,递归
template
可以使用没有函数开销 . 由于它已经是template
,int
也可以是template
参数 . 这也使得编码阵列大小不是十分微不足道的 .请注意,要排序
int x[10]
,调用是insert_sort<int, 9>::sort(x);
,因为该类使用最后一项的索引 . 这可以包装,但这将是更多的代码来阅读 .在我的测试中,这比排序网络示例更快 .
处理此固定大小时,请查看Sorting Networks . 这些算法具有固定的运行时,并且与其输入无关 . 对于您的用例,您没有某些排序算法所具有的开销 .
Bitonic sort是此类网络的实现 . 这个最适合在CPU上使用len(n)<= 32 . 在更大的输入上,您可以考虑转向GPU . https://en.wikipedia.org/wiki/Sorting_network
顺便说一句,这是一个比较排序算法的好页面(尽管它缺少
bitonic sort
.http://www.sorting-algorithms.com
尽管网络排序在小型阵列上具有很快的快速成功率,但如果经过适当优化,有时您无法击败插入排序 . 例如,具有2个元素的批量插入: