全文共6168字，預計學習時長12分鐘
對數據進行分類整理是數據科學家和數據工程師的基礎工作。Python會提供許多內置庫，優化排序選項。有些庫甚至可以同時在GPU上運行。令人驚奇的是，一些排序方法並沒有使用之前所述的算法類型，其他方法的執行效果也不如預期。
選擇使用哪種庫和哪類排序算法著實難辦，因為算法的執行變化很快。本文將具體展開講解，提供一些幫助記憶算法的技巧，分享測速的結果。
分好類的茶
開始排序吧！
更新於2019年7月17日：速度測試結果現在包括PyTorch和TensorFlow的GPU執行。TensorFlow還包括tensorflow==2.0.0-beta1和tensorflow-gpu==2.0.0-beta1下的CPU結果。令人感到驚奇的發現是：PyTorch GPU變亮的速度更快，TensorFlow GPU比TensorFlow CPU速度更慢。
有許多不同的基本排序算法。有些比其他執行速度更快、佔用內存更小。有些適合處理大數據，還有些可以更好地對特定序列數據進行排排序。可參見下表了解許多常用算法的時間和空間複雜性。
圖片來自 http://bigocheatsheet.com/
了解基礎的算法並不能解決大多數數據科學問題。事實上，過早的優化處理說不定什麼時候就會被視為錯誤源泉。不過需要重複排序大量數據時，知道使用哪個庫和哪些關鍵字參數會十分有用。以下是一個備忘表。
Google表格可在此處獲取：
https://docs.google.com/spreadsheets/d/1zQbDvpmrvTYVnRz_2OTlfB6knLlotdbAoFH6Oy48uSc/edit?usp=sharing
多年來，許多庫的排序算法都發生了變化。用於本文分析的軟體版本如下。
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
讓我們從基礎開始吧！
Python (vanilla版)
Python包含兩個內置排序法。
my_list.sort（）對原有列表進行排序。改變了列表。sort（）返回None。
sorted（my_list）生成任何可迭代的排序副本。sorted（）返回已排序的迭代。sort（）不會改變原始迭代。
sort（）應該更快，因為已到位。神奇的是這不是下面測試中的發現。就地排序更危險，因為會改變原始數據。
香草味冰激凌
說到vanilla版Python，本文呈現的默認排序順序都是升序—從小到大。大多數排序方法採用關鍵字參數，將順序切換為降序。對大腦來說很不幸，因為每個庫的參數名稱都不同。
要將vanilla Python中排序方式更改為降序，通過reverse = True.
key可以作為關鍵字參數來傳遞，從而創建自己的排序標準。例如，sort（key = len）將按照每個列表項的長度排序。
Vanilla Python中唯一使用的排序算法是Timsort。Timsort會根據要排序的數據特徵選擇排序方法。舉個例子，如果排短列表，就採用插入排序。
Timsort以及Vanilla Python的其他算法都很穩定。這意味著如果有多個相同值，這些數據在排序後仍維持原始順序。
想要記住sort（）與sorted（）不同，就記著sorted比sort單詞長，並且因複製需要排序時間會更長。雖然下面的結果與傳統觀念相悖，但助記符仍然起作用。
NumPy
Numpy是用於科學計算的Python基礎庫。與vanilla Python一樣，有兩種執行方式，一種是變異數組，另一種是數據的複製。
my_array.sort（）改變有序數組並返回已排序數組。
np.sort（my_array）返回已排序數組的副本，因此原始數組不會改變。
以下是可選參數。
axis：int，可選—要排序的軸。默認值為-1，表示沿最後一個軸排序。
kind：{'quicksort'，'mergesort'，'heapsort'，'stable'}，可選—排序算法。默認為'quicksort'。詳細信息如下。
order：str或str的列表，可選—當a是已定義欄位的數組時，該參數會指定首先比較哪一欄位，其次是哪個等等。可以指定單個欄位為字符串，而且不是所有欄位都需指定，不過仍需按照未指定欄位在dtype中的順序執行，打破聯繫。
現在，人們使用的排序算法與根據名字聯想的略有不同。通過kind = quicksort意味著排序實際是從introsort算法開始的。
若[它]沒有明顯進展，則會切換成堆排序算法。執行該操作最壞的情況就是產生快速排序O（n * log（n））。Stable會自動為正在排序的數據類型選擇最穩定的排序算法。目前依據數據類型，它與合併排序一起映射到tim排序或基數排序中。API前向兼容性目前抑制了選擇執行的能力，並且是不同數據類型的硬連線。添加Timsort是為了更好地處理已完成或幾乎排好序的數據。對於隨機數據，timsort在處理方式上幾乎與mergesort相同。現在timsort用於穩定排序，而在沒有其他選擇的情況下，quicksort仍為默認排序...'mergesort'和'stable'會映射到整數數據類型的基數排序。 來自Numpy文檔 -（部分內容有改動）
其中一點是Numpy提供了比vanilla Python排序算法選項更大的控制範圍。第二點是kind關鍵字值不一定與實際排序類型相對應。最後一點是mergesort和stable值是穩定的，但quicksort和heapsort不是。
Numpy排序是列表中唯一沒有用關鍵字參數來反轉排序順序的操作。幸運的是，這個可快速反轉數組順序：my_arr [:: -1]。
Numpy算法選項在更受歡迎的Pandas中也適用—而且這些功能更容易保持穩定。
Pandas
通過df.sort_values（by = my_column）對Pandas DataFrame進行排序。有許多可用關鍵字參數。
by：str或str of list，required—要排序的名稱或名稱列表。如果axis為0或index，那by可能會有索引級別和/或列標籤。如果axis為1或columns，則by可能含級別和/或索引標籤。
axis：{0或index，1或columns}，默認為0—排序軸。
ascending：bool或bool列表，默認為True—按升序與降序排序。指定多個排序順序的列表。如果是bool列表，就必須與by參數長度匹配。
inplace：bool，默認為False—如果為True，則直接對其執行操作。
kind：{quicksort，mergesort，heapsort或stable}，默認快速排序—選擇排序算法。可另參見ndarray.np.sort了解更多內容。對於DataFrames，此法僅應用於單列或單標籤的排序。
na_position：{『first』，『last』}，默認『last』 - 首先以NaNs作為開頭，最後將NaNs作為結尾。
按照相同的句法對Pandas系列進行排序。用Series時，不需要輸入by關鍵字，因為列不多。
Pandas用到了Numpy計算法，動動手指即可輕鬆獲得同等優化的排序選項。但是，Pandas操作需要更多的時間。
按單列排序時的默認設置是Numpy的quicksort。如果排序進度很慢，那麼實際為內省排序的quicksort會變為堆排序。Pandas確保多列排序使用Numpy的mergesort。Numpy中的mergesort實際用的是Timsort和Radix排序算法。這些排序算法都很穩定，而且多數列排序中穩定排序是很有必要的。
使用Pandas需記住的關鍵內容：
函數名稱：sort_values（）。
by= column_name或列名列表。
「 ascending」是逆轉的關鍵字。
用mergesort進行穩定排序。
在進行探索性數據分析時，常發現自己是用Series.value_counts（）在Pandas DataFrame中對值進行求和排序的。這是一個代碼片段，用於每列常用值的求和和排序。
for c in df.columns:
print(f"---- {c} ---")
print(df[c].value_counts().head())
Dask，實際上是用於大數據的Pandas，到2019年中期還沒有實現並行排序，儘管大家一直在討論這個。
對小數據集進行探索性數據分析，Pandas排序是個不錯的選擇。當數據很大，想要在GPU上並行搜索時，你也許會想到TensorFlow或PyTorch。
TensorFlow
TensorFlow是最受歡迎的深度學習框架。以下是TensorFlow 2.0的簡介。
tf.sort（my_tensor）返回tensor排序副本。可選參數有：
axis：{int，optional}待排序軸。默認值為-1，對最後一個軸進行排序。
direction：{ascending or descending}—數值排序的方向。
name：{str，optional}—操作的名稱。
tf.sort在幕後使用top_k（）方法。top_k使用CUB庫的CUDA GPU促使並行性更容易實現。正如文檔所述「CUB為CUDA編程模型的每一項程序都提供了最先進、可重複利用的軟體組件。」TensorFlow通過CUB在GPU上使用基數排序。
為了使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可轉換排序順序。
PyTorch
torch.sort（my_tensor）返回tensor排序副本。可選參數有：
dim：{int，optional} - 待排序維度
descending：{bool，optional} - 控制排序順序（升序或降序）。
out：{tuple，optional} - （Tensor，LongTensor）的輸出元組，可以作為輸出緩衝區。
通過將.cuda（）粘貼到張量的末尾來指定要使用GPU進行排序。
gpu_tensor=my_pytorch_tensor.cuda()
%time torch.sort(gpu_tensor)
一些分析表明，如果任何大於100萬行乘以100,000列的數據集要排序，PyTorch將通過Thrust利用分段式並行排序。
不幸的是，當我們試圖通過Google Colab中的Numpy創建1.1M x 100K隨機數據點時，發現內存已不足。然後嘗試了416 MB RAM的GCP，依舊沒有內存。
分段排序和位置排序是mergesort的高性能體現，處理非均勻隨機數據。分段排序使我們能夠並行排序許多長度可變數組。 https://moderngpu.github.io/segsort.html
Thrust作為並行算法庫，實現了GPU與多核CPU之間的聯繫。提供了排序原語，可自動選擇最有效的執行方式。TensorFlow使用的CUB庫會用來包裝Thrust。PyTorch和TensorFlow在操作時GPU分類法相似 - 無論選擇何種。
與TensorFlow一樣，PyTorch的排序方法記起來相當容易：torch.sort（）。唯一費腦子的是排序值的方向：TensorFlow使用direction，而PyTorch使用descending。
雖然用GPU進行排序對於非常大的數據集來說可能是一個很好的選擇，但直接在SQL中對數據進行排序也是可以的。
SQL
SQL中的排序通常非常快，特別是在內存中執行時。
SQL很規範，但沒有規定某操作必須使用哪種排序算法。Postgres使用磁碟合併排序，堆排序或快速排序，視情況而定。如果內存夠，在內存中排序會更快。通過work_mem設置增加排序的可用內存。
其他SQL的執行使用不同排序算法。例如，根據Stack Overflow的回答，谷歌BigQuery的內省排序採取了一些措施。
SQL中的排序由ORDER BY命令執行。這種句法不同於所有使用單詞sort的Python排序執行。其實更容易記住SQR語句與ODER BY，因為非常獨特。
為使排序降序，請用關鍵字DESC。因此，按字母順序從最後一個到第一個反饋給客戶的查詢如下所示：
SELECT Names FROM Customers
ORDER BY Names DESC;
比較
對於上面的每個Python庫，我們對wall time進行了分析，以便在單列，單數組或單列表中對相同的1,000,000個數據點進行排序。同時使用了配有T4 GPU的Google Colab Jupyter筆記本。
數據來源: https://colab.research.google.com/drive/1NNarscUZHUnQ5v-FjbfJmB5D3kyyq9Av
觀察
對於Numpy和Pandas，inplace比複製數據更快。這並不奇怪。
Pandas默認快速排序相當快。
大多數Pandas功能相對較慢。
TensorFlow操作相當快。
Python inplace排序慢得出奇。比Numpy inplace mergesort和TensorFlow慢了10倍。曾多次對其進行測試（使用不同的數據）來確認這不是一個異常現象。
重申，這只是一個小測試。絕對不是決定性的。
Wrap
通常不需要自定義排序。選擇很多。一般不會採用單一的排序方法。相反，首先對數據進行評估，然後用效果更好的排序算法。如果排序進展不快，執行操作時也會自行改變算法。
在本文中，你已經了解了如何在Python數據科學堆和SQL中的每個板塊裡進行排序。
只需要記住選擇哪個選項以及如何調用它們。可用上面的備忘表，節省時間。大致建議如下：
使用默認的Pandas sort_values（）來探索相對較小的數據集。
數據集較大或運行速度較高時，嘗試Numpy的就地合併，PyTorch或TensorFlow並行GPU方式或SQL。
留言 點讚 關注
我們一起分享AI學習與發展的乾貨
編譯組：黃雪嬌、孫夢琪
相關連結：
https://towardsdatascience.com/surprising-sorting-tips-for-data-scientists-9c360776d7e
如需轉載，請後臺留言，遵守轉載規範