Morn：C语言解决topN问题

Morn是一个C语言的基础工具和基础算法库，包括数据结构、图像处理、音频处理、机器学习等，具有简单、通用、高效的特点。
https://github.com/jingweizhanghuai/Morn

大量的数据，怎么从中找出最大（或最小）的N个数，是最常见的算法问题之一。把所有的数据排序，然后取出前N个，这当然是一种解决方案，但是不是最好的方案。Morn的方案是这样的：

接口

本文的相关函数的源码在：
https://github.com/jingweizhanghuai/Morn/blob/master/src/math/morn_sort.c

最小值子集

也就是从num_in个数据里，取出num_out个最小的数，取出的数并无必要按照大小顺序排列。

D64 mMinSubsetD64(D64 *data_in,int *index_in,int num_in,D64 *data_out,int *index_out,int num_out);
F32 mMinSubsetF32(F32 *data_in,int *index_in,int num_in,F32 *data_out,int *index_out,int num_out);
S32 mMinSubsetS32(S32 *data_in,int *index_in,int num_in,S32 *data_out,int *index_out,int num_out);
U32 mMinSubsetU32(U32 *data_in,int *index_in,int num_in,U32 *data_out,int *index_out,int num_out);
S16 mMinSubsetS16(S16 *data_in,int *index_in,int num_in,S16 *data_out,int *index_out,int num_out);
U16 mMinSubsetU16(U16 *data_in,int *index_in,int num_in,U16 *data_out,int *index_out,int num_out);
 S8 mMinSubsetS8 ( S8 *data_in,int *index_in,int num_in, S8 *data_out,int *index_out,int num_out);
 U8 mMinSubsetU8 ( U8 *data_in,int *index_in,int num_in, U8 *data_out,int *index_out,int num_out);

或者，可以用：

Type mMinSubset(Type，Type *data_in,int *index_in,int num_in, Type *data_out,int *index_out,int num_out);

其参数Type、data_in、data_out、index_in、index_out与mAscSort相同，不再赘述。

num_in即输入数据的个数。num_out即输出数据的个数。

返回值是临界值，即输出数据中的最大值。

例如：

printf("\n\nin :");
for(int i=0;i<10;i++) {data[i] = mRand(-100,100);printf("%d,",data[i]);}
mMinSubset(S32,data,NULL,10,NULL,index,4);
printf( "\nout :");
for(int i=0;i<4;i++) {printf("%d(%d),",data[i],index[i]);}
    

其运行结果为

in :47,-56,-38,57,-63,-41,23,41,29,78,
out :-41(5),-56(1),-38(2),-63(4),

最大值子集

D64 mMaxSubsetD64(D64 *data_in,int *index_in,int num_in,D64 *data_out,int *index_out,int num_out);
F32 mMaxSubsetF32(F32 *data_in,int *index_in,int num_in,F32 *data_out,int *index_out,int num_out);
S32 mMaxSubsetS32(S32 *data_in,int *index_in,int num_in,S32 *data_out,int *index_out,int num_out);
U32 mMaxSubsetU32(U32 *data_in,int *index_in,int num_in,U32 *data_out,int *index_out,int num_out);
S16 mMaxSubsetS16(S16 *data_in,int *index_in,int num_in,S16 *data_out,int *index_out,int num_out);
U16 mMaxSubsetU16(U16 *data_in,int *index_in,int num_in,U16 *data_out,int *index_out,int num_out);
 S8 mMaxSubsetS8 ( S8 *data_in,int *index_in,int num_in, S8 *data_out,int *index_out,int num_out);
 U8 mMaxSubsetU8 ( U8 *data_in,int *index_in,int num_in, U8 *data_out,int *index_out,int num_out);

或者，可以用：

Type mMaxSubset(Type，Type *data_in,int *index_in,int num_in, Type *data_out,int *index_out,int num_out);

其参数与mMinSubset相同，不再赘述。

返回值是临界值，即输出数据中的最小值。

例如：

printf("\n\nin :");
for(int i=0;i<10;i++) {data[i] = mRand(-100,100);printf("%d,",data[i]);}
mMaxSubset(S32,data,NULL,10,NULL,NULL,4);
printf( "\nout :");
for(int i=0;i<4;i++) {printf("%d,",data[i]);}    

其运行结果为

in :16,-65,90,-58,-12,6,-60,42,-36,-52,
out :16,42,90,6,

性能

测试程序如下：

int *data=mMalloc(n*sizeof(int));
for(int i=0;i<n;i++) data[i] = mRand(0-n,n);
    
printf("S32 Morn subset(in %d, out %d):\n",n,m);
mTimerBegin();
mMinSubset(S32,data,NULL,n,NULL,NULL,m);
mTimerEnd();
    
mFree(data);

测试结果如下：

排序2.PNG

这里测试了32位整数和64位浮点数的性能，测试的数据输入都是1000000个，输出分别为100000个、300000个、500000个、700000个、900000个。

上一篇文章写了，关于Morn排序的性能，对于1000000个整数的排序，使用标准库qsort进行排序需要120ms，使用Morn排序需要70ms，对于1000000个双精度浮点数的排序，使用标准库qsort进行排序需要150ms，使用Morn排序需要80ms，

对比可以看到其运算用时，比1000000个数据排序要小一个数量级。

Morn：写C语言！快点！简单点！
https://github.com/jingweizhanghuai/Morn