作者 | Jeff Hale
原文 | https://towardsdatascience.com/surprising-sorting-tips-for-data-scientists-9c360776d7e
譯者 | kbsc13('算法猿的成長'公眾號作者)
聲明 | 翻譯是出于交流學習的目的，歡迎轉載，但請保留本文出于，請勿用作商業或者非法用途
導讀
這篇文章介紹了 Python 中幾個常用庫的排序技巧，包括原生 Python的、Numpy、Pandas、PyTorch、TensorFlow 以及 SQL。
前言
現在其實有很大基礎的排序算法，其中有的算法速度很快而且只需要很少的內存，有的算法更適合用于數據量很大的數據，有的算法適合特定排序的數據，下面的表格給出了大部分常用的排序算法的時間復雜度和空間復雜度：
對于大部分數據科學問題，并不需要精通所有排序算法的基礎實現。事實上，過早進行優化有時候會被認為是所有錯誤的根源。不過，了解哪個庫以及需要使用哪些參數進行排序是非常有幫助的，下面是我做的一份小抄：
接下來將分別介紹上述這幾個庫的排序方法，不過首先是介紹本文用到的這幾個庫的版本，因為不同版本的排序方法可能會有些不同：
Python
Python 包含兩個內置的排序方法：
sort 方法是兩者中速度更快的，因為是修改列表本身的關系。但這種操作是非常危險的，因為會修改原始數據。
兩種排序方法的默認排序方式都是升序--由小到大。大部分排序方法都可以接受一個參數來改變排序方式為降序，不過，不幸的是，每個庫的這個參數名字都不相同。
在 python 中，這個參數名字是 reverse，如果設置 reverse=True 表示排序方式是降序--從大到小。
key 也是一個參數名字，可以用于創建自己的排序標準，比如sort(key=len) 表示根據元素的長度進行排序。
在 python 中的唯一排序算法是Timsort。Timsort是源自歸并排序和插入排序，它會根據需要排序的數據的特征選擇排序方法。比如，需要排序的是一個短列表，就選擇插入排序方法。更詳細的Timsort實現可以查看 Brandon Skerritt 的文章：
https://skerritt.blog/timsort-the-fastest-sorting-algorithm-youve-never-heard-of/
Timsort是一個穩定的排序算法，這表示對于相同數值的元素，排序前后會保持原始的順序。
對于 sort() 和 sorted() 兩個方法的記憶，這里提供一個小技巧，因為sorted() 是一個更長的詞語，所以它的運行速度更長，因為需要做一個復制的操作。
Numpy
Numpy 是 Python 用于科學計算的基礎庫，它同樣也有兩個排序方法，一個改變數組本身，另一個進行復制操作：
下面是兩個方法可選的參數：
不過需要注意的是這個排序算法的使用和對這些參數名字的期待會有所不同，比如傳遞kind=quicksort實際上采用的是一個 introsort 算法，這里給出 numpy 的文檔解釋：
當沒有足夠的進展的時候，會轉成堆排序算法，它可以讓快速排序在最糟糕的情況的時間復雜度是 O(n*log(n))
stable會根據待排序數據類型自動選擇最佳的穩定排序算法。而如果選擇 mergesort 參數，則會根據數據類型采用 timsort 或者 radix sort 。因為 API 的匹配性限制了選擇實現方法并且也固定了對不同數據類型的排序方法。
Timsort是用于排序好的或者接近排序好的數據，對于隨機排列的數據，它的效果幾乎和 mergesort 一樣。目前它是作為排序算法，而如果沒有設置 kind 參數，默認選擇還是快速排序quicksort ,而對于整數數據類型，'mergesort' 和 'stable' 被映射為采用 radix sort 方法
上述來自 numpy 的文檔解釋，以及作者的部分修改：
https://github.com/numpy/numpy/blob/v1.16.1/numpy/core/fromnumeric.py#L815-L935
在上述介紹的幾個庫中，只有 numpy 是沒有可以控制排序方式的參數，不過它可以通過切片的方式快速反轉一個數組--my_arr[::-1]。
numpy 的算法參數在更加友好的 pandas 中可以繼續使用，并且我發現函數可以很容易就保持。
Pandas
Pandas 中對 DataFrame 的排序方法是 df.sort_values(by=my_column) ，參數有：
對于 Series 類似也是同樣的排序方法。但Series 并不需要指定 by 參數，因為不會有多列。
由于底層實現是采用 numpy ，所以同樣可以得到很好的優化排序選項，但 pandas 因為其便利性會額外耗時一點。
默認對單列的排序算法是采用 Numpy 的 quicksort ,當然實際上調用的排序算法是 introsort ，因為堆排序會比較慢。而對于多列的排序算法，Pandas 確保采用的是 Numpy 的 mergesort ，但實際上會采用 Timsort 或者 Radix sort 算法。這兩個都是穩定的排序算法，并且對多列進行排序的時候也是必須采用穩定的排序算法。
對于 Pandas，必須記住的是這些關鍵知識點是：
在做數據探索分析的時候，一般在對 DataFrame 做求和和排序數值的時候都采用方法 Series.value_counts()。這里介紹一個代碼片段用于對每列出現次數最多的數值進行求和和排序：
for c in df.columns: print(f'---- {c} ----') print(df[c].value_counts().head())Dask ，是一個基于 Pandas 的用于處理大數據的庫，盡管已經開始進行討論，直到2019年秋天的時候，還沒有實現并行排序的功能。關于這個庫，其 github 地址：
https://github.com/dask/dask
如果是小數據集，采用 Pandas 進行排序是一個不錯的選擇，但是數據量很大的時候，想要在 GPU 上并行搜索，就需要采用 TensorFlow 或者 PyTorch 了。
TensorFlow
TensorFlow 是目前最流行的深度學習框架，這里可以看下我寫的這篇對比不同深度學習框架的流行性和使用方法的文章：
https://towardsdatascience.com/which-deep-learning-framework-is-growing-fastest-3f77f14aa318?source=friends_link&sk=0a10207f22f4dbc143e7a90a3f843515
下面的介紹都是 TensorFlow 2.0 版本的 GPU 版本。
在 TensorFlow 中，排序方法是 tf.sort(my_tensor) ，返回的是一個排序好的 tensor 的拷貝。可選的參數有：
tf.sort 采用的是 top_k 方法，而 top_k 是采用 CUB 庫來使得 CUDA GPUs 更容易實現并行化操作。正如官方文檔說的：
CUB 提供給 CUDA 編程模型的每一層提供了最好的可復用的軟件組件。
TensorFlow 的排序算法通過 CUB 庫采用在 GPU 上的 radix sort ，詳細介紹可以查看：
https://github.com/tensorflow/tensorflow/issues/288
TensorFlow 的 GPU 信息可以查看：
https://www.tensorflow.org/install/gpu
如果需要讓 GPU 兼容 2.0 版本，需要采用下列安裝命令：
下面這個代碼可以查看是否每行代碼都在 GPU 或者 CPU 上運行：
tf.debugging.set_log_device_placement(True)
如果需要指定使用一個 GPU, 代碼如下所示：
如果是想用CPU，只需要將上述代碼第一行修為： with tf.device('/CPU:0')，也就是替換 GPU 為 CPU 即可。
tf.sort() 是非常容易記住的方法，另外就是記住需要改變排序順序，是修改參數 direction 。
PyTorch
PyTorch 的排序方法是：torch.sort(my_tensor)，返回的也是排序好的 tensor 的拷貝，可選參數有：
通過下列代碼來指定采用 GPU：
gpu_tensor=my_pytorch_tensor.cuda()%time torch.sort(gpu_tensor)
PyTorch 在面對一個數據量大于一百萬行乘10萬列的數據集的時候，是通過 Thrust 實現分割的并行排序。
但不幸的是，我嘗試在谷歌的 Cola 上通過 Numpy 構建一個 1.1M * 100 K 的隨機數據集的時候出現內存不足的錯誤，然后嘗試用 GCP 的 416 MB，出現同樣的內存不足的錯誤。
Thrust 是一個并行算法庫，可以使得性能在 GPUs 和多核 GPUs 之間移植。它可以自動選擇最有效率的排序算法實現。而剛剛介紹的 TensorFlow 使用的 CUB 庫是對 Thrust 的封裝。所以 PyTorch 和 TensorFlow 都采用相似的排序算法實現方式。
和 TensorFlow 一樣，PyTorch 的排序方法也是非常直接，很容易記住：torch.sort()。兩者稍微不同的就是排序順序的參數名字：TensorFlow 是 direction，而 PyTorch 是 descending 。另外，不要忘記通過 .cuda() 方法指定采用 GPU 來提高對大數據集的計算速度。
在大數據集通過 GPU 進行排序是很好的選擇，但直接在 SQL 上排序也是有意義的。
SQL
在 SQL 中進行排序通常都是非常快速，特別是數據加載到內存中的時候。
SQL 只是一個說明書，并沒有指定排序算法的具體實現方式。比如 Postgres 根據環境選擇采用 disk merge sort ，或者 quick sort 。如果內存足夠，可以讓數據加載在內存中，提高排序的速度。通過設置 work_mem 來增加可用的內存，具體查看：
https://wiki.postgresql.org/wiki/Tuning_Your_PostgreSQL_Server
其他的 SQL 數據庫采用不同的排序算法，比如根據下面這個回答，谷歌的 BigQuery 通過一些技巧實現 introsort 。
https://stackoverflow.com/a/53026600/4590385
在 SQL 中進行排序是通過命令 ORDER_BY ，這個用法和 python 的實現還是有區別的。但它這個命令名字很獨特，所以很容易記住。
如果是實現降序，采用關鍵詞 DESC。所以查詢顧客的名字，并根據字母表的倒序來返回的語句是如下所示：
比較
對上述介紹的方法，我都做了一個分析，采用同樣的 100萬數據，單列，數組或者列表的數據格式。使用的是谷歌的 Colab Jupyter Notebook，然后硬件方面是 K80 GPU, Intel(R) 的 Xeon(R) CPU @2.30GHZ。
源碼地址：https://colab.research.google.com/drive/1NNarscUZHUnQ5v-FjbfJmB5D3kyyq9Av
對比結果如下所示：
根據上圖可知：
另外，這就是一個小小的測試，絕對不是權威的結果。
總結
最后，通常我們都不需要自己實現排序算法，目前各個庫實現的方法以及很強大了。它們也并不是只采用一種排序算法，都是通過對不同類型的數據進行測試不同的排序算法，從而選擇不同情況下最佳的排序算法，甚至有的實現會改進算法本身來提高排序的速度。
本文介紹了在不同的 Python 庫和 SQL 進行排序的方法，一般來說只需要記得采用哪個參數實現哪個操作，然后下面是我的一些建議：
關于在 GPU 進行排序的做法，可以查看這篇文章：
https://devtalk.nvidia.com/default/topic/951795/fastest-sorting-algorithm-on-gpu-currently/
參考
