算法与计算机科学concatenative.org
奇特的数据结构（2011）
Exotic Data Structures (2011)
2012 — 2017，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
concatenative.org 上的一份“冷门数据结构”清单，介绍了哈希数组树、可持久化数组等大多数程序员从未接触过、但在特定场景下非常有用的结构，并附有论文引用。页面文字较为简略，更像一份带参考资料的索引。
为什么经久不衰：它把教科书之外、却真实有用的数据结构集中成一份清单，做性能优化或想拓宽工具箱时依然值得翻阅。
HN 评论精选
掌握标准库之外的数据结构，在性能优化阶段非常有价值
这是一份相当不错的清单，列出了那些确实有用、但大多数程序员似乎从未接触过的数据结构。我经常使用其中一些的变体，也常被没见过它们的程序员问起设计思路。实践中只掌握少数几种数据结构也能应付，但到了性能剖析阶段，标准库之外有备选方案就很有价值——针对特定约束和工作负载，通常存在一个近乎理想的数据结构。而且这些结构里往往埋着值得学习的好点子。以我做高性能 C++ 的经验，第一版常用 STL，一旦开始剖析，STL 往往是最先要替换的东西。
jandrewrogers查看英文原文
This is a pretty good list of data structures that are out there, that are also useful, and to which most programmers never seem to have been introduced. I regularly use variants of some of the data structures listed (plus several that did not make the list) and frequently get questions about the design and structure from programmers that have never seen them. In practice, you can get away with knowing just a handful of data structures and most programmers do. However, when it comes time to profile it is valuable to have alternatives to what the standard libraries and implementations offer. For any given set of constraints on the intended use case and workload for a classic container, there is usually a data structure that is nearly ideal for that use case. Also, there are often neat ideas buried in some of these data structures that are worth learning for their own sake. For the work that I do (high-performance C++) the first pass will often use the C++ STL. When we start profiling, the STL is usually among the first things that need to be replaced. Having a large number of workload optimized data structures in the toolkit for the same abstract container makes this relatively easy.
文中 O(lglgN) 的可持久化数组结论是有前提条件的，需查原文论文
文章不错，虽然有点简略。让我惊讶的是这句：完全可持久化数组可以做到每次更新 O(1) 空间、访问和更新 O(lglgN) 时间。我查了引用的论文，发现这个复杂度是有条件的：仅当算法对数组的访问满足“均匀性”要求时才成立，否则是 O(log n) 均摊时间。所谓均匀性是指任何索引的使用次数不超过平均值的常数倍，堆就是违反该条件的典型例子。
Strilanc查看英文原文
Nice article, although a bit terse. One part that jumped out at me was: > It is possible to implement fully persistent arrays in O(1) space per update, with O(lglgN) time for access and updates [4]. This is surprising because it would guarantee at most a log(log(n)) slowdown for any immutable data structure (instead of the log(n) bound I was aware of). But then I checked out the paper and it turns out that the complexity is conditional: > Fully persistent array use can also be provided at O(1) amortized cost, provided that the algorithm satisfies a simple requirement as to uniformity of access. For those algorithms which do not access the array uniformly or single-threadedly, array reads or updates take at most O(log n) amortized time, where n is the size of the array By uniformity they mean no index is used more than K times the average use-per-index (for some constant K). A simple example of a data structure breaking that condition is a heap. The top element is accessed every query but the bottom elements, that dominate the average, are accessed once per n queries (not a constant).
推荐 Open Data Structures 教材作为该结构的更详细讲解
第一个数据结构 Compact dynamic array，在 Pat Morin 的开源教材《Open Data Structures》里有面向本科生的精彩讲解，书中称之为 rootish array stack。
cdelahousse查看英文原文
The first data structure, the Compact dynamic array, is explained beautifully for an undergraduate audience, in Pat Morin's Open Data Structures open source data structures textbook. He calls them rootish array stacks. http://opendatastructures.org/ods-java/2_6_RootishArrayStack_Space.html
推荐 MIT OCW 高级数据结构课程作为深入学习的资源
MIT OCW 的高级数据结构课程对这些内容讲得非常详细，绝对值得一看。
_asummers查看英文原文
The MIT OCW Advanced Data Structures course goes over these in pretty good detail. Definitely worth a watch.
历次讨论
同类还值得读
位运算技巧集
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编辑精选