language-agnostic structure有哪些 - 什么是较少知道但有用的数据结构?




data (25)

Van Emde-Boas树 。 我甚至有一个C ++ implementation它,最多2 ^ 20个整数。

有一些数据结构是非常有用的,但大多数程序员都不知道。 他们是哪一个?

每个人都知道链表,二叉树和散列,但跳过列表布卢姆过滤器例如。 我想知道更多不太常见的数据结构,但值得了解,因为它们依靠伟大的想法并丰富了程序员的工具箱。

PS:我对像跳舞链接这样的技术也很感兴趣,这些技术巧妙地使用了通用数据结构的属性。

编辑 :请尝试将链接包含到更详细描述数据结构的页面中。 另外,为了说明为什么数据结构很酷,尝试添加几句话(正如JonasKölker已经指出的那样)。 另外,尝试为每个答案提供一个数据结构 。 这将允许更好的数据结构根据他们的投票单独浮到顶部。



斐波那契堆

它们用于一些已知最快的算法(渐近地)用于很多图形相关的问题,例如最短路径问题。 Dijkstra算法运行在标准二进制堆的O(E log V)时间内; 使用斐波纳契堆将其提高到O(E + V log V),这对于密集图是一个巨大的加速。 但不幸的是,它们具有很高的不变因素,常常使它们在实践中不切实际。


这里有几个:

  • 后缀尝试。 几乎适用于所有类型的字符串搜索( )。 另见后缀数组; 它们并不像后缀树那么快,但总体来说小得多。

  • 展开树木(如上所述)。 他们很酷的原因有三个:

    • 它们很小:您只需要像在任何二叉树中一样使用左指针和右指针(不需要存储节点颜色或大小信息)
    • 它们(相对)很容易实现
    • 它们为大量“测量标准”提供了最佳的分期复杂性(日志查找时间是大家都知道的)。 请参阅
  • 堆排序搜索树:您将一堆(键,prio)对存储在一棵树中,这样它就是一个关于键的搜索树,并且针对优先级按堆排序。 人们可以证明这样一棵树具有独特的形状(并且它并不总是完全打包到左边)。 随机优先,它给你预期的O(log n)搜索时间,IIRC。

  • 一个小生境是具有O(1)邻居查询的无向平面图的邻接列表。 这不是一种数据结构,而是一种组织现有数据结构的特殊方式。 以下是你如何做的:每个平面图都有一个节点,其中最多有6个节点。选择这样一个节点,将它的邻居放置在它的邻居列表中,从图中移除它,并递归到图表为空。 当给定一对(u,v)时,在v的邻居列表中查找u,并在u的邻居列表中查找v。 两者的大小至多为6,所以这是O(1)。

通过上面的算法,如果u和v是邻居,你不会同时拥有v的列表和v的列表。 如果你需要这个,只需将每个节点的缺失邻居添加到该节点的邻居列表中,但是需要存储多少邻居列表才能快速查找。


我认为不相交集对于需要将一堆项目分成不同集合和查询成员资格的情况非常好。 Union和Find操作的良好实现会导致实际上不变的摊销成本(如果我正确地记得我的数据结构类,则可以使用Ackermnan函数的反函数)。


我认为标准数据结构(如无锁队列,堆栈和列表)的无锁选择被忽略。
它们越来越相关,因为并发性成为更高的优先级,并且比使用Mutex或锁来处理并发读/写更令人钦佩。

这里有一些链接
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [链接到PDF]
http://www.boyet.com/Articles/LockfreeStack.html

Mike Acton的 (经常是挑衅性的)博客有一些关于无锁设计和方法的优秀文章



左倾斜的红黑树 。 Robert Sedgewick在2008年发布了一个显着简化的红黑树实现(实现代码行的一半)。 如果您在实施红黑树时遇到困难,请阅读有关此变种的信息。

与Andersson树非常相似(如果不相同)。


空间索引 ,特别是R-treesKD-trees ,可以有效地存储空间数据。 它们适用于地理地图坐标数据和VLSI布局和布线算法,有时适用于最近邻搜索。

位阵列紧凑地存储各个位,并允许快速位操作。


具有3D渲染经验的任何人都应该熟悉BSP树 。 一般来说,这是一种通过构建3D场景以便知道相机坐标和方位进行渲染的方法。

二进制空间分区(BSP)是一种用超平面递归地将空间细分为凸集的方法。 该细分通过称为BSP树的树数据结构产生场景的表示。

换句话说,它是一种将复杂形状的多边形分解为凸集或者更小的多边形完全由非反射角组成的角度(角度小于180°)的方法。 有关空间分区的更一般描述,请参阅空间分区。

