python快排

Ⅰ 「干貨」讓python性能起飛的15個技巧，你知道幾個呢

前言

Python 一直以來被大家所詬病的一點就是執行速度慢，但不可否認的是 Python 依然是我們學習和工作中的一大利器。本文總結了15個tips有助於提升 Python 執行速度、優化性能。

關於 Python 如何精確地測量程序的執行時間，這個問題看起來簡單其實很復雜，因為程序的執行時間受到很多因素的影響，例如操作系統、Python 版本以及相關硬體（CPU 性能、內存讀寫速度）等。在同一台電腦上運行相同版本的語言時，上述因素就是確定的了，但是程序的睡眠時間依然是變化的，且電腦上正在運行的其他程序也會對實驗有干擾，因此嚴格來說這就是實驗不可重復。

我了解到的關於計時比較有代表性的兩個庫就是 time 和 timeit 。

其中， time 庫中有 time() 、 perf_counter() 以及 process_time() 三個函數可用來計時（以秒為單位），加後綴 _ns 表示以納秒計時（自 Python3.7 始）。在此之前還有 clock() 函數，但是在 Python3.3 之後被移除了。上述三者的區別如下：

與 time 庫相比， timeit 有兩個優點：

timeit.timeit(stmt='pass', setup='pass', timer= , number=1000000, globals=None) 參數說明：

本文所有的計時均採用 timeit 方法，且採用默認的執行次數一百萬次。

為什麼要執行一百萬次呢？因為我們的測試程序很短，如果不執行這么多次的話，根本看不出差距。

Exp1：將字元串數組中的小寫字母轉為大寫字母。

測試數組為 oldlist = ['life', 'is', 'short', 'i', 'choose', 'python']。

方法一

方法二

方法一耗時 0.5267724000000005s ，方法二耗時 0.41462569999999843s ，性能提升 21.29%

Exp2：求兩個 list 的交集。

測試數組：a = [1,2,3,4,5]，b = [2,4,6,8,10]。

方法一

方法二

方法一耗時 0.9507264000000006s ，方法二耗時 0.6148200999999993s ，性能提升 35.33%

關於 set() 的語法： | 、 & 、 - 分別表示求並集、交集、差集。

我們可以通過多種方式對序列進行排序，但其實自己編寫排序演算法的方法有些得不償失。因為內置的 sort() 或 sorted() 方法已經足夠優秀了，且利用參數 key 可以實現不同的功能，非常靈活。二者的區別是 sort() 方法僅被定義在 list 中，而 sorted() 是全局方法對所有的可迭代序列都有效。

Exp3：分別使用快排和 sort() 方法對同一列表排序。

測試數組：lists = [2,1,4,3,0]。

方法一

方法二

方法一耗時 2.4796975000000003s ，方法二耗時 0.05551999999999424s ，性能提升 97.76%

順帶一提， sorted() 方法耗時 0.1339823999987857s 。

可以看出， sort() 作為 list 專屬的排序方法還是很強的， sorted() 雖然比前者慢一點，但是勝在它「不挑食」，它對所有的可迭代序列都有效。

擴展 ：如何定義 sort() 或 sorted() 方法的 key

1.通過 lambda 定義

2.通過 operator 定義

operator 的 itemgetter() 適用於普通數組排序， attrgetter() 適用於對象數組排序

3.通過 cmp_to_key() 定義，最為靈活

Exp4：統計字元串中每個字元出現的次數。

測試數組：sentence='life is short, i choose python'。

方法一

方法二

方法一耗時 2.8105250000000055s ，方法二耗時 1.6317423000000062s ，性能提升 41.94%

列表推導（list comprehension）短小精悍。在小代碼片段中，可能沒有太大的區別。但是在大型開發中，它可以節省一些時間。

Exp5：對列表中的奇數求平方，偶數不變。

測試數組：oldlist = range(10)。

方法一

方法二

方法一耗時 1.5342976000000021s ，方法二耗時 1.4181957999999923s ，性能提升 7.57%

大多數人都習慣使用 + 來連接字元串。但其實，這種方法非常低效。因為， + 操作在每一步中都會創建一個新字元串並復制舊字元串。更好的方法是用 join() 來連接字元串。關於字元串的其他操作，也盡量使用內置函數，如 isalpha() 、 isdigit() 、 startswith() 、 endswith() 等。

