为什么我的quicksort在python中这么慢?
发布时间:2020-12-20 11:43:15 所属栏目:Python 来源:网络整理
导读:我试着在 python中编写一个quicksort(用于学习算法),但我发现它比本机排序慢了10倍.这是结果: 16384 numbers:native: 5.556 msquicksort: 96.412 ms65536 numbers:native: 27.190 msquicksort: 436.110 ms262144 numbers:native: 151.820 msquicksort: 1975
我试着在
python中编写一个quicksort(用于学习算法),但我发现它比本机排序慢了10倍.这是结果:
16384 numbers: native: 5.556 ms quicksort: 96.412 ms 65536 numbers: native: 27.190 ms quicksort: 436.110 ms 262144 numbers: native: 151.820 ms quicksort: 1975.943 ms 1048576 numbers: native: 792.091 ms quicksort: 9097.085 ms 4194304 numbers: native: 3979.032 ms quicksort: 39106.887 ms 这是否意味着我的实施有问题? 尽管如此,我认为将100万个数字分类为近10个是不可接受的,尽管我只是为了学习而不是实际应用而编写它.我的电脑很快. def quicksort(lst): quicksortinner(lst,len(lst)-1) def quicksortinner(lst,start,end): if start>=end: return j=partition(lst,end) quicksortinner(lst,j-1) quicksortinner(lst,j+1,end) def partition(lst,end): pivotindex=random.randrange(start,end+1) swap(lst,pivotindex,end) pivot=lst[end] i,j=start,end-1 while True: while lst[i]<=pivot and i<=end-1: i+=1 while lst[j]>=pivot and j>=start: j-=1 if i>=j: break swap(lst,i,j) swap(lst,end) return i def swap(lst,a,b): if a==b: return lst[a],lst[b]=lst[b],lst[a] 在分区中,我向右扫描并向左扫描j(来自算法的方法).早些时候我试过了两个向右移动的方式(可能更常见),并没有太大区别. 解决方法
本机排序用C语言编写.您的快速排序是用纯Python编写的.预计速度差为10倍.如果使用
PyPy运行代码,则应该更接近本机速度(PyPy使用跟踪JIT来实现高性能).同样,Cython也会提供很好的速度提升(Cython是一个Python-to-C编译器).
判断算法是否在同一个球场中的一种方法是计算两种排序算法使用的比较次数.在精细调整的代码中,比较成本主导了运行时间.这是一个计算比较的工具: class CountCmps(float): def __lt__(self,other): global cnt cnt += 1 return float.__lt__(self,other) >>> from random import random >>> data = [CountCmps(random()) for i in range(10000)] >>> cnt = 0 >>> data.sort() >>> cnt 119883 另一个因素是你对random.randrange()的调用有许多纯Python步骤,并且比你想象的做更多的工作.它将是总运行时间的一个非常重要的组成部分.由于随机枢轴选择可能很慢,请考虑使用median-of-three技术选择枢轴. 此外,在CPython中调用swap()函数的速度并不快.内联代码应该可以提高速度. 如您所见,优化Python还有很多,而不仅仅是选择一个好的算法.希望这个答案能让你进一步实现目标:-) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |