转自hecknews: https://news.ycombinator.com/item?id=1370847
为方便点击引文里的链接, 我列出了文字版:
什么是鲜为人知但很酷的数据结构？（stackoverflow.com）
174点的limist 于2010年5月22日|隐藏|过去|网络|喜欢|44条评论
跳过列表和splay树，这个线程上的两个常见建议是“鲜为人知”的原因：跳过列表，因为对于任何给定的跳过列表实现，很可能是平衡二进制树的编码，即使在并发性方面也优于它，并且splay trees因为每个平衡二叉树都优于它们 - 并且，为了避免编写和测试平衡代码，你必须权衡读取树修改数据结构的事实。
朱迪阵列也曾出现过; 这里有一个非常好的Judy数组批评：
http://www.nothings.org/computer/judy/
（长话短说：你可以从简单的哈希表中获得可比性能，而Judy Arrays必须调整到微体系结构）。
这里没有引用喜爱的数据结构：
Aguri树，它将有界大小的基数trie（就像你在软件路由表中使用的那样）与LRU列表结合，并从模式中自动合成聚合（如，来自所有IP的1,000次观察的10.0.0.0/16）插入 它们在流量分析中最为人所知，但我们也在运行时内存分析中使用它们。
对于任何给定的跳过列表实现，很可能是平衡二进制树的编码，其性能优于它
绝对不仅可能。跳过列表可能非常均衡，总是不太平衡，实际上非常平衡。与实际的自平衡树相比，它们唯一的声誉是它们的实施简单。
不是这样！使用跳过列表可以做一件事，我不知道有什么简单的方法可以处理其他数据结构。假设您需要一个优先级队列，并且您拥有一堆核心，并且这些核心希望插入队列并同时删除最小元素。你如何实现这一点，以允许从很多线程快速并发访问？
首先，每个人都会从Intro to Algorithms中记住这种方法：使用二进制最小堆。它保证是平衡的，因此您可以获得O（lg n）时间插入和删除最小操作，具有低常数因子。太好了！但是你如何让它并发？你可以锁定整个事情，只让一个线程一次使用它，但这很慢。您可以使用花哨的细粒度锁定，但仍然存在由维护堆不变量所需的堆化操作引起的线程间内存冲突。已经有一些工作，他们已经提出了一些不错的想法，但它仍然存在扩展问题。
现在看看跳过列表。它是一个随机排序的列表数据结构，它声称，正如你所说，可能非常平衡。各种线程可以同时插入而不会破坏“可能相当平衡”的属性。内存读写集非常本地化，可以通过无锁同步完成所有这些操作。最终结果是优先级队列数据结构，可扩展到数百个核心。并且代码不会炒你的大脑，这是一个加号。这里有一篇非常简洁的论文：
http://www-cs-students.stanford.edu/~itayl/ipdps.pdf
顺便说一句，如果你碰巧使用的是具有硬件事务内存支持的处理器（你还没有），那么这段代码就更容易编写，因为你不必担心如何做无锁同步。我几乎感到被骗多么简单。
总的教训是，随机算法通常不需要在并发进程之间进行同步。例如，从大空间中随机选择id而不是协调选择唯一ID。
您可以访问具有硬件事务内存支持的处理器的工作方式和位置？
只有在模拟中，我才会害怕。据我所知，唯一拥有HTM支持的处理器是Sun的Rock处理器（我认为现在停止使用Oracle）和Azul Systems的Vega芯片。我无法访问其中任何一个，并且它们都没有我正在研究的HTM增强功能。研究领域的技术水平比生产芯片中的安全技术水平要复杂得多。
也就是说，未来的HTM系统具有很大的潜力，我认为我们最终会看到它们得到更广泛的应用。它们的主要问题似乎是现有的软件生态系统并不是用HTM编写的，因此您可以获得病态的内存访问模式，从而降低速度。但是，随着HTM设计的一些小改进（如加载指令立即将其目标地址添加到事务的写集）和编译器和运行时支持，以及一组合理的并发数据结构，HTM绝对可以飞。
你可以找到博客文章和Stack Overflow文章，讨论rb-trees与跳过列表中的锁定开销，只需查看一个图表就可以直观地感知这个想法的来源。但是这些类型的分析通常是因为它们假设树边缘最可能的编码（void * tree * tree *）。
嗯，什么是一些对conncurrency友好的方法来编码树边？
我没有给你一个答案（我只是指出，当人们争论树的效率低下时，他们通常会假设一个带有两个边缘指针的结构），但是对你的问题更直接的回答可能是：
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
（那是一个无锁的红黑树）。
跳过列表的一个有趣应用：http：//www.skorks.com/2010/03/faster-list-intersection-using ...
但我不明白为什么使用树木无法做到这一点。： - /
没有人提到展开的链表，这是一个简单，有用且经常被忽视的数据结构。
http://en.wikipedia.org/wiki/Unrolled_linked_list
这个想法与链表相同，但它不是每个节点中只有一个元素，而是存储整个数组。这个简单的更改解决了链表的两个最大问题 - 内存开销和缓存效率。根据需要调整更像“类似阵列”或更“类似列表”也很容易。
一个有趣的变体就是VList，它的工作方式相同，只是内部数组的大小可变。这为许多操作提供了渐近而不是恒定的加速。
http://en.wikipedia.org/wiki/VList
有一次，Python试图转向类似的标准列表数据结构：
http://www.python.org/dev/peps/pep-3128/
BList类似于B + Tree。它的作用就像是一个小型列表的数组，但更快地进行追加，连接和切片等操作。这是一个非常酷的数组组合（用于内存紧凑性和良好的缓存性能以及小的常量因子）与树，它们可以带来渐近的改进。
可悲的是，它没有起飞，因为它会破坏与扩展模块的向后兼容性。
一些lisp和方案实现也使用了它，部分是由1994年的论文引起的：http：//portal.acm.org/citation.cfm？id = 182453
（不过，如果有任何广泛使用的，目前也不知道。）
是的，展开的喜欢列表通常适用于稀疏的2D数据结构，尤其是当您在小区域周围进行大量聚类时。（想想电子表格）
这不是clojure的作用吗？
IIRC，clojure使用64-ary树，这是一个不同的数据结构，但两者共享'叶子'包含多个对象的属性。例如，展开的链表节点将具有63个对象和指向另一个节点的指针。64-ary树节点将具有64个对象，或指向其他64个节点的指针。一个重要的特性是，因为树中的每个中间节点有64个孩子而不是2个，所以在实践中树的深度非常浅。
但是，clojure可能会将此布局用于数组，而将不同的布局用于列表或其他序列。
我找到了实现细节的链接，你是对的：
HTTP：//blog.higher-order.net/2009/02/01/understanding-clojur ...
哈，我从来不知道有它的名字，谢谢。
ZDDs。ZDD是outdegree 2的DAG，其中每个节点表示一些任意排序的域的一组子集。节点的左子节包含缺少这些子集中最小元素的所有子集; 它的右子包含所有包含最小元素的子集。
这允许对搜索空间的巨大压缩 - 一个例子，Knuth在几周前的一次演讲中给出的一个例子是代表英语中的所有五个字母的单词（表示为{a_1，a_2，...，z_4的子集， z_5}，其中例如：{k_1，n_2，u_3，t_4，h_5}代表“knuth”），并有效地进行查询，例如查找所有单词，当'b'替换为'o'时，产生另一个单词。对我来说更令人印象深刻的是代表所有特定类别的倾斜，只有几十万个节点，当这种倾斜的总数是IIRC时，大约10 ^ 20。
然而，这并不是一件好事。尝试使用ZDD代表所有有效的Sudokus
到目前为止，最酷的数据结构是软堆（http：//www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-he ...）。
来自维基百科：http：//en.wikipedia.org/wiki/Soft_heap
在计算机科学中，由Bernard Chazelle在2000年设计的软堆是简单堆数据结构的变体。通过仔细“破坏”（增加）堆中最多一定固定百分比值的密钥，它能够为其所有五个操作实现分摊的常量时间限制：
偏离主题，但是。这家伙是一个可怕的搞笑和精明的引导。在A Tiny Revolution中查看他的任何帖子http://www.tinyrevolution.com/mt/
谢谢你对这个数据结构ljlolel的提示。
不确定kd树是否鲜为人知，但它们很整洁。我最近才了解到它们，所以对我来说它们“鲜为人知”。
“在计算机科学中，kd树（k维树的简称）是用于组织k维空间中的点的空间划分数据结构.kd-tree是一些有用的数据结构，适用于多个应用，例如涉及的搜索多维搜索关键字（例如范围搜索和最近邻搜索）.kd树是BSP树的特例。“-http://en.wikipedia.org/wiki/Kd-tree
我是第二棵kd-trees。我最近才学会它们，并且最初遇到它们的概念类似于计算机图形中使用的二进制空间分区。可以使用非常简单的二维kd树来实现最近邻搜索。对于找到平面上给定点的n个最近邻点（用于映射应用程序等）非常有用。
没有什么能让我想雇用开发人员，比如阅读算法列表并发现我不理解它们。
你有多少努力去理解它们？和所有事情一样，事情越复杂（或者你所熟悉的东西越远）你就越需要投入其中。
如果您有兴趣了解它们，我建议您寻找其他解释来源，例如维基百科。stackoverflow上的那些可以稍微简短，以获得充分的解释。
此外，通过阅读某些内容，您可以理解的数量是有限的。尝试绘制出来。
最后，我不确定这些东西对你对开发人员的需求有多大了解，这取决于你正在做什么。大多数网络编程都涉及让齿轮与其他齿轮匹配，而不是高级算法。由于某种原因，模糊的数据结构通常是模糊的; 他们更像是一种智力上的好奇心而不是其他任何东西^ - ^。
>由于某种原因，模糊的数据结构通常是模糊的; 他们更像是一种智力上的好奇心而不是其他任何东西^ - ^。
我认为这不一定是真的，问题在于它们有这么多。
考虑木工。一个优秀的木工有一套绝对庞大的工具，所有的木工都会这样做，如果你用非木工的思维方式来思考，就可以从其他木头上取下一些木头，然后再将它们重新组合在一起。
算法是程序员工具箱中的工具，我们所做的就是将一系列位转换为其他位系列。但是，与木工使用的工具数量相比，算法的数量是巨大的，并且不可能记住所有这些工具，选择对手头问题“最合适”的算法。
因此，当一个“模糊”算法更合适时，我们最终可能会使用次优解决方案，因为计算机在很大程度上足够快以覆盖低效率。
为了扩展你的类比，晦涩难懂的算法可能就像让大师们只使用细心的连接和轻木胶制造漂亮，坚固的家具的技术。另一方面，大多数人想要的是从宜家的标准零件快速而廉价地组装的东西。
这是一个很好的方式。
无论如何，工具制作是我所知道的最好的编程形式之一。
如果只是每天编程的编程会更频繁地需要有趣的算法。当然不是网络开发的情况:-(
我日常编程中最实用的鲜为人知的类型是：
-元素树（etrees），partiocularly lxml实现。在xpaths上简单插入和追加操作（例如/ body / html / table / tr[3]/ td[7]），迭代子节点，访问元素属性作为对象属性。
- 依赖图（又名图）。我不知道为什么他们被称为图形（我做生意，而不是CS），但在任何你有依赖存储和锻炼（比如项目管理应用程序或包装工具）这些都是最合适的。
这就是为什么每当我看到我每天都在做系统级C ++应用程序和引导加载程序并且开始变得沮丧时所做的大肆宣传的工作，我只需要考虑它有多么有趣，以及它是如何在精神上刺激的，我脸上露出笑容:)
每个网站背后都有一些新的和令人兴奋的东西，有趣而有趣的构建。前端部分和所有胶水层都没有那么多。
（宠物小便：浏览器不兼容:(）。
早期的HN项目讨论了一个有趣的项目（http://news.ycombinator.com/item?id=1156628）
RodgerTheGreat 于2010年5月23日举行[ - ]
我没有看到任何关于“螺纹树”的提及：http：//en.wikipedia.org/wiki/Threaded_binary_tree
他们在Knuth的“计算机编程艺术”第一卷中详细讨论过。
我很难确定“鲜为人知”的资格，我不确定红黑树是否合格，但它们肯定很酷：
http://en.wikipedia.org/wiki/Red-black_tree
我的印象是大多数平衡的二元树是红黑树。我知道大多数C ++ STL std :: map实现都是红黑树，Java的TreeMap也是如此。
我喜欢放松平衡的红黑树。在那些，你被允许违反平衡条件; 您可以稍后返回并修复违规行为。如果要同时使用它们，这非常有用。平衡转换往往会导致线程之间发生大量争用，因此推迟对以后的清理线程进行重新平衡可以真正帮助实现可伸缩性。
我最近才了解到这一点：
http://www.itl.nist.gov/div897/sqg/dads/
我之前没有意识到这样的事情几乎必须存在，我觉得很愚蠢。
嘿; 它也打击了我。回想起来似乎很明显。我发现这个页面有一个很好的迷你介绍：
http://www.imada.sdu.dk/~kslarsen/RelBal/
如果使用红黑树的请求倾向于突发，那么您可以通过延迟空闲时段的重新平衡来获得加速，甚至是单线程。那太酷了。我希望看到一些编程语言运行时看到rb-tree访问模式，并决定在运行时这是否是一个好主意。
马尔可夫链：http：//www.itl.nist.gov/div897/sqg/dads/HTML/markovchain.htm ...
我发现“计算几何：算法和应用”中的许多数据结构都很有趣
很高兴在那里看到不相交的集合
