794

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

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

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

编辑:请尝试包含指向更详细描述数据结构的页面的链接。另外,尝试添加一些关于为什么数据结构很酷的词(正如Jonas Kölker已经指出的那样)。此外,尝试为每个 answer 提供一个数据结构。这将允许更好的数据结构仅根据他们的投票浮动到顶部。

4

83 回答 83

270

尝试,也称为前缀树或暴击位树,已经存在了 40 多年,但仍然相对不为人知。“ TRASH - A dynamic LC-trie and hash data structure ”中描述了一个非常酷的 Trie 用法,它结合了 trie 和哈希函数。

于 2009-02-01T11:24:12.337 回答
231

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

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

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

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

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

于 2009-02-01T19:11:07.590 回答
139

Rope:这是一个允许廉价前置、子串、中间插入和附加的字符串。我真的只用过一次,但没有其他结构就足够了。常规的字符串和数组前置对于我们需要做的事情来说太昂贵了,而且扭转一切都是不可能的。

于 2009-02-18T20:01:37.797 回答
127

跳过列表非常整洁。

Wikipedia
跳过列表是一种概率数据结构,基于多个并行的排序链表,其效率可与二叉搜索树媲美(大多数操作的平均时间为 log n)。

它们可以用作平衡树的替代品(使用概率平衡而不是严格执行平衡)。它们比红黑树更容易实现且速度更快。我认为它们应该是每个优秀程序员的工具箱。

如果您想深入了解跳过列表,请点击此处链接到麻省理工学院关于它们的算法简介讲座的视频。

此外,这里是一个 Java 小程序,直观地演示了跳过列表。

于 2009-02-18T19:53:04.243 回答
91

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

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

于 2009-02-01T12:23:44.340 回答
86

拉链- 修改结构以具有“光标”的自然概念的数据结构的衍生物 - 当前位置。这些非常有用,因为它们保证索引不会越界——例如在xmonad 窗口管理器中用于跟踪哪个窗口已聚焦。

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

于 2010-05-22T23:02:18.040 回答
69

