快速排序算法(QSort,快排)及C语言实现

上节介绍了如何使用起泡排序的思想对无序表中的记录按照一定的规则进行排序,本节再介绍一种排序算法——快速排序算法(Quick Sort)。

C语言中自带函数库中就有快速排序——qsort函数 ,包含在 <stdlib.h> 头文件中。

快速排序算法是在起泡排序的基础上进行改进的一种算法,其实现的基本思想是:通过一次排序将整个无序表分成相互独立的两部分,其中一部分中的数据都比另一部分中包含的数据的值小,然后继续沿用此方法分别对两部分进行同样的操作,直到每一个小部分不可再分,所得到的整个序列就成为了有序序列。

例如,对无序表{49,38,65,97,76,13,27,49}进行快速排序,大致过程为:

  1. 首先从表中选取一个记录的关键字作为分割点(称为“枢轴”或者支点,一般选择第一个关键字),例如选取 49;
  2. 将表格中大于 49 个放置于 49 的右侧,小于 49 的放置于 49 的左侧,假设完成后的无序表为:{27,38,13,49,65,97,76,49}
  3. 以 49 为支点,将整个无序表分割成了两个部分,分别为{27,38,13}{65,97,76,49},继续采用此种方法分别对两个子表进行排序;
  4. 前部分子表以 27 为支点,排序后的子表为{13,27,38},此部分已经有序;后部分子表以 65 为支点,排序后的子表为{49,65,97,76}
  5. 此时前半部分子表中的数据已完成排序;后部分子表继续以 65为支点,将其分割为{49}{97,76},前者不需排序,后者排序后的结果为{76,97}
  6. 通过以上几步的排序,最后由子表{13,27,38}{49}{49}{65}{76,97}构成有序表:{13,27,38,49,49,65,76,97}

整个过程中最重要的是实现第 2 步的分割操作,具体实现过程为:

  • 设置两个指针 low 和 high,分别指向无序表的表头和表尾,如下所示:
  • 先由 high 指针从右往左依次遍历,直到找到一个比 49 小的关键字,所以 high 指针走到 27 的地方停止。找到之后将该关键字同 low 指向的关键字进行互换:
  • 然后指针 low 从左往右依次遍历,直到找到一个比 49 大的关键字为止,所以 low 指针走到 65 的地方停止。同样找到后同 high 指向的关键字进行互换:
  • 指针 high 继续左移,到 13 所在的位置停止(13<49),然后同 low 指向的关键字进行互换:
  • 指针 low 继续右移,到 97 所在的位置停止(97>49),然后同 high 指向的关键字互换位置:
  • 指针 high 继续左移,此时两指针相遇,整个过程结束;

该操作过程的具体实现代码为:

该方法其实还有可以改进的地方:在上边实现分割的过程中,每次交换都将支点记录的值进行移动,而实际上只需在整个过程结束后(low==high),两指针指向的位置就是支点记录的准确位置,所以无需每次都移动支点的位置,最后移动至正确的位置即可。

所以上边的算法还可以改写为:

快速排序的完整实现代码(C语言)

运行结果:

总结

快速排序算法的时间复杂度为O(nlogn),是所有时间复杂度相同的排序方法中性能最好的排序算法。

参考链接


macOS Mojave(10.14.5) Octave libSVM加速SVM计算


安装完成后,库提供了 svmtrain , svmpredict, libsvmwrite, libsvmread  等函数,可以加速整个 SVM的处理速度。

Octave 中使用的方式如下:

参考链接


乘积累加运算(Multiply Accumulate, MAC)

乘积累加运算英语:Multiply Accumulate, MAC)是在数字信号处理器或一些微处理器中的特殊运算。实现此运算操作的硬件电路单元,被称为“乘数累加器”。这种运算的操作,是将乘法的乘积结果和累加器 A 的值相加,再存入累加器:

