周围有一些数据结构非常有用,但大多数程序员都不知道.他们是哪一个？
每个人都知道链接列表,二叉树和哈希,但是例如跳过列表和布隆过滤器.我想知道更多不常见的数据结构,但值得了解,因为它们依赖于很棒的想法并丰富了程序员的工具箱.
PS:我也对像跳舞链接这样的技巧感兴趣,这些技巧巧妙地使用了常见数据结构的属性.
编辑:请尝试更详细地包含指向描述数据结构的页面的链接.此外,尝试添加几个关于数据结构为什么很酷的词(正如JonasKölker已经指出的那样).此外,尝试为每个答案提供一个数据结构.这将允许更好的数据结构根据他们的投票单独浮动到顶部.
尝试,也称为前缀树或暴击树,已存在超过40年,但仍然相对未知.在" TRASH - 动态LC-trie和散列数据结构 "中描述了一种非常酷的尝试用法,它结合了trie和散列函数.
布隆过滤器:m位的位数组,最初都设置为0.
要添加一个项目,您可以通过k哈希函数运行它,这将在数组中为您提供k个索引,然后将其设置为1.
要检查项目是否在集合中,请计算k个索引并检查它们是否都设置为1.
当然,这给出了一些假阳性的概率(根据维基百科它约为0.61 ^(m/n),其中n是插入项目的数量).假阴性是不可能的.
删除项目是不可能的,但您可以实现计数布隆过滤器,由整数数组和递增/递减表示.
绳索:它是一个字符串,允许廉价的prepends,子串,中间插入和追加.我真的只使用过一次,但没有其他结构就足够了.常规字符串和数组前置对于我们需要做的事情来说太昂贵了,并且逆转翻转是不可能的.
跳过列表非常简洁.
维基百科
跳过列表是一种概率数据结构,基于多个并行排序链表,效率可与二叉搜索树相媲美(大多数操作的订单日志n平均时间).
它们可以用作平衡树的替代品(使用probalistic平衡而不是严格执行平衡).它们易于实施,并且比红黑树更快.我认为他们应该在每个优秀的程序员工具箱中.
如果你想深入介绍跳过列表,可以看一下麻省理工学院"算法导论"讲座的链接.
此外,这是一个Java applet,可以直观地演示Skip Lists.
空间指数,特别是R树和KD树,有效地存储空间数据.它们适用于地理地图坐标数据和VLSI布局布线算法,有时也适用于最近邻搜索.
比特串压缩存储单个位,并允许快速位操作.
拉链 - 数据结构的衍生物,修改结构以具有"光标"的自然概念 - 当前位置.这些非常有用,因为它们可以保证指标不会超出界限 - 例如在 xmonad窗口管理器中用于跟踪哪个窗口已经聚焦.
令人惊讶的是,您可以通过将微积分技术应用于原始数据结构的类型来推导它们!
以下是一些:
后缀尝试.几乎适用于所有类型的字符串搜索(http://en.wikipedia.org/wiki/Suffix_trie#Functionality).另见后缀数组; 它们不如后缀树那么快,但是要小得多.
Splay树(如上所述).他们很酷的原因有三个:
它们很小:你只需要像在任何二叉树中那样使用左右指针(不需要存储节点颜色或大小信息)
它们(相对)非常容易实现
它们为一系列"测量标准"提供了最佳的摊销复杂性(log n查找时间是每个人都知道的).看到http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
堆排序的搜索树:在树中存储一堆(密钥,prio)对,这样它就是关于密钥的搜索树,并且根据优先级进行堆排序.可以证明这样的树具有独特的形状(并且它并不总是完全包装在左上方).通过随机优先级,它可以为您提供预期的O(log n)搜索时间IIRC.
利基1是具有O(1)个邻居查询的无向平面图的邻接列表.这不是一种数据结构,而是组织现有数据结构的特定方式.以下是您的操作方法:每个平面图都有一个度数最多的节点6.选择这样一个节点,将其邻居放在其邻居列表中,将其从图中删除,然后递归直到图为空.当给出一对(u,v)时,在v的邻居列表中查找u,在u的邻居列表中查找v.两者的大小最多为6,因此这是O(1).
通过上面的算法,如果u和v是邻居,你将不会同时拥有v列表中的u和你列表中的v.如果您需要这个,只需将每个节点的缺失邻居添加到该节点的邻居列表,但是存储您需要查看多少邻居列表以进行快速查找.
我认为标准数据结构的无锁替代方案,即无锁队列,堆栈和列表,都被忽视了.
它们越来越相关,因为并发性变得更高优先级,并且比使用互斥锁或锁来处理并发读/写更加令人钦佩.
这里有一些链接
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(通常是挑衅性的)博客有一些关于无锁设计和方法的优秀文章
我认为Disjoint Set非常适合需要将一堆项目划分为不同的集合和查询成员资格的情况.Union和Find操作的良好实现会导致有效的常量摊销成本(如果我正确地回忆起我的数据结构类,则与Ackermnan函数相反).
斐波那契堆积
它们被用于一些最快的已知算法(渐近)用于许多与图形相关的问题,例如最短路径问题.Dijkstra算法在标准二进制堆的O(E log V)时间内运行; 使用Fibonacci堆可以将其提高到O(E + V log V),这对于密集图来说是一个巨大的加速.不幸的是,它们具有很高的常数因子,通常使它们在实践中不切实际.
任何具有3D渲染经验的人都应该熟悉BSP树.通常,这是通过将3D场景结构化为可管理以便知道相机坐标和方位的方法.
二进制空间分区(BSP)是一种通过超平面将空间递归细分为凸集的方法.该细分通过称为BSP树的树数据结构产生场景的表示.
换句话说,它是一种将复杂形状的多边形分解成凸集的方法,或者是完全由非反射角(小于180°的角度)组成的较小多边形.有关空间分区的更一般说明,请参阅空间分区.
最初,这种方法是在3D计算机图形中提出的,以提高渲染效率.一些其他应用包括在CAD中执行具有形状(构造实体几何)的几何操作,在机器人和3D计算机游戏中执行碰撞检测,以及涉及处理复杂空间场景的其他计算机应用.
霍夫曼树 - 用于压缩.
看看Finger Trees,特别是如果你是前面提到的纯功能数据结构的粉丝.它们是持久性序列的功能表示,支持以摊销的恒定时间访问末端,并且在较小的片段的大小中以时间对数进行连接和分割.
根据原始文章:
我们的功能性2-3指树是由Okasaki(1998)引入的一般设计技术的实例,称为隐式递归减速.我们已经注意到这些树是其隐式deque结构的扩展,用2-3个节点替换对,以提供有效连接和分裂所需的灵活性.
手指树可以参数与独异,并使用不同的类群将导致树不同的行为.这使得Finger Trees可以模拟其他数据结构.
循环或环形缓冲区 - 用于流式传输等.
我很惊讶没有人提到Merkle树(即哈希树).
在许多情况下(P2P程序,数字签名)使用,当您只有部分文件可用时,您要验证整个文件的哈希值.
Van Emde-Boas树木
我认为知道为什么它们很酷很有用.一般来说,问题"为什么"是最重要的问题;)
我的答案是他们给你带有{1..n}键的O(log log n)字典,与使用的密钥数量无关.就像重复减半给你O(log n)一样,重复的sqrting给你O(log log n),这就是vEB树中发生的事情.
如何伸展树？
此外,Chris Okasaki的纯功能数据结构浮现在脑海中.
哈希表的一个有趣变体叫做Cuckoo Hashing.它使用多个哈希函数而不是1来处理哈希冲突.通过从主哈希指定的位置删除旧对象,并将其移动到备用哈希函数指定的位置来解决冲突.Cuckoo Hashing允许更有效地使用内存空间,因为只需3个散列函数就可以将负载因子提高到91%,并且仍然具有良好的访问时间.
甲最大-最小堆是一个的变型堆实现双端的优先级队列.它通过对堆属性的简单更改来实现这一点:如果偶数(奇数)级别上的每个元素都小于(大于)所有子级和大型子级,则称树为最小 - 最大级别.级别从1开始编号.
http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg
我喜欢Cache Oblivious数据结构.基本思想是以递归较小的块布置树,以便许多不同大小的缓存将利用方便地适合它们的块.这导致从RAM中的L1高速缓存到从磁盘读取的大块数据的所有内容中有效地使用高速缓存,而无需知道任何这些高速缓存层的大小的细节.
左倾红黑树.Robert Sedgewick于2008年发布了一个非常简化的红黑树实现(大约一半的代码行实现).如果您在实施红黑树时遇到麻烦,请阅读此变体.
与安德森树非常相似(如果不相同).
工作窃取队列
用于在多个线程之间分配工作的无锁数据结构 在C/C++中实现工作窃取队列？
由GerthStøltingBroodal和Chris Okasaki 引导的扭曲二项式堆积:
尽管名称很长,但它们提供了渐近最优的堆操作,即使在函数设置中也是如此.
O(1)大小,联合,插入,最小
O(log n) deleteMin
请注意,与数据结构教科书中常见的堆,例如左派堆不同,联合需要时间O(1)而不是O(log n)时间.与Fibonacci堆不同,这些渐近线是最坏情况,而不是摊销,即使持续使用!
Haskell中有多个 实现.
在布罗达尔提出具有相同渐近线的命令堆之后,它们是由布罗达尔和冈崎共同衍生出来的.
Kd-Trees,在实时光线追踪中使用的空间数据结构(以及其他)具有以下缺点:需要剪切与不同空间交叉的三角形.通常BVH更快,因为它们更轻便.
MX-CIF Quadtrees,通过在四边形边缘组合常规四叉树和二叉树来存储边界框而不是任意点集.
HAMT,分层哈希映射,由于涉及的常量,访问时间通常超过O(1)哈希映射.
倒置索引,在搜索引擎圈中非常有名,因为它用于快速检索与不同搜索词相关联的文档.
大多数(如果不是全部)这些都记录在NIST 算法和数据结构词典中
球树.只是因为他们让人们傻笑.
球树是一种对度量空间中的点进行索引的数据结构. 这是一篇关于构建它们的文章. 它们通常用于寻找点的最近邻居或加速k均值.
不是真正的数据结构; 更多的是优化动态分配数组的方法,但Emacs中使用的间隙缓冲区很酷.
芬威克树.它是一个数据结构,用于在两个给定的子索引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然后教Fenwick树.
Van Emde-Boas树.我甚至有一个C++ 实现,最多2 ^ 20个整数.
嵌套集很适合在关系数据库中表示树并在它们上运行查询.例如,ActiveRecord(Ruby on Rails的默认ORM)带有一个非常简单的嵌套set插件,这使得使用树很简单.
它非常适合特定领域,但是半边数据结构非常简洁.它提供了一种迭代多边形网格(面和边)的方法,这在计算机图形和计算几何中非常有用.
替罪羊树. 普通二叉树的一个典型问题是它们变得不平衡(例如,当按升序插入键时).
平衡二叉树(AKA AVL树)在每次插入后浪费了大量时间.
红黑树保持平衡,但每个节点需要额外的存储空间.
替罪羊树保持平衡,如红黑树,但不需要任何额外的存储.他们通过在每次插入后分析树并进行微调来完成此操作.见http://en.wikipedia.org/wiki/Scapegoat_tree.
一个展开链表是存储在每个节点的多个元素链表上的变化.它可以显着提高缓存性能,同时减少与存储列表元数据(如引用)相关的内存开销.它与B树有关.
record node {
node next // reference to next node in list
int numElements // number of elements in this node, up to maxElements
array elements // an array of numElements elements, with space allocated for maxElements elements
}
2-3指树木通过Hinze和帕特森是一个伟大的功能性数据结构瑞士军刀与多元化的经营具有十分重要的渐近性.虽然复杂,但它们比具有连锁性的持久性列表要简单得多,它们通过Kaplan和Tarjan之前的递归减速来实现.
它们作为可连接的双端队列工作,可以O(1)访问任一端,O(log min(n,m))附加,并提供O(log min(n,length - n))索引,可以直接访问序列任何部分的monoidal前缀和.
实现存在于Haskell,Coq,F#,Scala,Java,C,Clojure,C#和其他语言中.
你可以用它们来实现优先级队列搜索,间隔的地图,绳索快速访问头,地图,集合,catenable序列或者几乎所有您可在此短语作为收集monoidal在快速catenable /可转位序列的结果.
我还有一些描述它们的推导和使用的幻灯片.
配对堆是一种堆数据结构,具有相对简单的实现和出色的实用摊销性能.
一个鲜为人知但非常漂亮的数据结构是Fenwick树(有时也称为二进制索引树或BIT).它存储累积总和并支持O(log(n))操作.虽然累积总和可能听起来不太令人兴奋,但它可以适用于解决需要排序/日志(n)数据结构的许多问题.
IMO,其主要卖点是易于实施.在解决算法问题时非常有用,否则将涉及编码红黑/ avl树.
我真的很喜欢Interval Trees.它们允许您采用一系列间隔(即开始/结束时间或其他)并查询哪些时间间隔包含给定时间,或者在给定时间段内哪些时间间隔为"活动".查询可以在O(log n)中完成,预处理是O(n log n).
XOR链接列表使用两个XOR'd指针来减少双向链表的存储要求.有点晦涩但整洁!
Splash Tables很棒.它们就像一个普通的哈希表,除了它们保证了恒定时间查找,并且可以在不损失性能的情况下处理90%的利用率.它们是Cuckoo Hash(也是一个很棒的数据结构)的概括.他们似乎确实获得了专利,但与大多数纯软件专利一样,我不会太担心.
增强的散列算法非常有趣.线性散列很简洁,因为它允许一次在散列表中拆分一个"桶",而不是重新整理整个表.这对分布式缓存特别有用.但是,通过大多数简单的拆分策略,您最终会快速连续拆分所有存储桶,并且表的负载因子振荡得非常糟糕.
我认为螺旋哈希真的很整洁.与线性散列一样,一次分割一个桶,并将桶中少于一半的记录放入同一个新桶中.它非常干净,快速.但是,如果每个"桶"由具有类似规格的机器托管,则效率可能会很低.要充分利用硬件,您需要混合使用功能更少且功能更强大的机器.
二进制决策图是我最喜欢的数据结构之一,或者实际上是降阶有序二进制决策图(ROBDD).
这些结构可以用于例如:
表示项集并在这些集上执行非常快速的逻辑运算.
任何布尔表达式,旨在查找表达式的所有解法
请注意,许多问题可以表示为布尔表达式.例如,suduku的解决方案可以表示为布尔表达式.为该布尔表达式构建BDD将立即产生解决方案.
地区四叉树
(引自维基百科)
区域四叉树通过将区域分解为四个相等的象限,子等分,等等来表示二维空间的划分,其中每个叶节点包含对应于特定子区域的数据.树中的每个节点都有四个子节点,或者没有子节点(叶子节点).
像这样的四叉树有利于存储空间数据,例如纬度和经度或其他类型的坐标.
这是迄今为止我最喜欢的大学数据结构.编码这个人并看到它的工作非常酷.如果你正在寻找一个需要思考的项目,并且有点偏离常规,我强烈推荐它.无论如何,它比您通常在数据结构类中分配的标准BST衍生物更有趣!
事实上,作为奖励,我在这里找到了讲座的注释(来自弗吉尼亚理工大学)(pdf警告).
我喜欢treaps - 为了平衡它而在叠加搜索树上叠加具有随机优先级的堆结构的简单而有效的想法.
计算未分类的平衡btree.
适合文本编辑缓冲区.
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html
快速紧凑尝试:
Judy数组:用于位,整数和字符串的非常快速且内存有效的有序稀疏动态数组.Judy数组比任何二进制搜索树更快,内存效率更高.
HAT-trie:用于字符串的基于缓存的基于Trie的数据结构
B尝试基于磁盘的字符串管理
我有时使用Inversion LIsts来存储范围,它们通常用于在正则表达式中存储字符类.请参阅http://www.ibm.com/developerworks/linux/library/l-cpinv.html
另一个不错的用例是加权随机决策.假设您有一个符号列表和相关概率,并且您希望根据这些概率随机选择它们
a => 0.1 b => 0.5 c => 0.4
然后你做所有概率的运行总和:
(0.1, 0.6, 1.0)
这是你的反演名单.您生成一个介于0和1之间的随机数,并在列表中查找下一个更高条目的索引.您可以使用二进制搜索来执行此操作,因为它已经过排序.获得索引后,您可以在原始列表中查找符号.
如果你有n符号,你有O(n)准备时间,然后O(log(n))每个随机选择的符号的访问时间 - 独立于权重的分布.
反演列表的变体使用负数来指示范围的端点,这使得可以容易地计算在某个点处重叠的范围.有关示例,请参见http://www.perlmonks.org/index.pl?node_id=841368.
Arne Andersson树是红黑树的简单替代品,其中只有正确的链接可以是红色.这大大简化了维护,同时保持性能与红黑树相当.原始论文为插入和删除提供了一个很好的简短实现.
DAWG是一种特殊的Trie,类似的子树被压缩成单亲.我扩展了修改后的DAWG,并提出了一个名为ASSDAWG(Anagram Search Sorted DAWG)的漂亮数据结构.这种方式的工作方式是每当一个字符串被插入DAWG时,它首先进行桶式排序然后插入,叶子节点还有一个额外的数字,表明如果我们从root到达那个叶节点,哪些排列是有效的.这有两个很好的优点:
由于我插入前的字符串进行排序,自DAWGs自然崩溃类似的子树,我得到压缩的高级别(例如,"吃","吃","茶"都变成指示1路的叶节点与数字列表AET哪种aet排列有效).
现在,搜索给定字符串的字谜非常快且微不足道,因为从根到叶的路径使用置换数保存叶节点处该路径的所有有效字谜.
我喜欢后缀树和用于字符串处理的数组,跳过平衡列表的列表和用于自动平衡树的splay树
看看Donald Knuth提出的侧身堆.
http://stanford-online.stanford.edu/seminars/knuth/071203-knuth-300.asx
BK-Trees或Burkhard-Keller树是基于树的数据结构,可用于快速查找字符串的近匹配.
Fenwick树(或二进制索引树)是一个值得添加的工具包.如果你有一个计数器阵列,你需要在查询累积计数时不断更新它们(如在PPM压缩中),Fenwick树将在O(log n)时间内完成所有操作,并且不需要额外的空间.另请参阅此topcoder教程以获得详细介绍.
Zobrist Hashing是一种哈希函数,通常用于表示游戏板位置(如国际象棋),但肯定还有其他用途.关于它的一个好处是可以随着电路板的更新而逐步更新.
京公网安备 11010802040832号 | 京ICP备19059560号-6 