Exp6：將字元串列表中的元素連接起來。

測試數組：oldlist = ['life', 'is', 'short', 'i', 'choose', 'python']。

方法一

方法二

方法一耗時 0.27489080000000854s ，方法二耗時 0.08166570000000206s ，性能提升 70.29%

join 還有一個非常舒服的點，就是它可以指定連接的分隔符，舉個例子

life//is//short//i//choose//python

Exp6：交換x，y的值。

測試數據：x, y = 100, 200。

方法一

方法二

方法一耗時 0.027853900000010867s ，方法二耗時 0.02398730000000171s ，性能提升 13.88%

在不知道確切的循環次數時，常規方法是使用 while True 進行無限循環，在代碼塊中判斷是否滿足循環終止條件。雖然這樣做沒有任何問題，但 while 1 的執行速度比 while True 更快。因為它是一種數值轉換，可以更快地生成輸出。

Exp8：分別用 while 1 和 while True 循環 100 次。

方法一

方法二

方法一耗時 3.679268300000004s ，方法二耗時 3.607847499999991s ，性能提升 1.94%

將文件存儲在高速緩存中有助於快速恢復功能。Python 支持裝飾器緩存，該緩存在內存中維護特定類型的緩存，以實現最佳軟體驅動速度。我們使用 lru_cache 裝飾器來為斐波那契函數提供緩存功能，在使用 fibonacci 遞歸函數時，存在大量的重復計算，例如 fibonacci(1) 、 fibonacci(2) 就運行了很多次。而在使用了 lru_cache 後，所有的重復計算只會執行一次，從而大大提高程序的執行效率。

Exp9：求斐波那契數列。

測試數據：fibonacci(7)。

方法一

方法二

方法一耗時 3.955014900000009s ，方法二耗時 0.05077979999998661s ，性能提升 98.72%

注意事項：

我被執行了（執行了兩次 demo(1, 2) ，卻只輸出一次）

functools.lru_cache(maxsize=128, typed=False) 的兩個可選參數：

點運算符( . )用來訪問對象的屬性或方法，這會引起程序使用 __getattribute__() 和 __getattr__() 進行字典查找，從而帶來不必要的開銷。尤其注意，在循環當中，更要減少點運算符的使用，應該將它移到循環外處理。

這啟發我們應該盡量使用 from ... import ... 這種方式來導包，而不是在需要使用某方法時通過點運算符來獲取。其實不光是點運算符，其他很多不必要的運算我們都盡量移到循環外處理。

Exp10：將字元串數組中的小寫字母轉為大寫字母。

測試數組為 oldlist = ['life', 'is', 'short', 'i', 'choose', 'python']。

方法一

方法二

方法一耗時 0.7235491999999795s ，方法二耗時 0.5475435999999831s ，性能提升 24.33%

當我們知道具體要循環多少次時，使用 for 循環比使用 while 循環更好。

Exp12：使用 for 和 while 分別循環 100 次。

方法一

方法二

方法一耗時 3.894683299999997s ，方法二耗時 1.0198077999999953s ，性能提升 73.82%

Numba 可以將 Python 函數編譯碼為機器碼執行，大大提高代碼執行速度，甚至可以接近 C 或 FORTRAN 的速度。它能和 Numpy 配合使用，在 for 循環中或存在大量計算時能顯著地提高執行效率。

Exp12：求從 1 加到 100 的和。

方法一

方法二

方法一耗時 3.7199997000000167s ，方法二耗時 0.23769430000001535s ，性能提升 93.61%

矢量化是 NumPy 中的一種強大功能，可以將操作表達為在整個數組上而不是在各個元素上發生。這種用數組表達式替換顯式循環的做法通常稱為矢量化。

在 Python 中循環數組或任何數據結構時，會涉及很多開銷。NumPy 中的向量化操作將內部循環委託給高度優化的 C 和 Fortran 函數，從而使 Python 代碼更加快速。

Exp13：兩個長度相同的序列逐元素相乘。

測試數組：a = [1,2,3,4,5], b = [2,4,6,8,10]

方法一

方法二

方法一耗時 0.6706845000000214s ，方法二耗時 0.3070132000000001s ，性能提升 54.22%

若要檢查列表中是否包含某成員，通常使用 in 關鍵字更快。

Exp14：檢查列表中是否包含某成員。

