比 O(nlog(n)) 做得更好 — 5.结束语和基准

这就是 groupSort 真正优于 mergeSort 的地方。

长按关注《Python学研大本营》，加入读者群，分享更多精彩 扫码关注《Python学研大本营》，加入读者群，分享更多精彩

最后的想法

我们知道，将一个大问题分解为一系列更小、更简单的问题是一种基本的编程范式。通过检查这些关于排序的想法，可以看出，有时，我们也可以从将我们的问题变成一个完全不同的问题中受益。通过这样做，我们也许能够使用真正提高效率和速度的工具和方法——我们在原始环境中无法使用的工具和方法。

这种方法在大数据环境中似乎具有非凡的价值。在这些环境中，我可能有数以百万计的数据点，如果不是数以百万计的数以百计，甚至数十亿的数据点，其范围将相对较小。从下面的基准中可以看出，这就是 groupSort 真正开始明显优于 mergeSort 的地方。

基准

使用的 Python 版本：3.9.7

处理器：AMD Ryzen 5 3600 6 核处理器 3.60 GHz

内存：16.0 GB

显卡：NVIDIA GeForce RTX 2060 Super

原版 Python groupSort 与 C 实现的 timSort

首先，让我真正说明一下我的观点。我将用普通 Python 编写的方法与 Python 的 sorted() 函数进行比较，根据 Wikipedia的说法，该函数是 mergeSort 和 insertSort 的组合，并使用 C 实现。我运行了 100 次迭代的测试，生成了一个随机数组每次100万个元素和10万个范围（不包括在时间统计中）。结果如下：

Timsort，即Python的sorted()函数：

基本组排序：

Vanilla Python 阈值比较

groupSort 与 timSort（~rng 5000 万，大小 100 万）

groupSort 与 quickSort（~rng 2500 万，大小 100 万）

groupSort vs. countSort（组总是~2x 快）

groupSort 与 bucketSort（~rng 380 万，大小 100 万）

与 mergeSort 的详细比较

现在，关于普通 Python 中的 groupSort 与普通 Python 中的 mergeSort 的基准比较。

在前面的部分中，所有代码示例都是单次运行。在这里，我将提供这些场景在多次迭代中平均时的屏幕截图。

包含 100 万个元素的数组，具有1亿个范围，100 次迭代

使用基本组排序：

使用数字桶分组排序：

使用合并排序：

100 万个元素的数组，1000万个范围，100 次迭代

使用基本组排序：

使用数字桶分组排序：

使用合并排序：

100 万个元素的数组， 100万个范围，100 次迭代

使用基本组排序：

使用数字桶分组排序：

使用合并排序：

100 万个元素的数组， 10 万个范围，100 次迭代

使用基本组排序：

使用数字桶分组排序：

使用合并排序：

100 万个元素的数组，10000个范围，100 次迭代

使用基本组排序：

使用数字桶分组排序：

使用合并排序：

100 万个元素的数组，1000个范围，100 次迭代

使用基本组排序：

使用数字桶分组排序：

使用合并排序：

（完结）

https://medium.com/@ajchristian86/doing-better-than-o-nlog-n-part-5-68895553fb99

推荐书单

《Pandas1.x实例精解》

本书详细阐述了与Pandas相关的基本解决方案，主要包括Pandas基础，DataFrame基本操作，创建和保留DataFrame，开始数据分析，探索性数据分析，选择数据子集，过滤行，对齐索引，分组以进行聚合、过滤和转换，将数据重组为规整形式，组合Pandas对象，时间序列分析，使用Matplotlib、Pandas和Seaborn进行可视化，调试和测试等内容。此外，本书还提供了相应的示例、代码，以帮助读者进一步理解相关方案的实现过程。 本书适合作为高等院校计算机及相关专业的教材和教学参考书，也可作为相关开发人员的自学用书和参考手册。

链接：https://u.jd.com/UKjx4et

精彩回顾

《Pandas1.x实例精解》新书抢先看！

【第1篇】利用Pandas操作DataFrame的列与行

【第2篇】Pandas如何对DataFrame排序和统计

【第3篇】Pandas如何使用DataFrame方法链

【第4篇】Pandas如何比较缺失值以及转置方向？

【第5篇】DataFrame如何玩转多样性数据

【第6篇】如何进行探索性数据分析？

【第7篇】使用Pandas处理分类数据

【第8篇】使用Pandas处理连续数据

【第9篇】使用Pandas比较连续值和连续列

【第10篇】如何比较分类值以及使用Pandas分析库

长按关注《Python学研大本营》

长按二维码，加入Python读者群

扫码关注《Python学研大本营》，加入读者群，分享更多精彩