最初,这种方法是在3D计算机图形中提出的,以提高渲染效率。 其他一些应用包括用CAD中的形状(建设性立体几何),机器人和3D电脑游戏中的碰撞检测以及涉及处理复杂空间场景的其他计算机应用来执行几何操作。


Zippers - 数据结构的衍生物,修改结构以具有“游标”的自然概念 - 当前位置。 这些功能非常有用,因为它们可以保证指示不会超出限制 - 例如在xmonad窗口管理器中用于跟踪哪个窗口已关注。

令人惊讶的是,您可以通过将微积分技术应用于原始数据结构的类型来派生它们!


Fenwick树。 这是一个数据结构,用于保持向量中所有元素的总和,并在两个给定的子索引i和j之间进行计数。 这个简单的解决方案,预先计算自开始以来的总和不允许更新一个项目(你必须做O(n)的工作跟上)。

Fenwick Trees允许你在O(log n)中更新和查询,它的工作原理非常酷且简单。 在Fenwick的原始论文中可以很好地解释它,可以在这里免费获得:

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

它的父亲RQM树也非常酷:它允许你保存有关向量两个索引之间的最小元素的信息,它也可以用于O(log n)更新和查询。 我喜欢先教RQM,然后再教芬威克树。




嵌套集很适合在关系数据库中表示树并在其上运行查询。 例如,ActiveRecord(Ruby on Rails的默认ORM)带有一个非常简单的嵌套set插件 ,这使得树木工作变得微不足道。


布隆过滤器m位的位数组,最初全部设置为0。

要添加一个项目,您可以通过k散列函数运行它,该函数将为您提供数组中的k个索引,然后将其设置为1。

要检查项目是否在集合中,计算k个索引并检查它们是否都设置为1。

当然,这给出了一些错误肯定的概率(根据维基百科它约为0.61 ^(m / n),其中n是插入项目的数量)。 假阴性是不可能的。

删除项目是不可能的,但是您可以实现计数布隆过滤器 ,由整数和增量/减量表示。



跳过列表非常整洁。

维基百科
跳过列表是基于多个并行排序链接列表的概率数据结构,其效率与二叉搜索树(大多数操作的平均时间顺序记录)相当。

它们可以用作平衡树木的替代品(使用平衡性而不是严格的平衡)。 它们很容易实施,而且比红黑树更快。 我认为他们应该是每一位优秀的程序员工具。

如果您想深入介绍跳过列表,可以链接到 MIT关于算法介绍的视频演讲。

另外, here有一个Java applet以可视方式展示Skip List。


  • 在实时光线追踪中使用的KD-trees (空间数据结构等)有缺点,即不同空间交叉相交的三角形需要裁剪。 通常BVH的速度更快,因为它们更轻量。
  • MX-CIF四叉树通过将常规四叉树与四边形边上的二叉树相结合来存储边界框而不是任意点集。
  • HAMT ,层次哈希映射的访问时间通常超过O(1)哈希映射,由于涉及的常量。
  • 倒排索引在搜索引擎圈中非常有名,因为它用于快速检索与不同搜索条件相关的文档。

大多数(如果不是全部的话)都记录在NIST 算法和数据结构字典中


我喜欢Cache不重要的数据结构 。 其基本思想是以递归较小的块布局树,以便许多不同大小的缓存将利用方便适合它们的块。 这导致从RAM中的L1高速缓存到从磁盘读取的大块数据的高速缓存有效使用,而无需知道任何这些高速缓存层的大小的具体细节。


哈希表的一个有趣的变体称为布谷鸟哈希 。 它使用多个散列函数而不是1个来处理散列冲突。 通过从主散列指定的位置移除旧对象并将其移动到由交替散列函数指定的位置来解决冲突。 布谷鸟哈希允许更有效地利用内存空间,因为只有3个哈希函数可以将您的加载因子提高到91%,并且仍然具有良好的访问时间。


Van Emde-Boas树

我认为了解他们为什么很酷很有用。 一般来说,“为什么”这个问题是最重要的问题;)

我的答案是,他们给你带{1..n}个键的O(log log n)个字典,而不管有多少个键在使用中。 就像重复减半给你O(log n)一样,重复的sqrting给你O(log log n),这就是vEB树中发生的情况。


Rope :这是一个字符串,允许便宜的prepends,子字符串,中间插入和附加。 我真的只用过它一次,但没有其他结构可以满足。 对于我们需要做的事情来说,规则的字符串和数组的前置代码太昂贵了,而扭转事务是不可能的。


它非常适合特定领域,但是半边数据结构非常整齐。 它提供了一种迭代多边形网格(面边)的方法,这在计算机图形和计算几何中非常有用。






language-agnostic data-structures computer-science