測試數組：lists = ['life', 'is', 'short', 'i', 'choose', 'python']

方法一

方法二

方法一耗時 0.16038449999999216s ，方法二耗時 0.04139250000000061s ，性能提升 74.19%

itertools 是用來操作迭代器的一個模塊，其函數主要可以分為三類：無限迭代器、有限迭代器、組合迭代器。

Exp15：返回列表的全排列。

測試數組：["Alice", "Bob", "Carol"]

方法一

方法二

方法一耗時 3.867292899999484s ，方法二耗時 0.3875405000007959s ，性能提升 89.98%

根據上面的測試數據，我繪制了下面這張實驗結果圖，可以更加直觀的看出不同方法帶來的性能差異。

從圖中可以看出，大部分的技巧所帶來的性能增幅還是比較可觀的，但也有少部分技巧的增幅較小（例如編號5、7、8，其中，第 8 條的兩種方法幾乎沒有差異）。

總結下來，我覺得其實就是下面這兩條原則：

內置庫函數由專業的開發人員編寫並經過了多次測試，很多庫函數的底層是用 C 語言開發的。因此，這些函數總體來說是非常高效的（比如 sort() 、 join() 等），自己編寫的方法很難超越它們，還不如省省功夫，不要重復造輪子了，何況你造的輪子可能更差。所以，如果函數庫中已經存在該函數，就直接拿來用。

有很多優秀的第三方庫，它們的底層可能是用 C 和 Fortran 來實現的，像這樣的庫用起來絕對不會吃虧，比如前文提到的 Numpy 和 Numba，它們帶來的提升都是非常驚人的。類似這樣的庫還有很多，比如Cython、PyPy等，這里我只是拋磚引玉。

原文鏈接：https://www.jb51.net/article/238190.htm

Ⅱ 最快的排序演算法是什麼

最快的排序演算法是什麼，很多人的第一反應是快排，感覺QuickSort 當然應該最快了，其實並非如此，坦歲快排是不穩定的，最壞情況下，快排序並不是最優，Java7 中引入的 TimSort 就是一個結合了插入排序和歸並排序的高效演算法.

Timsort最早是 Tim Peters 於2001年為 Python 寫的排序演算法。自從發明該演算法以來，它已被用作Python，Java，Android平台和GNU Octave中的默認排序演算法。

關於此演算法的詳細描述參見 http://svn.python.org/projects/python/trunk/Objects/listsort.txt

看看它與另外兩個高效排序演算法的比較

相比之下， TimSort 的最佳，平均和最壞情況綜合起來最佳。在數據量比較少（<=64）的情況下，它直接用 Insert Sort，否則使用 MergeSort + BinarySearch 來提高排序效率

下面寫一個給撲克牌排序的例子，比較一下冒泡，插入，快排，歸並排序，TimSort的性能:

然後分別用以上5種排序方法來做下性能比較

將1000 副牌打亂順序的撲克牌排序下來，結果如下

但是 TimSort 也有讓做睜一個問題， 在 JDK7 的描述中提到它有如下兼容性問題

所以在JDK7以後，實現Comparable介面的比較器需要滿足以下三個約束條件：
1） 自反性：x，y 的比較結果和 y，x 的比較結果胡團相反。
2） 傳遞性：x>y, y>z,則 x>z。
3） 對稱性：x=y,則 x,z 比較結果和 y，z 比較結果相同。

如果你的比較方法違反了以上的約束，要麼你不使用這個新的演算法，還是回到傳統的歸並排序

要麼修改你的比較器以符合上述的約束條件。

舉兩個例子如下

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

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

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

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

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

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

Ⅳ python後端開發需要學什麼

第一階段：Python語言基礎

主要學習Python最基礎知識，如Python3、數據類型、字元串、函數、類、文件操作等。階段課程結束後，學員需要完成Pygame實戰飛機大戰、2048等項目。

第二階段：Python語言高級

主要學習Python庫、正則表達式、進程線程、爬蟲、遍歷以及MySQL資料庫。

第三階段：Pythonweb開發

主要學習HTML、CSS、JavaScript、jQuery等前端知識，掌握python三大後端框架(Django、 Flask以及Tornado)。需要完成網頁界面設計實戰;能獨立開發網站。

第四階段：Linux基礎