这里有几个:

  • 后缀尝试。适用于几乎所有类型的字符串搜索(http://en.wikipedia.org/wiki/Suffix_trie#Functionality)。另见后缀数组;它们不如后缀树快,但要小得多。

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

    • 它们很小:您只需要像在任何二叉树中一样的左右指针(不需要存储节点颜色或大小信息)
    • 它们(相对)很容易实现
    • 它们为一大堆“测量标准”(每个人都知道的 log n 查找时间)提供了最佳的摊销复杂性。看http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
  • 堆排序的搜索树:您将一堆(键,优先级)对存储在树中,这样它是关于键的搜索树,并且相对于优先级是堆排序的。可以证明这样一棵树有一个独特的形状(而且它并不总是完全挤在左边)。使用随机优先级,它可以为您提供预期的 O(log n) 搜索时间 IIRC。

  • 一个利基是具有 O(1) 邻居查询的无向平面图的邻接表。这与其说是一种数据结构,不如说是一种组织现有数据结构的特定方式。这样做的方法如下:每个平面图都有一个度数最多为 6 的节点。选择这样一个节点,将其邻居放入其邻居列表中,将其从图中删除,然后递归直到图为空。当给定一对 (u, v) 时,在 v 的邻居列表中查找 u,并在 u 的邻居列表中查找 v。两者的大小最多为 6,所以这是 O(1)。

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

于 2009-02-01T12:12:30.023 回答
65

我认为标准数据结构(即无锁队列、堆栈和列表)的无锁替代方案被忽视了。
它们变得越来越重要,因为并发性变得更高优先级,并且比使用互斥锁或锁来处理并发读/写更令人钦佩。

这里有一些链接
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 的(通常是挑衅性的)博客有一些关于无锁设计和方法的优秀文章

于 2009-12-14T23:16:09.890 回答
55

我认为Disjoint Set非常适合需要将一堆项目划分为不同的集合和查询成员资格的情况。Union 和 Find 操作的良好实现导致摊销成本实际上是恒定的(如果我正确回忆我的数据结构类,则与 Ackermnan 的函数相反)。

于 2009-02-18T20:17:50.940 回答
52

斐波那契堆

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

于 2009-06-17T21:38:51.243 回答
44

任何有 3D 渲染经验的人都应该熟悉BSP 树。通常,这是通过构建 3D 场景以便在知道相机坐标和方位的情况下进行渲染的方法。

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

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

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

于 2009-02-18T20:26:32.930 回答
43

霍夫曼树- 用于压缩。

于 2009-02-22T04:47:47.383 回答
38

看看Finger Trees,特别是如果您是前面提到的纯函数数据结构的粉丝。它们是持久序列的功能表示,支持在摊销的常数时间内访问末端,以及在较小部分的大小上按时间对数连接和拆分。

根据原始文章

我们的功能 2-3 指树是 Okasaki (1998) 引入的通用设计技术的一个实例,称为隐式递归减速。我们已经注意到,这些树是他的隐式双端队列结构的扩展,用 2-3 个节点替换对,以提供有效连接和拆分所需的灵活性。

手指树可以用monoid参数化,使用不同的 monoid 会导致树的不同行为。这让手指树可以模拟其他数据结构。

于 2010-01-29T11:54:18.427 回答
34

圆形或环形缓冲区- 用于流式传输等。

于 2009-03-17T18:30:42.547 回答
33

我很惊讶没有人提到默克尔树(即哈希树)。

在许多情况下使用(P2P 程序、数字签名),当您只有部分文件可供您使用时,您想要验证整个文件的哈希值。

于 2010-01-28T20:03:29.923 回答
32

<zvrba> Van Emde-Boas 树

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

我的回答是,他们给你 O(log log n) 个带有 {1..n} 键的字典,与正在使用的键的数量无关。就像重复减半给你 O(log n) 一样,重复 sqrting 给你 O(log log n),这就是 vEB 树中发生的情况。

于 2009-02-01T13:27:26.473 回答
31

散开树怎么样?

此外,我想到了Chris Okasaki 的纯函数式数据结构。

于 2009-02-01T11:27:36.340 回答
29

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

于 2009-05-10T21:56:05.177 回答
27

最小-最大堆是实现双端优先级队列的的变体。它通过对堆属性的简单更改来实现这一点:如果偶数(奇数)级别上的每个元素都小于(大于)所有子节点和孙子节点,则称树是最小最大排序的。级别从 1 开始编号。

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

于 2011-01-15T12:18:07.633 回答
26

我喜欢Cache Oblivious 数据结构。基本思想是在递归较小的块中布置树,以便许多不同大小的缓存将利用方便放入它们的块。这导致在从 RAM 中的 L1 缓存到从磁盘读取的大块数据的所有内容中有效地使用缓存,而无需知道任何这些缓存层大小的细节。

于 2011-03-24T22:20:26.243 回答
23

左倾红黑树。Robert Sedgewick 于 2008 年发布的一个显着简化的红黑树实现(大约需要实现的代码行数的一半)。如果您在思考红黑树的实现时遇到过麻烦,请阅读此变体。

与安德森树非常相似(如果不相同)。

于 2010-05-23T17:21:19.120 回答
22

工作窃取队列

用于在多个线程之间平均分配工作的无锁数据结构 在 C/C++ 中实现工作窃取队列?

于 2010-09-19T17:54:55.883 回答
19

Gerth Stølting Brodal 和 Chris Okasaki 的自举倾斜二项式堆

尽管它们的名字很长,但它们提供了渐近优化的堆操作,即使在函数设置中也是如此。

  • O(1)大小,联合,插入,最小
  • O(log n)删除最小值

请注意,与数据结构教科书中通常介绍的更知名的堆(例如左派堆O(1))不同,联合需要而不是时间。与Fibonacci heaps不同,这些渐近线是最坏的情况,而不是摊销,即使持续使用!O(log n)

Haskell中有多种 实现

它们是 Brodal 和 Okasaki 在 Brodal 提出具有相同渐近线的命令堆之后共同推导出的。

于 2010-07-23T06:15:19.053 回答
18
  • Kd-Trees是实时光线追踪中使用的空间数据结构(除其他外),它的缺点是需要裁剪与不同空间相交的三角形。通常 BVH 更快,因为它们更轻量级。
  • MX-CIF Quadtrees,通过将常规四叉树与四边形边缘上的二叉树组合来存储边界框而不是任意点集。
  • HAMT,分层哈希映射,由于涉及的常量,访问时间通常超过 O(1) 哈希映射。
  • 倒排索引,在搜索引擎圈子里非常有名,因为它用于快速检索与不同搜索词相关的文档。

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

于 2009-02-01T13:29:08.293 回答
18

球树。只是因为他们让人们咯咯笑。

球树是一种对度量空间中的点进行索引的数据结构。 这是一篇关于构建它们的文章。 它们通常用于寻找一个点的最近邻居或加速 k-means。

于 2010-07-23T00:04:15.530 回答
17

不是真正的数据结构;更多的是一种优化动态分配数组的方法,但是 Emacs 中使用的间隙缓冲区有点酷。

于 2010-05-23T21:52:47.873 回答
16

芬威克树。它是一种数据结构,用于在两个给定的子索引 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 Tree。

于 2010-07-23T03:45:43.407 回答
14

Van Emde-Boas 树。我什至有它的 C++实现,最多 2^20 个整数。

于 2009-02-01T13:06:37.653 回答
13

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

于 2010-05-22T23:56:40.513 回答
12

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

于 2010-05-23T07:31:25.773 回答
12

替罪羊树。 普通二叉树的一个典型问题是它们变得不平衡(例如,当键以升序插入时。)

平衡二叉树(AKA AVL 树)在每次插入后都会浪费大量时间进行平衡。

红黑树保持平衡,但每个节点都需要额外的存储空间。

替罪羊树像红黑树一样保持平衡,但不需要任何额外的存储空间。他们通过在每次插入后分析树并进行细微调整来做到这一点。请参阅http://en.wikipedia.org/wiki/Scapegoat_tree

于 2010-05-24T14:07:11.710 回答
12

展开的链表是链表的一种变体,它在每个节点中存储多个元素。它可以显着提高缓存性能,同时减少与存储列表元数据(如引用)相关的内存开销。它与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
}
于 2011-01-15T12:12:08.020 回答
11

