logo标签列表

最先进的数据结构

data-structures
35

现代数据结构有什么值得一提的呢？我们都知道传统的数据结构，比如树、trie、栈、链表、B 树等等（我认为 Cormen 的书是“经典结构”的一个不错列表）。但是最近有哪些研究呢？我至少可以提到两个：finger trees（指尖树） 和 judy 数组。我想了解更多。

14
这就像询问一个现代版的轮子，但不要那个无聊的圆形。 - Cosmin
2
你可能会在这些SO问题中找到一些有趣的材料，涉及高级、复杂和酷炫的数据结构。 - WReach
@Cosmin，Pugh的跳表是1989年的，我认为它相当现代。 - bestsss
1
投票关闭并移动到程序员板块。 - user7116
1
@sixlettervariables：为什么要转到程序员？这有什么真正主观的东西吗？如果那里是一个真正的问题，那么这里也是一个真正的问题。 - David Thornley
显示剩余6条评论
4个回答
19
这真的取决于你对“最近”的定义。CLRS包含大量数据结构，但由于其本质，无法涵盖多年来已经开发的所有伟大思想和技术。以下是一些研究领域的示例以及从中得出的结果：
二叉搜索树
在“经典”方面，最近开发的WAVL树是一种简单的平衡树结构，在仅插入情况下表现得像AVL树（紧密平衡），并且在插入和删除交替进行时永远不会比红黑树差。还有zip tree，它是将概率跳表编码为二叉搜索树的一种方法，并具有非常简单的规则。 Splay树是第一种通过重新排列节点在查找期间实现优异性能的二叉搜索树。它们具有许多出色的理论特性。虽然它们在某种意义上不算“现代”，因为它们最初是在20世纪80年代开发的，但它们开创了一个新的研究领域：寻找一种单一的二叉搜索树，在某种意义上，它是“最好的”二叉搜索树。这样的树理想情况下应该给出O(log n)的查找时间，但也应该具有其他令人满意的属性，如“查找最近搜索过的项目所需的时间更少”和“查找靠近最近查询项目的项目应该很快”。在21世纪初，我们看到了tango树和multisplay树的发展，它们具有不同寻常的保证：执行这些树上的一系列操作的成本永远不会比执行任何二叉搜索树上的这些操作慢O(log log n)倍。
在2010年代早期，研究人员发现了二叉搜索树算法与2D平面点集之间的联系。这种“二叉搜索树的几何结构”已被用于发现BST结构的新下限，并产生了一种新的BST候选项，该候选项在某种定义下“尽可能好”。
其他要查看的平衡树和类似树的结构包括跳表、treap和在1990年代开发的牺牲树。

素描和抽样

许多最近的数据结构都被设计用于处理数据流，其中每个元素只能一次看到。目标是在使用比存储所有元素所需空间低得多的情况下计算有关数据流的统计信息。（想想谷歌跟踪热门搜索查询或Twitter寻找趋势标签-有太多东西同时出现，无法实时跟踪所有发布的内容）。计数最小化草图使得可以估计数据流中各种项目已经被看到的频率，并可用于查找在流中频繁出现的项目。 HyperLogLog 估计器 仅使用很少量的空间，可以估计已经看到了多少不同的项目。像 AMS 估计器这样的估计器可用于近似估计数据分布的偏斜程度。

内存优化结构

已经进行了许多关于缓存遗忘数据结构的研究。缓存遗忘结构背后的思想是计算机中的内存通常涉及多层缓存，并且根据这些缓存的大小调整数据结构已被知道可以提供性能提升（例如，请参见 B-tree）。在缓存遗忘模型中，数据结构需要充分利用缓存，但是不知道缓存大小。令人惊讶的是，这是可能的，我们有二叉搜索树和优先队列来满足这个目标。

哈希表

Cuckoo哈希是在20世纪初开发的一种构建哈希表的方法，其中查找时间最坏情况下为O（1）。它们在实践中速度很快，并且它们的分析导致了对随机超图属性的研究。
自20世纪60年代以来已知的线性探测法假定使用随机哈希函数可以表现良好，但在理论意义上需要5个独立哈希函数才能快速执行。
在2010年代，一些Google工程师开发了“Swiss Table”，这是一种基于线性探测的极快哈希表，利用SIMD指令获得额外的性能提升。
布隆过滤器自20世纪70年代以来就存在，并提供了一种在小空间中存储集合的优秀方法，前提是允许误判。在2000年代、2010年代和2020年代，许多实用的数据结构被开发出来，从实践中改进了它。d-left counting Bloom filter支持插入和删除，空间降低约2倍。更近期的cuckoo filter比传统的Bloom过滤器使用更少的空间（对于合理的错误率），并支持插入和删除。XOR filter在所有情况下都比Bloom过滤器使用更少的空间，假设要存储的项事先已知。
XOR过滤器与Bloomier过滤器相关，是一种存储字典近似值的方法，类似于Bloom过滤器存储集合的近似值。它们被用于一篇晚期2010年代的论文中，用于压缩具有低误差率的机器学习模型。
还开发了几种纯理论兴趣的数据结构，这些数据结构显示可以实现Bloom过滤器替换的理论最优位数。Porat的矩阵过滤器可能是最简单的，而Pagh、Pagh和Rao的方法是第一个这样做的（如果我没记错的话）。
紧凑数据结构需要多少位来编码数据结构？这个问题引起了紧凑数据结构领域的出现。可以使用接近信息论最小位数来编码树等复杂结构。以Wavelet树为例。还有关于构建数据结构的工作，这些数据结构使用数据压缩来减小结构的大小，同时保持结构的有用性。FM-index是一个很好的例子。
持久数据结构是一种数据结构，其中执行编辑会产生两个结果版本-应用编辑之前和之后各一个版本。这是由Sarnak和Tarjan在1980年代首次探索，导致2D点位置的改进。
纯函数数据结构是其中的一种子情况，可以在函数语言中使用（或在命令式语言中保证持久性）。例如，Chris Okasaki在这个领域的工作已经导致了新树和优先队列的发展。
动态数据结构。
动态数据结构是存储移动对象的数据结构。这使得操作如“给定一组运动粒子，哪对粒子将是下一个碰撞？”成为可能，并在计算机图形学中找到了应用。搜索“动态优先队列”以获得良好的介绍。
并发数据结构是在多线程环境中很好地工作的数据结构。有巧妙的方法可以构建哈希表和优先队列，可以同时处理多个读者和多个写者而不锁定整个结构，其中许多已被Java标准库采用，其他可以用于并发密集型工作流程。
用于在二维、三维和更高维空间中处理点的数据结构在计算机图形学和数据处理中都有应用。这里有很大的空间需要涵盖；以下是一些亮点。
用于点定位问题的数据结构维护将2D平面划分为区域并支持查询“给定一个点，它在哪个空间区域内？”的形式。有许多解决此问题的方法。有些使用永久性数据结构。其他基于将三角网格细化为网格层次结构。其他通过将世界分割成梯形来工作。
正交范围搜索问题要求存储一组点的数据结构，并回答“这个轴对齐框中的所有点是什么？”的查询。范围树和k-d树在1970年代开发并仍然有用。更现代的方法，继续在2020年代开发，使用分数级联和整数数据结构的混合来在理论上改善这些运行时间。