主要學習Linux相關的各種命令，如文件處理命令、壓縮解壓命令、許可權管理以及Linux Shell開發等。

第五階段：Linux運維自動化開發

主要學習Python開發Linux運維、Linux運維報警工具開發、Linux運維報警安全審計開發、Linux業務質量報表工具開發、Kali安全檢測工具檢測以及Kali 密碼破解實戰。

第六階段：Python爬蟲

主要學習python爬蟲技術，掌握多線程爬蟲技術，分布式爬蟲技術。

第七階段：Python數據分析和大數據

主要學習numpy數據處理、pandas數據分析、matplotlib數據可視化、scipy數據統計分析以及python 金融數據分析;Hadoop HDFS、python Hadoop MapRece、python Spark core、python Spark SQL以及python Spark MLlib。

第八階段：Python機器學習

主要學習KNN演算法、線性回歸、邏輯斯蒂回歸演算法、決策樹演算法、樸素貝葉斯演算法、支持向量機以及聚類k-means演算法。

關於python後端開發需要學什麼的內容，青藤小編就和您分享到這里了。如果您對python編程有濃厚的興趣，希望這篇文章可以為您提供幫助。如果您還想了解更多關於python編程的技巧及素材等內容，可以點擊本站的其他文章進行學習。

Ⅳ 3. 用任意一種編程語言（C/C++/Java/C#/VB.NET）寫出任意一種你所知的排序演算法（比如：冒泡排序， 歸並排

#include<stdio.h>
#include<stdlib.h>
void BubbleSort(int a[], const int first, const int last);//冒泡排序
void InsertSort(int a[], const int first, const int last);//插入排序
void SelectSort(int a[], const int first, const int last);//選擇排序
void MergeSort(int a[], const int p, const int r);//合並排序
void QuickSort(int a[],const int p,const int r);//快速排序
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t);//希爾排序
void HeapSort(int a[],const int p, int r); //堆排序
void StoogeSort(int a[],const int p,const int r);//Stooge排序(不用)演算法復雜度沒算清楚

void main()
{
//插入排序演算法
int a[11] = {6,4,5,3,2,1};
int dlta[]={9,5,3,2,1};
//BubbleSort(a,0,5);
//InsertSort(a,0,5);
//SelectSort(a,0,5);
//MergeSort(a,0,5);
//QuickSort(a,0,5);
//ShellSort(a,0,5,dlta,5);
HeapSort(a,0,5);
//StoogeSort(a,0,5);

for(int i=0; i<=5;i++)
{
printf("%d ",a[i]);
}

}