Hinze 和 Paterson的2-3 Finger Trees是一种出色的函数式数据结构瑞士军刀,具有出色的渐近性,适用于各种操作。虽然很复杂,但它们比 Persistent 列表的命令式结构要简单得多,通过在它们之前的 Kaplan 和 Tarjan 的递归减速进行连接。

它们作为可连接双端队列工作,可以O(1)访问任一端、O(log min(n,m))追加,并提供O(log min(n,length - n))索引,可以直接访问序列任何部分的单端前缀和。

HaskellCoqF#ScalaJavaCClojureC#和其他语言都有实现。

您可以使用它们来实现优先级搜索队列区间映射具有快速头部访问的绳索、映射、集合、可连接序列或几乎任何您可以将其表述为在快速可连接/可索引序列上收集单曲面结果的结构

我还有一些幻灯片描述了它们的派生和使用。

于 2010-07-23T05:57:29.070 回答
10

XOR Linked List使用两个 XOR'd 指针来减少双向链表的存储要求。有点晦涩但很整洁!

于 2011-03-24T16:20:20.987 回答
10

配对堆是一种堆数据结构,实现比较简单,实际摊销性能优良。

于 2009-02-01T14:03:28.817 回答
10

一种鲜为人知但非常漂亮的数据结构是Fenwick 树(有时也称为二进制索引树或 BIT)。它存储累积和并支持 O(log(n)) 操作。虽然累积和听起来可能不是很令人兴奋,但它可以适应许多需要排序/log(n) 数据结构的问题。

IMO,它的主要卖点是易于实施。在解决涉及编码红黑/avl树的算法问题时非常有用。

于 2010-01-28T20:21:54.373 回答
10

我真的很喜欢间隔树。它们允许您获取一堆间隔(即开始/结束时间或其他时间)并查询哪些间隔包含给定时间,或者在给定时间段内哪些间隔是“活动的”。查询可以在 O(log n) 中完成,预处理是 O(n log n)。

于 2011-03-24T16:02:54.060 回答
9

飞溅表很棒。它们就像一个普通的哈希表,除了它们保证恒定时间查找并且可以处理 90% 的利用率而不会损失性能。它们是Cuckoo Hash的概括(也是一个很好的数据结构)。它们看起来确实是专利,但与大多数纯软件专利一样,我不会太担心。

于 2010-07-22T17:21:54.277 回答
8

二元决策图是我最喜欢的数据结构之一,或者实际上是归约二元决策图(ROBDD)。

