算法与计算机科学cstheory.stackexchange.com编辑精选
自 Okasaki 以来纯函数数据结构有哪些新进展？
What's new in purely functional data structures since Okasaki? (2010)
2010 — 2016，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是 CSTheory StackExchange 上的一个经典问答，讨论自 Okasaki 的《纯函数式数据结构》出版以来，该领域有哪些新进展。回答涵盖了 finger trees、Bagwell/Hickey 的持久化向量等重要成果，多次登上 HN 首页，成为该主题的常青参考。
为什么经久不衰：它是了解 Okasaki 之后纯函数式数据结构研究进展的最佳起点，多年后仍是该领域的权威索引。
HN 评论精选
C++ 因缺少 GC 和尾递归而难以实现持久化数据结构，若能突破将意义重大
我在这个领域最有趣的发现是：由于缺乏 GC 或尾递归，这类数据结构无法像在其他语言中那样在 C++ 中实现。另一个发现是，Swift 等语言引入了许多表面上的函数式惯用法，但缺少持久化结构——Swift 用 C++ 实现，恐怕正是这个原因。如果有人能巧妙地在 C++ 中实现 Okasaki 的成果，那将是改变语言格局的大事。
hellofunk查看英文原文
Perhaps the most interesting "discovery" for me in this area is that these types of data structures are not possible in C++ as they are in other languages, due to lack of GC or tail recursion[0], either of which could make them a reality. The other discovery is that some languages, like Swift, are introducing lots of surface-level functional idioms that resemble their counterparts in truly functional languages, but without the persistent structures. Since Swift is implemented in C++, no doubt that's why it's not a reality in that new language either. If someone could cleverly invent an implementation of Okasaki that worked in a language like C++ (and some smart people have really tried), I think it would be a major game changer to the language's possibilities. This handicap is a rare example of something that is simply not so possible in C++. [0] https://github.com/BartoszMilewski/Okasaki/issues/1
实践 Okasaki 的数据结构是很好的学习路径
我最近用 Scheme 的 SRFI-41 流实现了 Okasaki 的持久化队列，非常有趣。现在我需要弄懂 finger trees 这类结构，才能理解持久化向量和哈希表。
davexunit查看英文原文
I implemented Okasaki's persistent queue in Scheme recently using SRFI-41 streams and it was a lot of fun. Now, I need to grok things like finger trees so I can understand persistent vectors and hash tables.
Bagwell 的 trie 和 Hickey 的向量是影响最深远的后续成果
Phil Bagwell/Rich Hickey 的向量（trie）的重要性怎么强调都不为过。据我所知，几乎所有平台提供的标准不可变列表都基于这项工作。Bagwell 最初将其设计为可变数据结构，Hickey 则看到了如何将其应用于可行的不可变列表实现。
moomin查看英文原文
The importance of the Phil Bagwell/Rich Hickey* vector can't be understated. AFAIK, pretty much all standard immutable lists provided by platforms use this work. *Bagwell designed the tries as a mutable data structure. Hickey saw how to apply that to a workable immutable list implementation.
关心持久化数据结构相对可变结构的实际性能开销
出于好奇，纯函数式数据结构与经典可变数据结构在真实硬件性能上相比如何？听说它们对函数式纯粹主义者和某些并行编程任务有用，但在其他领域会有显著开销，希望能看到具体证据。
kazagistar查看英文原文
Out of curiosity, how to purely functional data structures compare with classic mutable data structures in terms of real hardware performance? From what I hear, they are useful if you are into functional purity, and sometimes if you are doing certain parallel programming tasks, but suffer significant overhead outside that domain, but I would like to hear of any specific evidence people have in either direction.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选