【AICon】 如何构建高效的 RAG 系统?RAG 技术在实际应用中遇到的挑战及应对策略?>>> 了解详情
写点什么

这可能是你听说过最快的稳定排序算法

  • 2019-10-18
  • 本文字数:2313 字

    阅读完需:约 8 分钟

这可能是你听说过最快的稳定排序算法

知道 Java 和 Python 的默认排序算法是什么吗?这个算法叫作 Timsort,由 Tim Peters 与 2001 年创建,是一种稳定高效的面向真实数据的排序算法。


Timsort 是一种面向真实数据的高效排序算法,它不是在学术实验室中创建出来的。2001 年,Tim Peters 为 Python 创建了 Timsort 算法。Timsort 算法首先对排序数据进行分析,然后根据分析结果来选择排序方式。


在该算法出现之后,就一直被作为 Python、Java、Android 平台和 GNU Octave 的默认排序算法。


Timsort 的时间复杂度是 O(n log n)。关于时间复杂度,可以参考下图。



Timsort 的排序时间与归并排序相同。实际上,Timsort 使用了插入排序和归并排序,你很快就会看到。


Timsort 利用了存在于大多数真实数据集中的已排序元素,这些已排序的元素被称为“natural runs”。算法会遍历要排序的数据,将元素收集到 run 中,同时将这些 run 合并在一起。

元素个数少于 64 的数组

如果数组的元素个数少于 64,Timsort 将执行插入排序。


插入排序是一种对小数据集最为有效的排序算法。它在排序较大的数据集时速度很慢,但在排序较小的数据集时速度很快。插入排序的思想如下:


  • 逐个检查元素;

  • 在正确的位置插入正确的元素,以此来构建排好序的列表。



在这个示例中,我们将新排序的元素插入到一个新的子数组中,从数组的头部开始。


插入排序的 GIF 动画演示:


关于 run

如果列表的元素个数大于 64,Timsort 会先遍历列表,查找严格递增或递减的部分。如果这个部分是递减的,就反转这个部分。


所以,如果 run 是递减的,它看起来像这样(其中 run 使用粗体表示):



如果不是递减的,它看起来是这样的:



minrun 根据数组的大小来确定。当 run 的数量等于或略小于 2 的幂时,合并 2 个数组的效率会更高。为了确保效率,Timsort 选择的 minrun 通常等于或小于 2 的幂。


minrun 的取值范围为 32 到 64。原始数组的长度除以 minrun 仍然等于或略小于 2 的幂。


如果 run 的长度小于 minrun,就用 minrun 减去这个 run 的长度,得出一个数字,然后针对这个数字长度的元素执行插入排序,以此来创建新的 run。


所以,如果 minrun 是 63,run 的长度是 33,那么就是 63-33=30,也就是对 run[33]前的 30 个元素执行插入排序来创建新的 run。


在这部分完成之后,我们就有了一系列排好序的 run。

合并

接下来,Timsort 会执行归并排序,将 run 合并在一起。Timsort 在执行合并排序时会确保稳定性和均衡性。


为了确保稳定性,我们不需要交换两个相等的数字。这样不仅可以保持它们在列表中的原始位置不动,而且会让算法更快。我们很快就会解释合并的均衡性问题。


在遇到一个 run 时,Timsort 将它添加到栈中。一个简单的栈看起来像这样:



你可以想象面前有一叠盘子,但你不能从底部拿盘子,必须从顶部拿。栈也是这个原理。


Timsort 在合并 run 时会尝试平衡两个相互矛盾的需求。一方面,我们希望尽可能多地推迟合并,以便找出可能会出现的模式,但也更希望尽快地进行合并,以便利用刚刚发现的 run。但我们不能延迟合并“太久”,因为我们需要记住未合并的 run,而这样做会消耗更多的内存。


为了获得这种平衡,Timsort 会跟踪栈上最新的三个项,这些项必须遵循以下规则:


  1. A > B + C

  2. B > C


其中 A、B 和 C 是栈上最新的三个项。


通常,合并不同长度的相邻的 run 是很困难的,而更困难的是我们必须确保稳定性。为了解决这个问题,Timsort 会留出临时内存,将较小的 run 放到临时内存中。

“奔驰”模式

Timsort 在合并 run A 和 run B 时会发现其中一个 run 连续多次“获胜”。如果 run A 的数字都比 run B 的数字小,那么 run A 的数字最后会待在原来的位置上。合并这两个 run 需要做大量的工作,但并没有产生任何结果。


排序的数据通常会有一些预先存在的内部结构。Timsort 假设如果 run A 的多个值小于 run B 的值,那么很可能 A 的值都小于 B 的值。



在示例中,run A 和 run B 必须严格递增或递减。


Timsort 将进入奔驰(gallop)模式。Timsort 不检查 A[0]和 B[0]之间的相互关系,而是进行二分查找,以便找出 B[0]在 A[0]中的位置。这样,Timsort 就可以将 A 的整个部分移动到合适的位置。然后,Timsort 在 B 中搜索 A[0]的位置,再将 B 的整个部分移动到适当的位置。


让我们来看看它是如何运行的。Timsort 检查 B[0](即 5),并使用二分查找找出它在 A 中的位置。


可以看到,B[0]在 A 的尾部。然后,Timsort 检查 A[0](即 1)在 B 中的位置。可以看到,数字 1 在 B 的开头。我们现在知道 B 在 A 的尾部,A 在 B 的开头。


