對數(shù)據(jù)進行分類整理是數(shù)據(jù)科學(xué)家和數(shù)據(jù)工程師的基礎(chǔ)工作。Python會提供許多內(nèi)置庫，優(yōu)化排序選項。有些庫甚至可以同時在GPU上運行。令人驚奇的是，一些排序方法并沒有使用之前所述的算法類型，其他方法的執(zhí)行效果也不如預(yù)期。

選擇使用哪種庫和哪類排序算法著實難辦，因為算法的執(zhí)行變化很快。本文將具體展開講解，提供一些幫助記憶算法的技巧，分享測速的結(jié)果。 

開始排序吧!

更新于2019年7月17日：速度測試結(jié)果現(xiàn)在包括PyTorch和TensorFlow的GPU執(zhí)行。TensorFlow還包括tensorflow==2.0.0-beta1和tensorflow-gpu==2.0.0-beta1下的CPU結(jié)果。令人感到驚奇的發(fā)現(xiàn)是：PyTorch GPU變亮的速度更快，TensorFlow GPU比TensorFlow CPU速度更慢。

有許多不同的基本排序算法。有些比其他執(zhí)行速度更快、占用內(nèi)存更小。有些適合處理大數(shù)據(jù)，還有些可以更好地對特定序列數(shù)據(jù)進行排排序?？蓞⒁娤卤砹私庠S多常用算法的時間和空間復(fù)雜性。 

圖片來自 http://bigocheatsheet.com/

了解基礎(chǔ)的算法并不能解決大多數(shù)數(shù)據(jù)科學(xué)問題。事實上，過早的優(yōu)化處理說不定什么時候就會被視為錯誤源泉。不過需要重復(fù)排序大量數(shù)據(jù)時，知道使用哪個庫和哪些關(guān)鍵字參數(shù)會十分有用。以下是一個備忘表。 

Google表格可在此處獲取

多年來，許多庫的排序算法都發(fā)生了變化。用于本文分析的軟件版本如下。

• python 3.6.8
• numpy 1.16.4
• pandas 0.24.2
• tensorflow==2.0.0-beta1
• #tensorflow-gpu==2.0.0-beta1 slows sorting
• pytorch 1.1

讓我們從基礎(chǔ)開始吧!

Python (vanilla版) 

Python包含兩個內(nèi)置排序法。

• my_list.sort()對原有列表進行排序。改變了列表。sort()返回None。
• sorted(my_list)生成任何可迭代的排序副本。sorted()返回已排序的迭代。sort()不會改變原始迭代。

sort()應(yīng)該更快，因為已到位。神奇的是這不是下面測試中的發(fā)現(xiàn)。就地排序更危險，因為會改變原始數(shù)據(jù)。 

說到vanilla版Python，本文呈現(xiàn)的默認(rèn)排序順序都是升序—從小到大。大多數(shù)排序方法采用關(guān)鍵字參數(shù)，將順序切換為降序。對大腦來說很不幸，因為每個庫的參數(shù)名稱都不同。

要將vanilla Python中排序方式更改為降序，通過reverse = True.

key可以作為關(guān)鍵字參數(shù)來傳遞，從而創(chuàng)建自己的排序標(biāo)準(zhǔn)。例如，sort(key = len)將按照每個列表項的長度排序。

Vanilla Python中唯一使用的排序算法是Timsort。Timsort會根據(jù)要排序的數(shù)據(jù)特征選擇排序方法。舉個例子，如果排短列表，就采用插入排序。

Timsort以及Vanilla Python的其他算法都很穩(wěn)定。這意味著如果有多個相同值，這些數(shù)據(jù)在排序后仍維持原始順序。

想要記住sort()與sorted()不同，就記著sorted比sort單詞長，并且因復(fù)制需要排序時間會更長。雖然下面的結(jié)果與傳統(tǒng)觀念相悖，但助記符仍然起作用。

NumPy 