例如,这类结构可用于:

  • 表示项目集并在这些集上执行非常快速的逻辑操作。
  • 任何布尔表达式,旨在找到表达式的所有解决方案

请注意,许多问题可以表示为布尔表达式。例如,数独的解决方案可以表示为布尔表达式。并且为该布尔表达式构建 BDD 将立即产生解决方案。

于 2009-02-19T01:13:10.090 回答
8

增强的散列算法非常有趣。线性散列很简洁,因为它允许一次在散列表中拆分一个“桶”,而不是重新散列整个表。这对于分布式缓存特别有用。但是,对于大多数简单的拆分策略,您最终会快速连续拆分所有存储桶,并且表的负载因子会非常糟糕地波动。

我认为螺旋散列也很整洁。像线性散列一样,每次拆分一个桶,将桶中不到一半的记录放入同一个新桶中。它非常干净和快速。但是,如果每个“桶”都由具有相似规格的机器托管,则效率可能会很低。要充分利用硬件,您需要混合功能更弱和更强大的机器。

于 2009-02-18T20:29:37.103 回答
8

区域四叉树

(引自维基百科

区域四叉树通过将区域分解为四个相等的象限、子象限等来表示二维空间的划分,每个叶节点包含对应于特定子区域的数据。树中的每个节点要么恰好有四个孩子,要么没有孩子(叶节点)。

像这样的四叉树非常适合存储空间数据,例如纬度和经度或其他类型的坐标。

这是迄今为止我在大学时最喜欢的数据结构。给这个人编码并看到它工作非常酷。如果您正在寻找一个需要深思熟虑并且有点偏僻的项目,我强烈推荐它。无论如何,它比您通常在数据结构类中分配的标准 BST 衍生物有趣得多!

事实上,作为奖励,我在这里找到了课堂项目(来自弗吉尼亚理工大学)的讲座笔记(pdf 警告)

于 2010-11-23T03:20:16.337 回答
7

我喜欢 treaps - 因为简单而有效的想法是在二叉搜索树上叠加具有随机优先级的堆结构以平衡它。

于 2009-02-02T21:34:11.123 回答
6

DAWG是一种特殊的 Trie,其中相似的子树被压缩为单亲。我扩展了修改后的 DAWG,并提出了一个漂亮的数据结构,称为 ASSDAWG(Anagram Search Sorted DAWG)。其工作方式是每当将字符串插入 DAWG 时,首先对其进行桶排序,然后再插入,并且叶节点保存一个额外的数字,指示如果我们从根到达该叶节点,哪些排列是有效的。这有两个很好的优点:

  1. 由于我在插入之前对字符串进行了排序,并且由于 DAWG 自然地折叠了类似的子树,因此我得到了高水平的压缩(例如,“eat”、“ate”、“tea”都变成了 1 条路径 aet,叶节点处的数字列表表示aet 的哪些排列是有效的)。
  2. 现在,搜索给定字符串的字谜非常快速且简单,因为从根到叶的路径使用排列数在叶节点处保存该路径的所有有效字谜。
于 2011-03-24T16:19:07.317 回答
6

Fast Compact tries:

于 2009-06-13T10:56:39.413 回答
6

计数未排序的平衡 btree。

非常适合文本编辑器缓冲区。

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html

于 2009-03-24T21:34:13.907 回答
6

我有时使用反转列表来存储范围,它们通常用于在正则表达式中存储字符类。参见例如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 。

于 2010-07-23T08:03:25.300 回答
6

Arne Andersson 树是红黑树的一种更简单的替代方案,其中只有正确的链接可以是红色的。这极大地简化了维护,同时保持了与红黑树相当的性能。原始论文为插入和删除提供了一个漂亮而简短的实现。

于 2011-01-15T11:39:40.110 回答
5

我喜欢用于字符串处理的后缀树数组、用于平衡列表的跳过列表和用于自动平衡树的展开树

于 2009-04-02T09:38:26.753 回答
5

看看 Donald Knuth 提出的横向堆。

http://stanford-online.stanford.edu/seminars/knuth/071203-knuth-300.asx

于 2009-04-02T09:58:24.147 回答
5

BK-Trees 或 Burkhard-Keller Trees是一种基于树的数据结构,可用于快速查找字符串的近似匹配项。

于 2010-05-25T07:07:47.217 回答
5

Fenwick 树(或二叉索引树)是工具包的一个有价值的补充。如果您有一个计数器数组,并且需要在查询累积计数时不断更新它们(如在 PPM 压缩中),则 Fenwick 树将在 O(log n) 时间内完成所有操作,并且不需要额外的空间。另请参阅此topcoder 教程以获得很好的介绍。

于 2011-03-24T12:23:18.933 回答
5

Zobrist Hashing是一种散列函数,通常用于表示棋盘位置(如在国际象棋中),但肯定还有其他用途。关于它的一件好事是可以随着董事会的更新而逐步更新。

于 2011-04-17T02:06:38.123 回答
4

伸展树很酷。它们以一种将最常查询的元素移近根的方式重新排序。

于 2009-02-02T08:59:29.040 回答
4

您可以使用最小堆在恒定时间内找到最小元素,或者使用最大堆来找到最大元素。但是如果你想同时做这两个操作呢?您可以使用Min-Max在恒定时间内完成这两项操作。它通过使用最小最大排序来工作:在连续树级别之间的最小和最大堆比较之间交替。

于 2010-01-17T10:49:13.143 回答
4

远离所有这些图形结构,我只喜欢简单的Ring-Buffer

如果实施得当,您可以大大减少内存占用,同时保持性能,有时甚至提高性能。

于 2009-05-13T14:36:49.840 回答
4

根据 Bloom Filter 的提及,可删除的 Bloom Filters (DlBF) 在某些方面优于基本的计数变体。见http://arxiv.org/abs/1005.0352

于 2011-03-24T14:33:37.883 回答
4

持久数据结构

于 2010-07-17T17:17:21.180 回答
4

B* 树

它是一种以更昂贵的插入为代价的高效搜索 B 树。

于 2010-09-22T18:31:20.833 回答
3

优先级双端队列比必须维护 2 个具有不同排序的独立优先级队列便宜。 http://www.alexandria.ucsb.edu/middleware/javadoc/edu/ucsb/adl/middleware/PriorityDeque.html http://cphstl.dk/Report/Priority-deque/cphstl-report-2001-14.pdf

于 2010-05-23T08:43:09.927 回答
3

跳过列表实际上非常棒: http ://en.wikipedia.org/wiki/Skip_list

于 2009-05-10T22:03:00.687 回答
3

三元搜索树

  • 快速前缀搜索(用于增量自动完成等)
  • 部分匹配(当您想查找字符串 X 汉明距离内的所有单词时)
  • 通配符搜索

很容易实现。

于 2011-03-25T05:17:33.997 回答
3

使用 2 个堆栈实现的队列非常节省空间(与使用至少有 1 个额外指针/引用开销的链表相反)。

如何使用两个堆栈实现一个队列?

当队列很大时,这对我来说效果很好。如果我在一个指针上保存 8 个字节,这意味着有一百万个条目的队列可以节省大约 8MB 的 RAM。

于 2011-03-27T05:35:59.980 回答
3

我认为 Paolo Ferragina 和 Giovanni Manzini 的FM-index真的很酷。尤其是在生物信息学方面。它本质上是一个压缩的全文索引,它结合了后缀数组和参考文本的 burrows-wheeler 变换。可以在不解压整个索引的情况下搜索索引。

于 2011-03-24T22:34:45.837 回答
2

PQ-树

于 2010-05-23T02:23:35.670 回答
2

增量列表/增量队列在 cron 或事件模拟器等程序中用于计算下一个事件应该何时触发。 http://everything2.com/title/delta+list http://www.cs.iastate.edu/~cs554/lec_notes/delta_clock.pdf

于 2010-05-23T08:44:38.673 回答
2

正确的字符串数据结构。几乎每个程序员都满足于一种语言对结构的任何原生支持,这通常是低效的(特别是对于构建字符串,你需要一个单独的类或其他东西)。

最糟糕的情况是将字符串视为 C 中的字符数组,并依赖 NULL 字节来保证安全。

于 2010-02-17T19:03:09.643 回答
2

Burrows–Wheeler 变换(块排序压缩)

其压缩的基本算法。假设您要压缩文本文件上的行。你会说,如果你对这些行进行排序,你就会丢失信息。但 BWT 的工作原理是这样的——它通过对输入进行排序来大量减少熵,保持整数索引以恢复原始顺序。

于 2011-03-24T14:59:05.920 回答
2

我不确定这个数据结构是否有名字,但建议tokenmap包含在 Boost 中的数据结构有点有趣。它是一个可动态调整大小的映射,其中查找不仅是 O(1),而且是简单的数组访问。我写了关于这个数据结构的大部分背景材料,描述了它如何工作的基本原理。

操作系统使用令牌映射之类的东西将文件或资源句柄映射到表示文件或资源的数据结构。

于 2011-03-24T17:09:35.250 回答
2

PATRICIA - 检索以字母数字编码的信息的实用算法,DRMorrison (1968)。

PATRICIA 树与 Trie 相关。Tries 的问题在于,当键集稀疏时,即当实际键形成潜在键集的一小部分时,通常情况下,Trie 中的许多(大多数)内部节点只有一位子孙。这导致 Trie 具有很高的空间复杂度。

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/

于 2011-03-24T15:05:42.257 回答
2

一个角缝的数据结构。从总结:

角拼接是一种表示矩形二维对象的技术。它似乎特别适合用于 VLSI 布局的交互式编辑系统。该数据结构有两个重要特点:一是显式表示空白空间;其次,矩形区域的角落像拼布被子一样缝合在一起。这种组织导致搜索、创建、删除、拉伸和压缩的快速算法(线性时间或更好)。该算法是在一个简化的VLSI电路模型下提出的,并讨论了该结构的存储要求。测量表明,角拼接需要的存储空间大约是最简单的表示的三倍。

于 2011-03-24T14:38:56.783 回答
2

不相交集森林允许快速的成员查询和联合操作,并且最著名的是在 Kruskal 算法中用于最小生成树。

真正酷的是,这两个操作都摊销了与Ackermann Function的倒数成正比的运行时间,使其成为“最快的”非常量时间数据结构。

于 2011-05-19T01:00:52.050 回答
2

斗式旅

它们在 Apache 中被广泛使用。基本上它们是一个链表,在一个环中循环。我不确定它们是否在 Apache 和 Apache 模块之外使用,但它们作为一种很酷但鲜为人知的数据结构符合要求。桶是一些任意数据的容器,桶旅是桶的集合。这个想法是您希望能够在结构中的任何位置修改和插入数据。

假设您有一个存储桶旅,其中包含一个 html 文档,每个存储桶一个字符。您想要将所有<and>符号转换为&lt;and&gt;实体。桶旅允许您在遇到<>符号时在旅中插入一些额外的桶,以适应实体所需的额外字符。因为铲斗大队是一个环形,你可以向后或向前插入。这比使用简单的缓冲区更容易(在 C 中)。

下面是一些关于斗式旅的参考:

Apache Bucket Brigade 参考

桶和旅的介绍

于 2010-07-22T18:16:52.970 回答
2

我个人觉得稀疏矩阵数据结构非常有趣。 http://www.netlib.org/linalg/html_templates/node90.html

著名的 BLAS 库使用这些。当您处理包含 100,000 行和列的线性系统时,使用它们变得至关重要。其中一些也类似于计算机图形学中常见的紧凑网格(基本上就像一个桶排序的网格)。 http://www.cs.kuleuven.be/~ares/publications/LD08CFRGRT/LD08CFRGRT.pdf

同样就计算机图形学而言,MAC 网格有些有趣,但这只是因为它们很聪明。 http://www.seas.upenn.edu/~cis665/projects/Liquation_665_Report.pdf

于 2010-05-23T03:02:56.323 回答
1

二项式堆有很多有趣的属性,其中最有用的是合并。

于 2009-06-17T21:32:43.240 回答
1

我认为循环排序是一种非常简洁的排序算法。

这是一种用于最小化写入总数的排序算法。当您处理闪存的寿命与写入量成正比的闪存时,这特别有用。这是Wikipedia 文章,但我建议转到第一个链接。(漂亮的视觉效果!)

于 2011-04-01T05:37:57.840 回答
1

环境跟踪递归结构。

编译器使用递归但不像树的结构。内部范围有一个指向封闭范围的指针,因此嵌套是由内向外的。验证变量是否在范围内是从内部范围到封闭范围的递归调用。

public class Env
{    
    HashMap<String, Object> map;
    Env                     outer;

    Env()
    {
        outer = null;
        map = new HashMap();
    }

    Env(Env o)
    {
        outer = o;
        map = new HashMap();
    }

    void put(String key, Object value)
    {
        map.put(key, value);
    }

    Object get(String key)
    {
        if (map.containsKey(key))
        {
            return map.get(key);
        }
        if (outer != null)
        {
            return outer.get(key);
        }
        return null;
    }

    Env push()
    {
        return new Env(this);
    }

    Env pop()
    {
        return outer;
    }
}

我不确定这个结构是否有名字。我称之为由内而外的清单。

于 2010-05-25T16:44:15.587 回答
1

我以前在WPL Trees上运气不错。最小化分支的加权路径长度的树变体。权重由节点访问决定,使经常访问的节点迁移到更靠近根的位置。不知道它们与伸展树相比如何,因为我从未使用过它们。

于 2010-07-22T19:17:28.013 回答
1

其他人已经提出了 Burkhard-Keller-Trees,但我想我可能会再次提及它们以插入我自己的实现。:)