若没有使用 MAC 指令,上述的程序可能需要二个指令,但 MAC 指令可以使用一个指令完成。而许多运算(例如卷积运算、点积运算、矩阵运算、数字滤波器运算、乃至多项式的求值运算)都可以分解为数个 MAC 指令,因此可以提高上述运算的效率。

MAC指令的输入及输出的数据类型可以是整数定点数或是浮点数。若处理浮点数时,会有两次的数值修约(Rounding),这在很多典型的DSP上很常见。若一条MAC指令在处理浮点数时只有一次的数值修约,则这种指令称为“融合乘加运算”/“积和熔加运算”(fused multiply-add, FMA)或“熔合乘法累积运算”(fused multiply–accumulate, FMAC)。

积和熔加运算

融合乘加运算的操作和乘积累加的基本一样,对于浮点数的操作也是一条指令完成。但不同的是,非融合乘加的乘积累加运算,处理浮点数时,会先完成b×c的乘积,将其结果数值修约到N个比特,然后才将修约后的结果与寄存器a的数值相加,再把结果修约到N个比特;融合乘加则是先完成a+b×c的操作,获得最终的完整结果后方才修约到N个比特。由于减少了数值修约次数,这种操作可以提高运算结果的精度,以及提高运算效率和速率。

积和融加运算可以显著提升像是这些运算的性能和精度:

积和融加运算通常被依靠用来获取更精确的运算结果。然而,Kahan指出,如果不加思索地使用这种运算操作,在某些情况下可能会带来问题。[1]像是平方差公式x2y2,它等价于 ((x×x) − y×y),若果x与y已知数值,使用积和融加运算来求结果,哪怕x = y时,因为在进行首次乘法操作时无视低位的有效比特,可能会使运算结果出错,如果是多步运算,第一步就出错则会连累后续的运算结果接连出错,比如前述的平方差求值后,再取结果的平方根,那么这个结果也会出错。

参考链接

Simple ARM NEON optimized sin, cos, log and exp

This is the sequel of the single precision SSE optimized sin, cos, log and exp that I wrote some time ago. Adapted to the NEON fpu of my pandaboard. Precision and range are exactly the same than the SSE version, so I won't repeat them.

The code

The functions below are licensed under the zlib license, so you can do basically what you want with them.

  • neon_mathfun.h source code for sin_ps, cos_ps, sincos_ps, exp_ps, log_ps, as straight C.
  • neon_mathfun_test.c Validation+Bench program for those function. Do not forget to run it once.

Performance

Results on a pandaboard with a 1GHz dual-core ARM Cortex A9 (OMAP4), using gcc 4.6.1

command line: gcc -O3 -mfloat-abi=softfp -mfpu=neon -march=armv7-a -mtune=cortex-a9 -Wall -W neon_mathfun_test.c -lm

So performance is not stellar. I recommend to use gcc 4.6.1 or newer as it generates much better code than previous (gcc 4.5) versions -- almost 20% faster here. I believe rewriting these functions in assembly would improve the performance by 30%, and should not be very hard as the ARM and NEON asm is quite nice and easy to write -- maybe I'll do it. Computing two SIMD vectors at once would also help to improve a lot the performance as there are enough registers on NEON, and it would reduce the dependancies between neon instructions.

Note also that I have no idea of the performance on a Cortex A8 -- it may be extremely bad, I don't know.

Comparison with an Intel Atom

For comparison purposes, here is the performance of the SSE version on a single core Intel Atom N270 running at 1.66GHz

command line: cl.exe /arch:SSE /O2 /TP /MD sse_mathfun_test.c (this is msvc 2010)

The number of cycles is quite similar -- but the atom has a higher clock..

Last modified: 2011/05/29

参考链接


Simple ARM NEON optimized sin, cos, log and exp

TI Designs:TIDA-01469 采用无线振动传感器并支持预防性维护的电机监控参考设计

采用无线振动传感器并支持预防性维护的电机监控参考设计
继续阅读TI Designs:TIDA-01469 采用无线振动传感器并支持预防性维护的电机监控参考设计