Numpy是用于科學(xué)計算的Python基礎(chǔ)庫。與vanilla Python一樣，有兩種執(zhí)行方式，一種是變異數(shù)組，另一種是數(shù)據(jù)的復(fù)制。

• my_array.sort()改變有序數(shù)組并返回已排序數(shù)組。
• np.sort(my_array)返回已排序數(shù)組的副本，因此原始數(shù)組不會改變。

以下是可選參數(shù)。

• axis：int，可選—要排序的軸。默認(rèn)值為-1，表示沿最后一個軸排序。
• kind：{'quicksort'，'mergesort'，'heapsort'，'stable'}，可選—排序算法。默認(rèn)為'quicksort'。詳細(xì)信息如下。
• order：str或str的列表，可選—當(dāng)a是已定義字段的數(shù)組時，該參數(shù)會指定首先比較哪一字段，其次是哪個等等?？梢灾付▎蝹€字段為字符串，而且不是所有字段都需指定，不過仍需按照未指定字段在dtype中的順序執(zhí)行，打破聯(lián)系。

現(xiàn)在，人們使用的排序算法與根據(jù)名字聯(lián)想的略有不同。通過kind = quicksort意味著排序?qū)嶋H是從introsort算法開始的。

若[它]沒有明顯進展，則會切換成堆排序算法。執(zhí)行該操作最壞的情況就是產(chǎn)生快速排序O(n * log(n))。Stable會自動為正在排序的數(shù)據(jù)類型選擇最穩(wěn)定的排序算法。目前依據(jù)數(shù)據(jù)類型，它與合并排序一起映射到tim排序或基數(shù)排序中。API前向兼容性目前抑制了選擇執(zhí)行的能力，并且是不同數(shù)據(jù)類型的硬連線。添加Timsort是為了更好地處理已完成或幾乎排好序的數(shù)據(jù)。對于隨機數(shù)據(jù)，timsort在處理方式上幾乎與mergesort相同。現(xiàn)在timsort用于穩(wěn)定排序，而在沒有其他選擇的情況下，quicksort仍為默認(rèn)排序...'mergesort'和'stable'會映射到整數(shù)數(shù)據(jù)類型的基數(shù)排序。 來自Numpy文檔 -(部分內(nèi)容有改動)

其中一點是Numpy提供了比vanilla Python排序算法選項更大的控制范圍。第二點是kind關(guān)鍵字值不一定與實際排序類型相對應(yīng)。最后一點是mergesort和stable值是穩(wěn)定的，但quicksort和heapsort不是。

Numpy排序是列表中唯一沒有用關(guān)鍵字參數(shù)來反轉(zhuǎn)排序順序的操作。幸運的是，這個可快速反轉(zhuǎn)數(shù)組順序：my_arr [:: -1]。

Numpy算法選項在更受歡迎的Pandas中也適用—而且這些功能更容易保持穩(wěn)定。

Pandas 

通過df.sort_values(by = my_column)對Pandas DataFrame進行排序。有許多可用關(guān)鍵字參數(shù)。

• by：str或str of list，required—要排序的名稱或名稱列表。如果axis為0或index，那by可能會有索引級別和/或列標(biāo)簽。如果axis為1或columns，則by可能含級別和/或索引標(biāo)簽。
• axis：{0或index，1或columns}，默認(rèn)為0—排序軸。
• ascending：bool或bool列表，默認(rèn)為True—按升序與降序排序。指定多個排序順序的列表。如果是bool列表，就必須與by參數(shù)長度匹配。
• inplace：bool，默認(rèn)為False—如果為True，則直接對其執(zhí)行操作。
• kind：{quicksort，mergesort，heapsort或stable}，默認(rèn)快速排序—選擇排序算法。可另參見ndarray.np.sort了解更多內(nèi)容。對于DataFrames，此法僅應(yīng)用于單列或單標(biāo)簽的排序。
• na_position：{‘first’，‘last’}，默認(rèn)‘last’ - 首先以NaNs作為開頭，最后將NaNs作為結(jié)尾。

按照相同的句法對Pandas系列進行排序。用Series時，不需要輸入by關(guān)鍵字，因為列不多。

