當前位置:成語大全網 - 新華字典 - 為什麽python內置的sort比自己寫的快速排序快100倍?

為什麽python內置的sort比自己寫的快速排序快100倍?

主要原因,內置函數用C寫的。在Python語言內無論如何造不出內置函數的輪子。這也是通常C跟C++語言用戶更喜歡造基礎算法的輪了的原因。因為C/C++用戶真有條件寫出匹敵標準庫的算法,但很多高級語言不行,不是程序員技術差,是客觀條件就根本做不到。

妳比如說Java語言沒人造字符串的輪子,C++光壹個字符串類就有無數多的實現。是因為C+用戶更喜歡寫字符串類嗎?顯然不是,壹方面是因為Java語言內沒法造出匹敵Java內置標準庫算法的輪子,而C++真的可以,另外壹個比較慘的原因是C++標準庫的字符串功能太弱了,大多數高級語言的字符串類功能都比C+標準庫字符串類功能更強。

寫C++的時候壹大錯覺就是我覺著我能比標準庫還快,同樣的道理放在Python裏面也同樣適用,不管是Python各種常用package或內建函數,基本上都針對實用場景作了優化,自己手寫的算法壹般是比不上內建算法效率的,這也是為什麽用Python時不鼓勵自己造輪子的原因。

回到這個問題,Python內建的sort本質上為C實現的函數,本身執行效率就會比Python快很多,並且會根據不同的數據規模采用不同的排序算法,故效率壹般都會優於自己在Python裏面手寫的排序更何況題主寫的是基於遞歸的quicksort9,額外時間開銷大。

因為python內置的sort是用c語言寫的,如果妳用c語言或者c++寫的話肯定是可以做到壹樣快的至於為什麽python計算效率比c語言能慢100倍這個具體的原理我不清楚,不過鑒於知乎上已經有很多大佬解釋過這個問題,我就不在這裏班門弄斧了

還有底下扯timsort的,快排序是所有比較排序算法裏平均性能最優的壹族算法,像C++和rust裏的unstable_sort都是用的快排序。可能在壹些情況下,比如數組幾乎有序時,timsort會比快排序快。但是妳隨便給壹個數組,比如像題主那樣隨機壹個壹百萬大小的數然後排序,timsort是絕對不可能比快排序快的。絕對不可能。快的這100倍和timsort屁關系都沒有。

我是C/C++程序員,我可以很負責的告訴妳,在用天下現有所有高級語言進行排序的問題上,C要是認了第二,則沒人敢認第壹。所以,我猜,Python以及好多其他高級語言,都會時不時直接上C語言寫的靜態庫和動態庫。我自己也造了不少輪子,有部分是因為剛剛起步,對系統API和函數庫不熟悉,找不到適合的,所以自己造輪子,後來發現了有更好的,我把我寫的拋棄了。但這裏也不排除有壹部分是因為我個人覺得還有優化的空間,所以自己用C語言重新造了壹個輪子,這樣效率比現成的更優。

所以說,要論高級語言的鼻祖,還真非C莫屬,從執行效率上講,別說python,JAVA,C#,VB,甚至C的親兒子C++,在同壹個程序員手中,都沒法與C抗衡,所以說,這些語言都是排著隊等著被C吊打的,也正因為如此,所以,像python這類高級語言,有自帶函數可用的,最好別想著自己重新造輪子,因為妳不可能造出比自帶函數更快的輪子。

內置庫函數都是用C實現的,肯定要比手寫的Python程序執行效率更高,此外內置排序Timsort相比本科課程上學的時間復雜度為Onlogn的排序算法做了很多常數優化,所以對於普通人而言,不要希望純手寫出來的東西效率能和標準庫相當了。另外,題主寫的排序是過不了LeetCode上的裸排序題目的,隨機選取pivot對於快速排序是最基本的優化雖然題主排的是隨機數,現在這麽選肯定不是效率低的主要原因。

所以說了,py幾乎得把自己的循環體拆了,這就是py和c/c++的性能差距,必須盡量用內置函數和numpy來處理數據,壹旦手寫循環體。,那妳就得知道這可能得慢百倍,像用opency的py版時妳不小心寫個雙循環來處理數據,那酸爽,而cppc#搞opencv就能隨意用指針來寫循環,這也是為啥他們其實不需要numpy這種組件,自身就有足夠的性能和靈活度來處理這個。

Cpp內置的排序是快排和堆排的結合,最壞時間復雜度為nlogn,而快排最壞是n2。至於python內部的排序,我認為是壹個道理,不會簡簡單單是壹個快排,舉個簡單例子,當妳數據已經是有序的時候,再傳入快排肯定就不合適。那妳設置排序函數的時候,是不是預先將他打亂,再進行快排會更好呢。當然具體不會這麽簡單,只是我認為官方給的接口都是很精妙的,很值得學習。

壹方面Python中sort函數是用C語言寫的,C++內部的sort是由快排,直接插入和堆排序混合的,當數據量比較大的時候先用的快排,當數據量小的時候用直接插入,因為當數據量變小時,快排中的每個部分基本有序,接近直接插入的最好情況的時間復雜度O(n),就比快排要好壹點了。

另外壹方面這個的底層實現就是歸並排序。,只是使用了Python無法編寫的底層實現,從而避免了Python本身附加的大量開銷,速度比我們自己寫的歸並排序要快很多,所以說我們壹般排序都盡量使用sorted和sort。