事实证明,如果 B[0]的位置非常接近 A 的开头,那这么做就不值得,反之亦然。如果是这种情况,它就会快速退出奔驰模式。此外,Timsort 会把这个记下来,并通过增加连续 A 或连续 B 的数量来提高进入奔驰模式的门槛。如果进入奔驰模式是值得的,Timsort 会让重新进入奔驰模式变得容易些。


总的来说,Timsort 有两个方面做得非常好:


  • 对存在内部结构的数组排序有非常好的性能

  • 能够保持稳定的排序


在以前,为了实现稳定的排序,必须将列表中的项映射成整数,并将其作为元组数组进行排序。

代码

如果你对代码不感兴趣,请跳过这一部分。


代码并不完整,与 Python 中的 sorted()也不一样。这只是一个简化版的 Timsort,我主要用它来演示 Timsort 算法。如果你想查看 Timsort 的原始源代码,请点击https://github.com/python/cpython/blob/master/Objects/listobject.c。Timsort 算法的正式版本是用 C 语言实现的,而不是 Python。


Python 已经内置了 Timsort 算法,要使用 Timsort,只需这样写:


list.sort()
复制代码


或者:


sorted(list)
复制代码


如果你想掌握 Timsort 算法,我强烈建议你自己试着实现它!


原文链接:https://skerritt.blog/timsort-the-fastest-sorting-algorithm-youve-never-heard-of/


2019-10-18 08:004474
用户头像

发布了 38 篇内容, 共 30.4 次阅读, 收获喜欢 206 次。

关注

评论 1 条评论

发布
用户头像
一直想知道 python的内置排序 算法,这下可知道是 timsort了。
2019-10-18 17:33
回复
没有更多了
发现更多内容

云原生网关如何实现安全防护能力

阿里巴巴云原生

阿里云 云原生 网关

计算机视觉和滤帧技术

鲸品堂

计算机视觉 图像 企业号 7 月 PK 榜

实测结果公开:用户见证 StarRocks 存算分离优异性能!

StarRocks

数据库 大数据 数据仓库 OLAP 湖仓一体

人工智能LLM模型:奖励模型的训练、PPO 强化学习的训练、RLHF | 社区征文

汀丶人工智能

人工智能 强化学习 RLHF ppo算法 年中技术盘点

华为云CodeArts Check代码检查新手操作指南

华为云PaaS服务小智

云计算 代码规范 华为云 代码检查

使用 JavaScript 脚本来进行复杂的查询改写

极限实验室

Java JavaScript

3D云渲染的优点和缺点是什么?

Finovy Cloud

直播回顾|用户增长之路,如何兼具体验和点击率?

HMS Core

HMS Core

C++采用Daemon进行后台程序部署

攻城狮Wayne

如何使用 Amazon Systems Manager 集中管理 Amazon IoT Greengrass 设备

亚马逊云科技 (Amazon Web Services)

Amazon

香港成新加密中心,JPEX生态平台通证JPC获益颇多

EOSdreamer111

百度 APP iOS 端包体积 50M 优化实践 (四) 代码优化

百度Geek说

ios 代码优化 企业号 7 月 PK 榜

Nautilus Chain NautDID NFT 将上主网,Layer3 数字身份时代开启

鳄鱼视界

2023-07-17:给定一个数组arr,长度为n, 再给定一个数字k,表示一定要将arr划分成k个集合, 每个数字只能进一个集合。 返回每个集合内部的平均值都累加起来最小的值。 平均值向下取整。 1

福大大架构师每日一题

福大大架构师每日一题

AlienSwap 首期 Launchpad — 偶像女团 NFT+RWA 的创新探索

EOSdreamer111

香港成新加密中心,JPEX生态平台通证JPC获益颇多

股市老人

抓住风向“猪”持续飞,还是维持在风向的高度上?

Bonaparte

产品 产品经理 产品需求 产品培训

自动化接口回归测试神器 AREX 使用初体验

AREX 中文社区

自动化测试 AWS 流量回放

Debian11系统编译安装Docker教程。

百度搜索:蓝易云

Docker 云计算 Linux 运维 Debian

Debian11系统编译安装Pure-Ftpd教程。

百度搜索:蓝易云

云计算 Linux 运维 Debian Pure-FTPd

再获肯定!柏睿数据通过国家级专精特新“小巨人”企业复核

新消费日报

QCN9274+QCN9074 chip: efficient and stable Wi-Fi 6 solution

wifi6-yiyi

wifi6 WiFi7

大语言模型的预训练[1]:基本概念原理、神经网络的语言模型、Transformer模型原理详解、Bert模型原理介绍| 社区征文

汀丶人工智能

神经网络 Transformer NLP 大模型 BERT 年中技术盘点

直播解锁 Serverless 新进展,与 AIGC 结合有什么搞头?

阿里巴巴云原生

阿里云 Serverless 云原生 AIGC

AlienSwap 首期 Launchpad — 偶像女团 NFT+RWA 的创新探索

股市老人

简易注册中心监控NAS断电断网

WizInfo

Python

C语言实现解一元二次方程

codists

代码随想录Day20 - 二叉树(六)

jjn0703

Debian11系统编译安装phpMyAdmin教程。

百度搜索:蓝易云

云计算 Linux 运维 Debian phpMyAdmin

Debian11系统编译安装Apache教程。

百度搜索:蓝易云

Apache Linux 运维 云服务器 Debian

Debian11系统编译安装Tomcat教程。

百度搜索:蓝易云

云计算 tomcat Linux 运维 Debian

这可能是你听说过最快的稳定排序算法_语言 & 开发_Brandon Skerritt_InfoQ精选文章