Pandas用到了Numpy計算法，動動手指即可輕松獲得同等優(yōu)化的排序選項。但是，Pandas操作需要更多的時間。

按單列排序時的默認(rèn)設(shè)置是Numpy的quicksort。如果排序進度很慢，那么實際為內(nèi)省排序的quicksort會變?yōu)槎雅判?。Pandas確保多列排序使用Numpy的mergesort。Numpy中的mergesort實際用的是Timsort和Radix排序算法。這些排序算法都很穩(wěn)定，而且多數(shù)列排序中穩(wěn)定排序是很有必要的。

使用Pandas需記住的關(guān)鍵內(nèi)容：

• 函數(shù)名稱：sort_values()。
• by= column_name或列名列表。
• “ ascending”是逆轉(zhuǎn)的關(guān)鍵字。
• 用mergesort進行穩(wěn)定排序。

在進行探索性數(shù)據(jù)分析時，常發(fā)現(xiàn)自己是用Series.value_counts()在Pandas DataFrame中對值進行求和排序的。這是一個代碼片段，用于每列常用值的求和和排序。 

for c in df.columns:  
print(f"---- {c} ---")  
print(df[c].value_counts().head()) 

Dask，實際上是用于大數(shù)據(jù)的Pandas，到2019年中期還沒有實現(xiàn)并行排序，盡管大家一直在討論這個。

對小數(shù)據(jù)集進行探索性數(shù)據(jù)分析，Pandas排序是個不錯的選擇。當(dāng)數(shù)據(jù)很大，想要在GPU上并行搜索時，你也許會想到TensorFlow或PyTorch。

TensorFlow 

TensorFlow是最受歡迎的深度學(xué)習(xí)框架。以下是TensorFlow 2.0的簡介。

tf.sort(my_tensor)返回tensor排序副本?？蛇x參數(shù)有：

• axis：{int，optional}待排序軸。默認(rèn)值為-1，對最后一個軸進行排序。
• direction：{ascending or descending}—數(shù)值排序的方向。
• name：{str，optional}—操作的名稱。

tf.sort在幕后使用top_k()方法。top_k使用CUB庫的CUDA GPU促使并行性更容易實現(xiàn)。正如文檔所述“CUB為CUDA編程模型的每一項程序都提供了最先進、可重復(fù)利用的軟件組件。”TensorFlow通過CUB在GPU上使用基數(shù)排序。

為了使GPU能夠滿足TensorFlow 2.0，你需要!pip3 install tensorflow-gpu==2.0.0-beta1。我們會從下面的評論看到，如果你要進行排序，你可能想堅持tensorflow==2.0.0-beta1。

使用下面一小段代碼來檢查代碼的每一行是否都能在CPU 或GPU中運行：

tf.debugging.set_log_device_placement(True) 

為了詳述你想要使用GPU,使用下面代碼： 

with tf.device('/GPU:0'):  
%time tf.sort(my_tf_tensor) 

使用 with tf.device('/CPU:0'):為了使用CPU。

假如在TensorFlow中工作，tf.sort()是非常直觀的記憶和使用方法。只需記住direction = descending可轉(zhuǎn)換排序順序。

PyTorch 

torch.sort(my_tensor)返回tensor排序副本。可選參數(shù)有：

• dim：{int，optional} - 待排序維度
• descending：{bool，optional} - 控制排序順序(升序或降序)。
• out：{tuple，optional} - (Tensor，LongTensor)的輸出元組，可以作為輸出緩沖區(qū)。

通過將.cuda()粘貼到張量的末尾來指定要使用GPU進行排序。 

gpu_tensor=my_pytorch_tensor.cuda()  
%time torch.sort(gpu_tensor) 

一些分析表明，如果任何大于100萬行乘以100,000列的數(shù)據(jù)集要排序，PyTorch將通過Thrust利用分段式并行排序。

