高性能树操作,APL 之道 // Aaron Hsu // Dyalog '18

High-performance Tree Wrangling, the APL Way // Aaron Hsu // Dyalog '18

频道:Dyalog User Meetings · 时长:30:37 · 发布:2018-11-30 · 播放:5790

在 YouTube 观看

简介

Aaron Hsu 展示如何在 APL 中使用数组和反转表而不是指针来操作和转换树数据。他声称代码更小、性能更好且更容易并行化。

HN 为什么推荐

HN 推荐它作为使用数组编程进行高性能树处理的突出例子。

他有一个演讲(可在 YouTube 上观看)关于他在 APL 中使用数组以高性能方式处理树结构的方法 — HN, 2021

编程语言设计 · 软件性能与优化 · 算法与数据结构

中文字幕节选

在我们开始之前,我想鼓励大家站起来稍微走动一下, 我不知道,挪动一下座位,做点什么,我有一份讲义, 你知道,这会很有趣,但现在还不许看,好的,传下去,不会花 太多时间,传下去,沿着过道传,不要看,不要偷看,那样就 没意思了,好了,现在站起来,伸展一下, 让头脑准备好,因为我已经说明了我们要做什么, 所以我们直接开始,我们会玩得开心,准备好你们的 求值器,每个人都有他们的REPL会话,我们准备好了,第一次执行集 记住它,我们没问题,好的,树,大家都知道 树,这里有人不知道树吗?好的好的,很好,所以大多数人当 我们处理树时,包括APL程序员,我们都必须以某种方式处理这个, 当然,欢迎你在整个过程中保持站立,或者你可以 坐下,随你便,大多数人这样想树,所以我们有一个顶部根 节点,然后有一些兄弟节点或一些子节点从那里向下, 然后从那里那些子节点可以有子节点等等,我们有一堆 后代,我们有一些兄弟节点,所以在根节点有一个,亚当节点, 如果你愿意,然后那里有一些子节点,你知道,塞特、哈姆或 类似的东西,所以你可以让兄弟节点彼此相邻,然后 它们向下,大多数人也知道树的深度,对吧,所以一棵树 可以有它的深度,这里我们将使用索引原点零,所以我们将从 深度零开始,然后从那里向下,好的,现在不幸的是,这是 大多数人停止思考树的地方,或者他们开始使用他们在 大学学到的东西,如果我们愿意,我们可以基本上说这个演讲可以 被改写为说,你在大学学到的关于树的一切,忘掉它, 你错了,或者你知道,我们以APL方式做这个,所以我在这里 展示的是一种我们可以处理这些树的方法,保持我们的渐近性,但 以我们被告知需要思考问题的方式来思考这些东西, 所以马丁说向量、数组等等,我们需要确保 我们正确地做我们的读取,除此之外,我想我听到一些 人提到我并没有在幻灯片上放很多信息,所以 你知道,我用了很多幻灯片,对吧,只是快速浏览它们,我忍不住 自己,对不起,我道歉,但你们自找的,所以 来了,幻灯片,所以这就是我们之前有的同一棵树, 但现在我们稍微重新组织了一下,所以在这一点上我们真正 需要做的是,我们需要思考我们如何重新思考树 是什么,当我们处理它时,对吧,所以这需要一点可视化, 以及一点工作,所以这是我们的树,和之前一样的树,但我们 重新定向了它,这种重新定向至关重要,因为最常见的 遍历之一,我们在树中看到的,叫做深度优先前序遍历, 那是什么?APL程序员可能会开始弄清楚,所以开始思考 一下这可能是什么,但这里我们可以给每个节点一个 身份,一个基于深度优先前序遍历的ID,恰好 这个第一个前序遍历,它是DFPT,对应于访问那些节点 按照我们在这里可视化的顺序,所以你触摸每个节点,然后向下 到最左边的子节点,然后你触摸那个,然后向下,从 那里向下,然后你弹回来,然后继续沿着那条路径向下,对吧,我们 可以做的是,我们可以看看这个,我们可以重新组织它,就像我们

HN 上的讨论

> “这节省了分配,节省了总内存使用” Co-Dfns 是 Aaron Hsu 的项目,他有一个演讲[1]讲一个用 nano-pass 风格实现的编译器,分别用 Racket、Chez Scheme[2] 和 Dyalog APL 各实现了一次,每次都使用 CPU 和 GPU。对于编译一个约 1600 万节点的 AST,他给出的基准数据是:Dyalog APL 需要 64MB 内存来容纳它,Racket 需要 1051MB,Chez Scheme 需要 1485MB。他在演讲中提出的挑衅性说法是“指针是编程的精制糖”。APL 版本的代码行数只有[4]的 1/50,在 CPU 上通常快 9 倍,在 GPU 上快 50 到 200 倍,尽管它是由 Dyalog 解释执行,而 Scheme 是编译执行。也有一些基准测试中 APL 版本在运行时间上落败,那是在不到 1k 行代码的情况下(他称之为… — jodrellblank, 2021-06
我在听那场关于 APL 中树的操纵与变换的演讲时,正是这种感觉(很棒,就像 Aaron 做的一切一样),[VIDEO] — snaky, 2020-01
资格:多年前我被引入函数式编程,并最终达到对 FP 整体有深入理解的程度。在我看来,Haskell 是“最好的”语言(“最好”是指考虑所有权衡后提供最佳整体收益)。我不再确信 Haskell 是“最好的”语言了。我最近接触了一种可能比 Haskell 更好的语言:Dyalog APL。([LINK])。自己试试([LINK]) 为了解释原因,我推荐观看 Aaron Hsu 关于 Dyalog APL 的视频: - APL 需要类型系统吗?([LINK]) - 这实际上是一个非常有趣的问题,比乍一看更微妙。 - APL 中的设计模式与反模式([LINK]) - 这个视频给我的主要收获是“习语优于库”的原则。 - 更高性能的树处理,APL 方式([VIDEO]) - 或者如何通过使用“倒置表”来建模树而不使用指针。(倒置表是一种列是行、行是列的表) — kadblas, 2019-06

相关视频