州

2018-06-13 23:47:13

你可以告诉关于现代数据结构的什么？我们都知道经典的，比如树木，尝试，堆叠，列表，B树等等（我认为科尔曼的书是“经典之作”的不错列表）。但是最近的研究呢？我至少可以命名其中2个：手指树和judy阵列。我想知道更多。

这真的取决于你对“最近”的定义。 CLRS包含大量的数据结构，但省略了当时开发的许多结构。例如，面向极速存储和整数查找的van Emde Boas树，当时已经开发出来，但在任何地方都没有提及。

很多现代研究都是关于缓存遗忘的数据结构，这些结构在受到某些合理假设的情况下可以充分利用内存层次结构。 Brodal是这个领域的研究人员之一，他创造了许多这样的优秀结构。

纯功能性数据结构可用于功能语言（或用命令式语言来保证持久性）也是一个活跃的研究课题。例如，Chris Okasaki在这个领域的工作导致了新树和优先队列的发展。

现在分布式数据结构非常重要。 Google的BigTable就是一个很好的例子。类似地，并发或无锁数据结构已经进入许多编程语言（例如，参见Java的ConcurrentHashMap或CopyOnWriteArrayList）。

在CLRS中切向提到了基于摊销的数据结构，其重点关注斐波那契堆。然而，同样在同一时间开发的松散树和倾斜堆结构没有被提及，尽管它们今天非常重要。

像跳树和跳跃列表这样的概率结构进行了大量的研究活动，是继续探索的好地方。与此相关，像杜鹃哈希表或动态完美哈希表等强大的哈希表当然值得研究。

过去几年计算几何的数据结构看起来很关注，但遗憾的是我不了解它们，足以说明任何特定的结构。

字符串处理的数据结构，即后缀树，在生物计算和网络搜索中非常相关。我不认为CLRS甚至提到它们的存在。尽管如此，你仍然应该研究它们，因为它们对基因组学中的许多新工作负责。

许多研究人员致力于构建数据结构，以利用现代机器可以并行操作多个位的事实。一些像融合树，指数树或y快树这样的结构利用这些属性来对整数数组进行排序和搜索，这比整个比较模型中强加的O（n lg n）个障碍更快。

对摘要，草图和概要数据结构也进行了大量工作，试图使回答有关数据集的问题成为可能，而不用明确存储整个集合。 Count-Min草图是其中一种数据结构的一个很好的例子。

这只是这里新建的很酷的建筑的一小部分。我希望这是一个很好的起点！

一些相对较新的（如过去30年）数据结构创新一直是概率性的，例如跳过列表。我觉得这些特别有趣，但我没有跟上研究。阅读最近的ACM交易算法可能会帮助您找到一些有趣且前沿的研究。

但是，大多数“新”的东西都是高度专业化的。在很长的一段时间内，只有一次创建了一个新的但基本上重要的算法/结构（如列表，树等）。

有数百个专门的数据结构。 http://en.wikipedia.org/wiki/List_of_data_structures是一个好的开始。

链接地址: http://www.djcxy.com/p/39845.html

上一篇: State