http://well-adjusted.de/mspace.py/index.html

周围有更快的实现(请参阅 ActiveState 的 Python 配方或其他语言的实现),但我认为/希望我的代码有助于理解这些数据结构。

顺便说一句,BK 和 VP 树的用途远不止搜索相似的字符串。只要您有一个满足几个条件(正性、对称性、三角不等式)的距离函数,您就可以对任意对象进行相似性搜索。

于 2010-07-17T17:33:06.797 回答
1

多边形网格的半边数据结构翼边

对计算几何算法很有用。

于 2011-03-24T16:52:19.497 回答
1

那里有一个聪明的数据结构,它使用数组来保存元素的数据,但是数组在链接列表/数组中链接在一起。

这样做的好处是元素的迭代非常快(比纯链表方法快),并且在内存中移动带有元素的数组和/或(取消)分配的成本最低。(因为这个数据结构对于模拟的东西很有用)。

我从这里知道:

http://software.intel.com/en-us/blogs/2010/03/26/linked-list-verses-array/

“......并且一个额外的数组被分配并链接到粒子数组的单元列表中。这在某些方面类似于 TBB 如何实现其并发容器。”(它是关于链接列表与数组的性能)

于 2010-07-13T23:05:05.717 回答
0

直角三角形网络 (RTIN)

