Python,Numpy,Pandas…數據科學家必備排序技巧
對數據進行分類整理是數據科學家和數據工程師的基礎工作。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表格可在此處獲取
多年來，許多庫的排序算法都發生了變化。用于本文分析的軟件版本如下。
- 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。