不幸的是，當(dāng)我們試圖通過Google Colab中的Numpy創(chuàng)建1.1M x 100K隨機數(shù)據(jù)點時，發(fā)現(xiàn)內(nèi)存已不足。然后嘗試了416 MB RAM的GCP，依舊沒有內(nèi)存。

分段排序和位置排序是mergesort的高性能體現(xiàn)，處理非均勻隨機數(shù)據(jù)。分段排序使我們能夠并行排序許多長度可變數(shù)組。 https://moderngpu.github.io/segsort.html

Thrust作為并行算法庫，實現(xiàn)了GPU與多核CPU之間的聯(lián)系。提供了排序原語，可自動選擇最有效的執(zhí)行方式。TensorFlow使用的CUB庫會用來包裝Thrust。PyTorch和TensorFlow在操作時GPU分類法相似 - 無論選擇何種。

與TensorFlow一樣，PyTorch的排序方法記起來相當(dāng)容易：torch.sort()。唯一費腦子的是排序值的方向：TensorFlow使用direction，而PyTorch使用descending。

雖然用GPU進行排序?qū)τ诜浅４蟮臄?shù)據(jù)集來說可能是一個很好的選擇，但直接在SQL中對數(shù)據(jù)進行排序也是可以的。

SQL

SQL中的排序通常非?？欤貏e是在內(nèi)存中執(zhí)行時。

SQL很規(guī)范，但沒有規(guī)定某操作必須使用哪種排序算法。Postgres使用磁盤合并排序，堆排序或快速排序，視情況而定。如果內(nèi)存夠，在內(nèi)存中排序會更快。通過work_mem設(shè)置增加排序的可用內(nèi)存。

其他SQL的執(zhí)行使用不同排序算法。例如，根據(jù)Stack Overflow的回答，谷歌BigQuery的內(nèi)省排序采取了一些措施。

SQL中的排序由ORDER BY命令執(zhí)行。這種句法不同于所有使用單詞sort的Python排序執(zhí)行。其實更容易記住SQR語句與ODER BY，因為非常獨特。

為使排序降序，請用關(guān)鍵字DESC。因此，按字母順序從最后一個到第一個反饋給客戶的查詢?nèi)缦滤荆?/p>

• SELECT Names FROM Customers
• ORDER BY Names DESC;

比較

對于上面的每個Python庫，我們對wall time進行了分析，以便在單列，單數(shù)組或單列表中對相同的1,000,000個數(shù)據(jù)點進行排序。同時使用了配有T4 GPU的Google Colab Jupyter筆記本。 

數(shù)據(jù)來源: https://colab.research.google.com/drive/1NNarscUZHUnQ5v-FjbfJmB5D3kyyq9Av

觀察

• 對于Numpy和Pandas，inplace比復(fù)制數(shù)據(jù)更快。這并不奇怪。
• Pandas默認(rèn)快速排序相當(dāng)快。
• 大多數(shù)Pandas功能相對較慢。
• TensorFlow操作相當(dāng)快。
• Python inplace排序慢得出奇。比Numpy inplace mergesort和TensorFlow慢了10倍。曾多次對其進行測試(使用不同的數(shù)據(jù))來確認(rèn)這不是一個異?，F(xiàn)象。

重申，這只是一個小測試。絕對不是決定性的。

Wrap

通常不需要自定義排序。選擇很多。一般不會采用單一的排序方法。相反，首先對數(shù)據(jù)進行評估，然后用效果更好的排序算法。如果排序進展不快，執(zhí)行操作時也會自行改變算法。

在本文中，你已經(jīng)了解了如何在Python數(shù)據(jù)科學(xué)堆和SQL中的每個板塊里進行排序。

只需要記住選擇哪個選項以及如何調(diào)用它們。可用上面的備忘表，節(jié)省時間。大致建議如下：

• 使用默認(rèn)的Pandas sort_values()來探索相對較小的數(shù)據(jù)集。
• 數(shù)據(jù)集較大或運行速度較高時，嘗試Numpy的就地合并，PyTorch或TensorFlow并行GPU方式或SQL。