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