排序算法:速度存在于人们的头脑中 - Andrei Alexandrescu - CppCon 2019

Sorting Algorithms: Speed Is Found In The Minds of People - Andrei Alexandrescu - CppCon 2019

频道:CppCon · 时长:1:29:55 · 发布:2019-09-18 · 播放:184209

在 YouTube 观看

简介

Andrei Alexandrescu 在 CppCon 2019 的演讲重新审视排序,展示无分支技巧、混合策略和成本度量如何加速现代硬件上的 std::sort 风格算法。

HN 为什么推荐

HN 推荐它作为一个有趣的演讲,从简单开始,深入实践性能优化。

起初他只是展示简单的东西,但请坚持看下去,他讲得很深入。 — HN, 2023

C、C++、Rust、Go 与系统语言 · 软件性能与优化 · 算法与数据结构

中文字幕节选

我不会介绍安德烈的简历,他都有维基百科页面了,如果你还没 读过,你应该去读读。你们中有些人可能没看过安德烈的演讲,我 有点羡慕你们,因为看过的人知道他们 即将第一次体验什么。你会笑,你会学到东西,当你 回家时——我还没听过,但我保证这将是你会 告诉别人的演讲。所以准备 好吧 这是一个著名的算法,大家都知道,它只是用汇编器实现的。当 你弄清楚它是什么时,举手,你有15秒 我只想引起你的注意,这不是,只是一些随机代码。好的,官方 公告:演讲结束后会进行签书 活动,没时间了 提到他会吃东西,什么时候结束,好吧,然后他会 等等,我和他谈过,他会等到结束。你们在这里是囚犯,这 是因为我们有一大堆材料要过。快速说一下,什么,抱歉,请原谅 我 抱歉,有点混淆,我说的是shed load,我说 shed load,这是个词,是个体面的词,它在剑桥 词典里 剑桥,不是马萨诸塞州的剑桥,剑桥,休息一下 好吧,太快了 说这是个词。那么排序是怎么回事? 排序是怎么回事?嗯,它只是计算机科学中研究最多的问题 有史以来,就像你知道的,如果你谷歌,如果你去谷歌学术 搜索排序算法,就有无数论文,最新的 是2019年的,而且它很有意义,不是分析之类的,所以是的,有新的 排序算法和新东西,绝对惊人。所以排序绝对是 计算机科学的基础,CS完全,如果你愿意,基本来说,它 如果你是音乐家,你必须演奏安娜·玛格达莱娜·巴赫的前奏曲,对吧,任何 你演奏的乐器,如果你是瑜伽,我听到一个好的左,如果你是瑜伽人,你 必须做像摊尸式,我不知道,像服务,我可以做足够,他就像你 躺下,什么都不做,那太棒了。所以如果你是程序员,你必须 一生中实现一次排序,就得做,坐下来做 它,甚至不太难,因为我们有 一些神圣的算法,其中快速排序自然是第一个 想到的。那么为什么它如此受欢迎,在所有标准库实现中,对于 C++和其他库,对于C++和其他语言,你会发现快速排序 就像排序实现的麦当娜。现在 它是一个非常好的算法,很有道理,它是教科书 分治法的应用,你可以花时间和才能,你知道 你可以对边缘情况有很多洞察来优化它,因为它如此 简单,容易分析。实际上有点有趣,快速排序比 快速选择更容易分析,后者是一个更简单的算法。所以快速排序分析 很容易,数学不难。快速选择绝对疯狂,是的,我 实际上喜欢最新的和最伟大的,他们不得不使用数学软件 来分析它,因为他们无法推导出公式,所以它更困难 和爱因斯坦的广义相对论一样,好吧,也许我有点夸张 快速排序的一个好处是它对几乎排序或已排序的数据做很少的工作 如果你正确切割,如果你照顾它, 一切都会工作得很好。是的,非常好的属性,幂等性 这也是一个礼貌的词,意思是如果数据已经 排序,它不会打乱它。有些排序算法会 打乱数据,即使它已排序,比如 谢谢,堆排序。堆排序的第一件事是 我们必须把最大的元素放在数组的最后,第一

HN 上的讨论

我非常喜欢 Andrei Alexandrescu 的演讲“Speed Is Found In The Minds Of People”。一开始他只是展示一些简单的东西,但请坚持看下去,他会深入探讨。[VIDEO] — bboreham, 2023-12
严格来说不算系列讲座,但 Andrei Alexandrescu 在 CppCon 上做过一些非常精彩的 keynote 演讲。我现在甚至都不写 C++ 了,但这些演讲我看过不止一遍,它们有趣、平易近人、鼓舞人心:Speed Is Found In The Minds of People [VIDEO] std::allocator Is to Allocation what std::vector Is to Vexation [LINK] 我真正享受观看的一个系列讲座是“The WE-Heraeus International Winter School on Gravity and Light”,它使用现代数学方法讲解广义相对论:[LINK] 同样,我已经 20 年没碰物理了,但我发现它出奇地容易跟上,因为讲得非常清晰。 — jiggawatts, 2023-01
这里有一个很好的例子,说明了 GP 所说的:[VIDEO](视频很长,如果赶时间可以跳到 26:00)关键在于代码并不是在真空中运行的。它是在处理数据(或控制系统等)。较少的代码可能以低效的方式处理数据,而较多的代码可能更高效地完成。在上面的演讲中,这种对比非常鲜明,因为“更多代码”的版本做了一些事情,然后做了与“更少代码”版本完全相同的事情,但速度更快。这种情况足够常见(尽管不像上面的例子那么鲜明),所以“更少的代码更快”并不是一个很好的“默认”假设。 — r_sreeram, 2023-09
我很喜欢 Alexandrescu 在 CppCon 2019 的演讲“Speed Is Found In The Minds of People”,关于为现代硬件优化通用排序例程。[VIDEO] — jacobolus, 2020-01
在他的演讲“Speed Is Found In The Minds of People”[0]中,Andrei Alexandrescu 尝试为中等大小的向量实现非常快的排序,然后以关于这个精确区别的思考结束。如果你对这个问题感兴趣,值得一看。[0]: [VIDEO] — nestorD, 2019-11

相关视频