/************************冒泡排序***********************/
void BubbleSort(int a[], int first, int last)
{
//實現對數組a[]中a[first]到a[last]升序的「冒泡」排序
int i,j,temp;
for(i=first; i<=last; i++)
{
for(j=first; j< last-i; j++)
{
if(a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}

/************************插入排序***********************/
void InsertSort(int a[], int first, int last)
{
//實現對數組a[]中a[first]到a[last]升序的「插入」排序
//最壞情況為n的平方，，多用於小數組
int i,j,temp;
for(i=first+1; i<=last; i++)
{
temp = a[i];
j = i - 1;
while((j >= 0) && (a[j] > temp))
{
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}

/************************選擇排序***********************/
void SelectSort(int a[], int first, int last)
{
//實現對數組a[]中a[first]到a[last]升序的「選擇」排序
int i, j, temp, num;
for(i=first; i<last; i++)
{
num = i;
for(j=i+1; j<=last; j++)
{
if(a[j] < a[num])
{
num = j;
}
}
if(i != num)
{
temp = a[num];
a[num] = a[i];
a[i] = temp;
}
}
}

/************************合並排序***********************/
void Merge(int a[],const int p,const int q,const int r)
{
//合並排序演算法中的實現合並的子程序
int iLLength,iRLength;
int *L, *R, i, j, k;
iLLength = q - p + 1;
iRLength = r - q;
L = (int *)malloc(iLLength*sizeof(int)); //或者 C++中 new int[iLLength];
R = (int *)malloc(iRLength*sizeof(int)); //或者 C++中 new int[iRLength];
if(L == 0 || R== 0)
{
printf("內存分配失敗！！！");
return;
}
for(i=0; i<iLLength; i++)
{
L[i] = a[p+i];
}
for(j=0; j<iRLength; j++)
{
R[j] = a[q+j+1];
}
i = 0;
j = 0;
for(k=p; k<=r; k++)
{
if((i<iLLength) && (j<iRLength) && (L[i]<=R[j]) || (j == iRLength))
{
a[k] = L[i];
i++;
}
else if(j<iRLength)
{
a[k] = R[j];
j++;
}
}

free(R);free(L);
}
void MergeSort(int a[],const int p,const int r)
{
//合並排序演算法-主程序
//n*lg(n),系數較小
int q;
if(p<r)
{
q = (p+r)/2;
MergeSort(a,p,q);
MergeSort(a,q+1,r);
Merge(a,p,q,r);
}
}

/************************Stooge排序***********************/
void StoogeSort(int a[],const int p,const int r)
{
//Stooge演算法
int temp, k;
if(a[p]>a[r])
{
temp = a[p];
a[p] = a[r];
a[r] = temp;
}
if((p+1) >= r)
{
return;
}
k = (r-p+1)/3;
StoogeSort(a,p,r-k);
StoogeSort(a,p+k,r);
StoogeSort(a,p,r-k);
}

/************************快速排序*********************/
int QuickPartition(int a[],const int p,const int r)
{
//快速排序的(關鍵)分治過程
int temp, x, i, j;
x = a[r];
i = p - 1;
for(j=p; j<r; j++)
{
if(a[j] <= x)
{
i = i + 1;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[i+1];
a[i+1] = a[r];
a[r] = temp;
return (i+1);
}
/*
void QuickSort(int a[],const int p,const int r)
{
//快速排序演算法-主程序
//與下面的「尾遞歸實現方法」比較，缺點：右邊數組的遞歸不是必須的，增加了運行堆棧深度和調用開銷
int q;
if(p < r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
QuickSort(a, q+1, r);
}
}
*/
void QuickSort(int a[],int p,const int r)
{
//快速排序演算法-主程序
//「尾遞歸實現方法」是對上面的快速排序主程序實現的一種優化
//系數較小,常用大數組
int q;
while(p < r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
p = q + 1;
}
}

/************************希爾排序**********************/
void ShellInsert(int a[],const int p,const int r, int dk)
{
//希爾排序演算法的關鍵子程序-插入排序子程序
int i, j, temp;
for(i=p+dk; i<=r; i++)
{
if(a[i] < a[i-dk])
{
temp = a[i];
for(j=i-dk; ((j>=0) && (temp < a[j])); j -= dk)
{
a[j+dk] = a[j];
}
a[j+dk] = temp;
}
}
}

void ShellSort(int a[],const int p,const int r,const int dlta[],const int t)
{
//希爾排序演算法-主程序
//按增量序列dlta[]中的前t個增量，實現對數組a[]中a[p]到a[r]的排序
//dlta[]可能取值如：1,2,3,5,9 dala[k]=2^(t-k+1)-1 其中0<=k<=t<=ld(b-1)
//增量序列的最後一個值必須是1
//增量序列中的值沒有除1以外的因子， 其精確時間復雜度：數學上尚未解決的難題
int k;
for(k=0; k<t; k++)
{
ShellInsert(a,p,r,dlta[k]);
}
}

/************************堆排序***********************/
//堆排序，不如快速排序
//但是可用其來實現「優先順序隊列」
int Parent(int i)
{
return ((i+1)/2-1);
}

int Right(int i)
{
return (2*(i+1)-1);
}

int Left(int i)
{
return (2*(i+1));
}

void Max_Heapify(int a[],const int hplast,const int i)
{
int l, r,largest,temp;
l = Left(i);
r = Right(i);
largest = ((l<=hplast) && (a[l]>a[i])) ? l:i;
if((r<=hplast) && (a[r]>a[largest]))
{
largest = r;
}
if(largest != i)
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
Max_Heapify(a,hplast,largest);
}

}

void Build_Max_Heap(int a[],const int p, const int r)
{
int i;
for(i = (p+r)/2; i>=p; i--)
{
Max_Heapify(a,r,i);
}
}

void HeapSort(int a[],const int p, int r)
{
int i,temp;
Build_Max_Heap(a,p,r);
for(i = r; i > p; i--)
{
temp = a[p];
a[p] = a[i];
a[i] = temp;
r -= 1;
Max_Heapify(a,r,0);
}
}