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

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

開始排序吧!

更新于2019年7月17日：速度測(cè)試結(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ù)，還有些可以更好地對(duì)特定序列數(shù)據(jù)進(jìn)行排排序。可參見下表了解許多常用算法的時(shí)間和空間復(fù)雜性。 

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

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

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包含兩個(gè)內(nèi)置排序法。

• my_list.sort()對(duì)原有列表進(jìn)行排序。改變了列表。sort()返回None。
• sorted(my_list)生成任何可迭代的排序副本。sorted()返回已排序的迭代。sort()不會(huì)改變?cè)嫉?/li>

sort()應(yīng)該更快，因?yàn)橐训轿?。神奇的是這不是下面測(cè)試中的發(fā)現(xiàn)。就地排序更危險(xiǎn)，因?yàn)闀?huì)改變?cè)紨?shù)據(jù)。 

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

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

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

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

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

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

NumPy 

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

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

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

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

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

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

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

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

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

Pandas 

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

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

按照相同的句法對(duì)Pandas系列進(jìn)行排序。用Series時(shí)，不需要輸入by關(guān)鍵字，因?yàn)榱胁欢唷?/p>

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

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

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

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

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

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

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

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

TensorFlow 

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

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

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

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

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

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

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排序副本?？蛇x參數(shù)有：

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

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

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

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

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

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

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

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

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

SQL

SQL中的排序通常非常快，特別是在內(nèi)存中執(zhí)行時(shí)。

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

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

SQL中的排序由ORDER BY命令執(zhí)行。這種句法不同于所有使用單詞sort的Python排序執(zhí)行。其實(shí)更容易記住SQR語句與ODER BY，因?yàn)榉浅＊?dú)特。

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

• SELECT Names FROM Customers
• ORDER BY Names DESC;

比較

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

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

觀察

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

重申，這只是一個(gè)小測(cè)試。絕對(duì)不是決定性的。

Wrap

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

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

只需要記住選擇哪個(gè)選項(xiàng)以及如何調(diào)用它們?？捎蒙厦娴膫渫?，節(jié)省時(shí)間。大致建議如下：

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