简洁数据结构
Succinct Data Structures
频道:Edward Kmett · 时长:1:26:10 · 发布:2013-11-12 · 播放:9154
简介
Edward Kmett 2013 年在布达佩斯 Prezi 关于简洁数据结构的演讲,这些数据结构以接近信息论最小空间存储数据,同时支持快速查询。它将研究联系在一起,并介绍了他的 Haskell succinct 库。
HN 为什么推荐
评论者称赞这是他们第一次了解简洁数据结构的地方,并发现它留下了持久的印象。
他的众多演讲之一,给我留下了难以置信的持久印象 — HN, 2018
中文字幕节选
[音乐] 嗨,披萨不多了 还剩一些。随便再拿点吧。 那么,感谢大家前来。 呃,你们可能已经看到了,我们请到了 Edward Kmett,他从遥远的 美国远道而来。他还带了一些贴纸。 我相信现在匈牙利的 Haskell 贴纸比知道 Haskell 是什么的人 还要多。随便拿一些吧。 想拿多少就拿多少。 那里大概有一千张一卷。 嗯,如果你们拿完了,下次我再带一卷来。 谢谢。那么,你们可能想靠近一点,因为会 用到白板。没错。 躲在那边那么远。 你们会看不到的。 没错。那么,我想介绍就到这里。 请开始吧。哦天哪。 看看我能不能把它扔到那边。 我会试着同时拿着麦克风和呃干擦记号笔。 看看我能不能真的搞定这个动作。 好的。 嗯,所以我很喜欢 Haskell。它是我最喜欢用来思考的语言。 嗯,Haskell 有很多非常擅长的事情。 嗯,但也有一些地方,我想思考一些问题,而 Haskell 作为一个生态系统,真的没有投入过任何注意力。 嗯,我非常喜欢,怎么说呢,不写那种 八年后再回头看会问自己我为什么写这个的代码? 嗯,你知道,那种为不存在的架构调优常量的代码,或者 做出的时间与空间权衡在更永恒的意义上根本说不通的代码。 对吧。嗯,我有点幸运,我有自由能做到这一点。 嗯,所以我花了很多时间在 寻找那些刚刚变得实用的数据结构,或者那些刚刚 开始获得它们所需的所有部件,能够被实际 使用的数据结构。嗯,但它们真的还没有得到那种 对细节的关注。 嗯,我找到了一些,嗯,最初是在试图 避开一堆专利的时候发现的。 嗯,所以谁说专利不能促进创新? 嗯,所以我想要,我想要,我想要 今天大致讲一讲,嗯,一种叫做简洁数据结构的东西。 呃,那是什么意思。会有很多大 O 符号和小 O 符号,以及 各种计算机科学的东西,如果你没有积极追求 计算机科学教育,或者最近几年没有这样做,可能 有点生疏了。嗯,我提前道歉。 嗯,我会尽量让它容易理解。 嗯,我关注的主要重点是试图 用尽可能最小的空间来表示某样东西,同时仍然支持 索引。好的。以一种非常严格的方式。 这就是,这就是我要讲的高层概述,就是 这里有一堆工具,让我能用尽可能最小的空间表示数据, 同时仍然让我能以某种方式遍历并计算聚合。 遍历并处理,嗯,回答有趣的查询,做连接和 其他事情。我会,我今天能讲到其中一些。 好的,这样我们就知道我在哪了。 我想在发送 我的 笔记本电脑之前,再拉出一点东西来。 这个能伸到这里吗? 好的。好的。嗯,那么话虽如此,我,我,我可能应该 解释一下简洁作为数据结构到底是什么意思。 好的。所以如果我们有像位向量这样的东西,只是一个只有 1 和 零,没什么大不了的。 0 1 0 0 1。我写在白板上的字大小还行吗? 这样行吗?呃,好的。 嗯,如果这里面有 n 个数字,那么我们有,你知道,第零项 呃,从 0 到 n 减 1。嗯,这里一共有 n 个比特,
HN 上的讨论
今晚我没心情。喝着威士忌,尽量不去想以色列的镜头和朝鲜局势有多糟糕。也许这就是为什么这不是最好的帖子。我不是要贬低所展示的工作。好文章,好总结,技术扎实。只是它比让我兴奋的东西要老;20 年来取得了很大进展,但大部分还没有找到商业应用。但这里有很多在这个领域惊人工作的引用根源:[LINK] 我绝对的英雄 Edward Kmett 很久以前做了一个演讲,将很多这项工作串联起来:[VIDEO]。我不知道他是否继续 pursue 了,这只是他众多演讲中给我留下极其持久印象的一个。这种技术的变体适用于任意文档和结构,在非常高的数据量下效果更好,具有缓存无关特性,并支持事务。对于所有查询都相当好的通用索引(而不是特定查询)也是可能的。结合基于区分的技术进行 O(n) 表连接,可能整个创业公司都围绕于此。抱歉我现在不能做得更好。 — KirinDave, 2018-05
我第一次听说简洁数据结构这个概念是从 Edward Kmett 那里,他是一位著名的 Haskeller,许多流行的 Haskell 库都出自他手。很久以前他做过一个关于简洁数据结构的演讲:[VIDEO] — kccqzy, 2025-03
我觉得有点好笑,人们在竞争最快速解码器,针对一种极其低效的格式。别误会,我喜欢比如 ZX Spectrum 演示,但这种努力的实际效用值得怀疑。但撇开这一点,我想知道这与压缩索引方法相比如何(见 [VIDEO] 和 [LINK]),显然,一旦索引建立起来。 — js8, 2017-05
相关视频
- Ruby Conf 12 - Y Not- 函数式编程历险记 by Jim Weirich · Confreaks · 53:21
- 但什么是傅里叶变换?视觉介绍。 · 3Blue1Brown · 19:41
- Erlang和Elixir的灵魂 • Sasa Juric • GOTO 2019 · GOTO Conferences · 42:02
- “简单造就易用” - Rich Hickey (2011) · Strange Loop Conference · 1:01:38
- Richard Feldman 谈“让不可能的状态不可能” · elm-conf · 25:06
- D/A 与 A/D | 数字展示与讲解(Monty Montgomery @ xiph.org) · FL Studio · 23:52
- William Byrd 谈“有史以来最美丽的程序” [PWL NYC] · PapersWeLove · 1:31:05
- Rich Hickey 谈价值的价值 · InfoQ · 31:43
- 为什么函数式编程没有成为主流?—— Richard Feldman · Metosin · 46:09
- 也许不 - Rich Hickey · ClojureTV · 1:03:28
- 用 Clojure 的方式解决问题 - Rafal Dittwald · Clojure/north · 1:02:26
- 第一讲A:Lisp概述与简介 · MIT OpenCourseWare · 1:12:55
- APL中的康威生命游戏 · Dyalog · 7:47
- 讲座 1A | MIT 6.001 计算机程序的构造和解释,1986 · MIT OpenCourseWare · 1:12:55
- CppCon 2017: Matt Kulukundis “逐步设计一个快速、高效、缓存友好的哈希表” · CppCon · 59:33
- 高效程序 - Clojure 10年 - Rich Hickey · ClojureTV · 1:14:51