自适应细分网格的精美简单方法。拆分和合并操作只是几行代码。

于 2011-03-24T22:58:44.897 回答
0

当我读到一些与 RMQ 和 LCA 相关的算法时,我偶然发现了另一种数据结构笛卡尔树。在笛卡尔树中,两个节点之间的最低共同祖先是它们之间的最小节点。将 RMQ 问题转换为 LCA 很有用。

于 2011-09-06T10:11:31.547 回答
0
  • 二元决策图(我最喜欢的数据结构,非常适合表示布尔方程并解决它们。对很多事情都有效)
  • 堆(节点的父节点始终与节点的子节点保持某种关系的树,例如,节点的父节点总是大于它的每个子节点(max-heap))
  • 优先级队列(实际上只是最小堆和最大堆,有利于维持许多元素的顺序,例如应该首先删除具有最高值的项目)
  • 哈希表,(具有各种查找策略,以及桶溢出处理)
  • 平衡二叉搜索树(每种都有自己的优势)
    • RB-trees(总体不错,插入、查找、删除和迭代时有序)
    • Avl-trees(查找速度比 RB 快,但在其他方面与 RB 非常相似)
    • 展开树(当最近使用的节点可能被重用时,查找速度更快)
    • 融合树(利用快速乘法以获得更好的查找时间)
    • B+Trees(用于数据库和文件系统中的索引,当从/向索引读取/写入的延迟很长时非常有效)。
  • 空间索引(非常适合查询点/圆/矩形/线/立方体是否彼此靠近或包含在彼此内)
    • BSP树
    • 四叉树
    • 八叉树
    • 范围树
    • 许多相似但略有不同的树,以及不同的尺寸
  • 区间树(很好的发现重叠区间,线性)
  • 图表
    • 邻接列表(基本上是边列表)
    • 邻接矩阵(表示图的有向边的表格,每条边有一位。图遍历非常快)

这些是我能想到的。维基百科上还有更多关于数据结构的内容

于 2009-02-18T19:47:57.297 回答