使用php构建quicksort

我最近阅读了关于quicksort的内容,并且想知道构建我自己的函数以使用quicksort对事物进行排序是否是明智的,或者它是否是无效的.您认为内置排序功能比自建快速排序功能更好吗？

来自http://php.net/sort

注意:与大多数PHP排序函数一样,sort()使用»Quicksort的实现.

核心PHP函数将在c而不是PHP中实现,因此它们通常应该比您在PHP中自己编写的任何内容快得多.在某些情况下,编写自己的编写速度会更快,但我想这些情况会在您有一个非常具体的案例时进行,并且您可以对此进行自己的特定优化.我认为这不太可能是这种情况.

事实上,我这样做是为了我正在整理的演示文稿中的数据点.该测试使用本机排序函数和用PHP编写的快速排序算法的实现对250,000个整数的数组进行排序.对于两次运行,数组的内容完全相同,数据是随机的,报告的时间仅用于执行排序,而不是调用php解释器所需的其他处理.

结果:

  Native sort implementation:  1.379 seconds
PHP quicksort implementation: 30.615 seconds

绝对使用本机实现.这应该是任何解释语言的情况.

我使用相同的条件在同一硬件和操作系统上使用相同的实现测试的其他语言的结果提供了有趣的性能比较,并将PHP结果放在透视图中:

               C: 0.107 seconds
            Java: 0.250 seconds
JavaScript (FF3): 4.401 seconds

值得注意的是,Chrome和Safari 在JavaScript测试中的执行速度要快得多,但我不在此处包含这些测试,因为这些测试是在不同的环境中录制的.

坚持使用内置排序功能.Quicksort是一种简单的算法,但要在实际使用的计算机上获得良好的性能需要一点点技巧.内置函数很可能已经比在合理的时间内编写的任何内容更优化.(用C而不是PHP编写的恒定因子加速也可能有用.)

如果你正在排序那么多的元素,你被sort函数放慢了速度,你可能会做错事.(毕竟这是PHP.您应该使用通用语言进行数据密集型处理.编写代码会更容易,而且运行速度会更快.)