 作者 | Jeff Hale 原文 | https:///surprising-sorting-tips-for-data-scientists-9c360776d7e 译者 | kbsc13('算法猿的成长'公众号作者) 声明 | 翻译是出于交流学习的目的，欢迎转载，但请保留本文出于，请勿用作商业或者非法用途 导读
前言 现在其实有很大基础的排序算法，其中有的算法速度很快而且只需要很少的内存，有的算法更适合用于数据量很大的数据，有的算法适合特定排序的数据，下面的表格给出了大部分常用的排序算法的时间复杂度和空间复杂度：  对于大部分数据科学问题，并不需要精通所有排序算法的基础实现。事实上，过早进行优化有时候会被认为是所有错误的根源。不过，了解哪个库以及需要使用哪些参数进行排序是非常有帮助的，下面是我做的一份小抄：  接下来将分别介绍上述这几个库的排序方法，不过首先是介绍本文用到的这几个库的版本，因为不同版本的排序方法可能会有些不同： 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 包含两个内置的排序方法：
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 的文档解释：
上述来自 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:///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 更容易实现并行化操作。正如官方文档说的：
TensorFlow 的排序算法通过 CUB 库采用在 GPU 上的 radix sort ，详细介绍可以查看： https://github.com/tensorflow/tensorflow/issues/288 TensorFlow 的 GPU 信息可以查看： https://www./install/gpu 如果需要让 GPU 兼容 2.0 版本，需要采用下列安装命令： !pip3 install tensorflow-gpu==2.0.0-beta1 下面这个代码可以查看是否每行代码都在 GPU 或者 CPU 上运行： tf.debugging.set_log_device_placement(True) 如果需要指定使用一个 GPU, 代码如下所示： with tf.device('/GPU:0'): %time tf.sort(my_tf_tensor) 如果是想用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./wiki/Tuning_Your_PostgreSQL_Server 其他的 SQL 数据库采用不同的排序算法，比如根据下面这个回答，谷歌的 BigQuery 通过一些技巧实现 introsort 。 https:///a/53026600/4590385 在 SQL 中进行排序是通过命令 ORDER_BY ，这个用法和 python 的实现还是有区别的。但它这个命令名字很独特，所以很容易记住。 如果是实现降序，采用关键词 DESC。所以查询顾客的名字，并根据字母表的倒序来返回的语句是如下所示： SELECT Names FROM CustomersORDER BY Names 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./default/topic/951795/fastest-sorting-algorithm-on-gpu-currently/ 参考
|
|
|