字符串数据结构

用于字符串处理的数据结构，如后缀树，在生物计算和网络搜索中非常重要。我认为CLRS甚至没有提到它们的存在。但你绝对应该研究它们，因为它们负责了基因组学中许多新工作。后缀数组构造算法方面最近有一些非常酷的进展，例如SA-IS算法弥合了理论上和实际上快速算法之间的差距。

整数数据结构

许多研究人员致力于构建数据结构，利用现代机器可以并行操作多个位的事实。一些结构，如融合树、指数树或y-fast树，利用这些特性在整数数组中进行排序和搜索，比天真的比较模型中的O(n lg n)障碍更快。 融合树 及其后代（指数树等）表明，通过字级并行性，你可以获得一些相当令人印象深刻的理论加速，尽管这些结构在实践中不是非常快。

整数数据结构还被用于给出单源最短路径问题的O(m + n)时间算法，从理论上讲严格优于Dijkstra算法，假设权重为整数。然而，该算法基本上只是理论上的兴趣，因为在实现中使用的常数因子太高，无法实用。

优先队列

斐波那契堆是第一个支持在（摊）时间 O(1) 内进行 enqueue、meld 和 decrease-key 操作，且 extract-min 操作的（摊）时间为 O(log n) 的优先队列，改进了 Dijkstra 算法、Prim 算法以及 Stoer-Wagner 最小割算法的性能。此后，许多其他优先队列已被开发出来，以简化 Fibonacci 堆或满足最坏情况下的这些时间上界。Quake 堆是一个更简单的结构（从概念上讲），但在实践中运行速度不够快。严格的 Fibonacci 堆以最坏情况的意义实现了与 Fibonacci 堆相同的时间上界。

基于伸展树的配对堆在实践中比 Fibonacci 堆快得多。它最初被推测可以满足与 Fibonacci 堆相同的时间上界，但在它们开发多年之后证明不是这样。截至2021年，配对堆的实际运行时间尚未确定。

动态图

许多经典的图问题（“给定两个节点，它们之间是否存在路径？”“找到一个最小生成树。”“检查图是否是平面图”）都有已知的快速算法。但如果允许图随时间改变会发生什么？这些问题突然变得很难在每次编辑时高效地重新计算而不从头开始。

在底层图是森林的情况下，欧拉遍历树、s-t 树（有时称为链接/剪切树）和 top tree 使得能够以非常低的更新时间每次编辑回答许多有趣的问题，如连通性。

对于一般图，Holm等人的分层森林结构可以在添加或删除边缘时保持图的连通性和MST，并具有相当好的摊销运行时间。Kapron等人的切割结构使用随机化以良好的最坏效率和高成功概率执行更新。

区间最小值查询

区间最小值查询问题是预处理值数组，以便快速回答“子数组中最小的条目是什么？”的查询。在20世纪80年代，找到了一种解决方案，它使用线性预处理时间和O（1）查询时间，并且这个解决方案已经被简化和改进多年，现在在实践中非常快（搜索“Fischer-Heun结构”）。

RMQ有很多意想不到的应用，特别是与树结合使用（其中它可用于快速查找最低公共祖先），特别是后缀树和后缀数组（其中它驱动许多令人印象深刻的算法）。

既不是CopyOnWriteArrayList，也不是ConcurrentHashMap是无锁结构。ConcurrentHashMap使用剥离锁（但在Object.equals()的虚拟调用期间可能会显著减慢），而CopyOnWriteArrayList在修改时使用单个锁。 - bestsss
@bestsss - 确实，我在描述这些结构时是想说“并发结构”而不是“无锁结构”。那句话是我表述不清楚了。 - templatetypedef
CopyOnWriteArrayList 在存在写入操作时性能表现很差，而 ConcurrentHashMap 在真正的多核（128+）系统上也不太好（加上缓存语义较差）。 - bestsss
5
一些相对较新（最近30年）的数据结构创新是概率性的，例如跳表。我觉得这些特别有趣，但我不关注研究。阅读最近的ACM算法事务可能会帮助您找到一些有趣和前沿的研究。
但是，大多数“新”的东西都将是高度专业化的。只有在非常长的时间内才会创建一个新的但基本重要的算法/结构（如列表、树等）。
1
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接