实践中的高级数据结构

一些例子。它们之所以含糊不清,是因为它们是为雇主工作的:

• A. heap 在谷歌风格的搜索中获得前N个结果。(从索引中的候选对象开始,线性地遍历它们,通过最大大小N的最小堆筛选它们。)这是一个图像搜索原型。

• Bloom filters 将数百万用户看到的某些数据的大小降低到适合现有服务器的大小(为了提高速度,所有数据都必须在RAM中);最初的设计需要许多新的服务器才能用于该数据库。

• A. triangular array representation 将推荐引擎的密集对称阵列的大小减半(出于同样的原因再次使用RAM)。

• 用户必须根据某些关联进行分组; union-find 使之简单、快速、准确,而不是缓慢、粗糙和近似。

• 一个应用程序,用于根据附近居民的驾车时间选择零售站点 Dijkstra shortest-path 使用优先级队列。其他地理信息系统工作利用了 quadtrees Morton 索引。

了解数据结构中的内容很方便——“在实验室呆上几周可以节省你在图书馆的时间”。BloomFilter的案例之所以值得,只是因为它的规模:如果问题是在一家初创公司而不是雅虎出现的,我会使用一个简单的旧哈希表。我认为其他例子在任何地方都是合理的(尽管现在你不太可能自己编写它们)。

B-trees 都在数据库中。

R-trees

deques 表格的 C++ STL 是可增长的向量(比链表内存效率更高,在中间“窥视”任意元素的时间恒定)。就我所记得的,我从来没有充分使用过DeQuin(从两端插入/删除),但一般来说,您可以使用它作为一个堆栈(从一端插入/删除)或队列(插入到一端,从另一个删除),并且还具有高性能的访问以查看中间的任意元素。

我刚读完 Java Generics and Collections --“仿制药”部分伤了我的头,但收藏部分很有用;他们指出了跳过列表和树(两者都可以实现映射/集)之间的一些区别:跳过列表为您提供了从一个元素到下一个元素的内置恒定时间迭代(树是O(logn))并且在多线程情况下实现无锁算法要简单得多。

优先级队列用于调度和其他事情(这里是一个 webpage

它们经常在图书馆的后台使用。例如,有序字典数据结构(即 associative array red-black tree.

许多数据结构( splay trees temporal locality of reference 在八字树的情况下),因此它们主要用于这些情况。在大多数情况下,了解这些数据结构的实际好处是能够在正确的环境中使用它们,并合理地理解它们的行为。

以排序为例:

• quicksort 单个片段变得足够小 用于大多数目的的算法。 几乎分类的数据。

• a的主要优点 heap sort 这件事可以在几分钟内完成 具有最小中间产物的原位 系统。虽然速度较慢 平均而言(尽管仍为n log(n)), 它不受影响 从最差的情况下的表现 快速排序。

• merge sort ,这是可以做到的 排序数据集的选择很多 比主内存大。 这个的另一个名字是 使用外部存储器(磁盘或磁盘)进行排序 磁带)用于中间结果。

这取决于您工作的抽象级别。

I use ring buffers/circular queues constantly in embedded work to service interrupts (e.g. serial ports).

Tree structures are heavily used in computer graphics.

If you use STL map or set data structures, then you are probably using a red-black tree without even knowing it!

我想你会看到很多高级算法都使用了奇特的数据结构。我想到的主要示例是*它使用一个图和一个由堆实现的优先级队列。

在金融学中,您需要使用树来计算依赖于许多其他动态值的工具的价值。电子表格也有类似的依赖关系树,编译器在转换为机器代码之前会创建一个抽象语法树。

Fibonacci heaps 用于高效地实现 Dijkstra's algorithm .

是的,有时。我所看到的问题是,许多人虽然知道它们,但他们不知道如何真正应用它们。大多数人会返回到数组、链表等。在大多数情况下,他们会将工作作为更高级的数据结构来完成(有时你真的必须“踢”进去),但效率较低。人们倾向于做对他们来说比较容易的事情,但这不一定是做事情的最佳方式。我不能指责他们,我肯定我也这样做,但这就是为什么在编程中你们看不到很多“高级”概念的原因。

但我发现,当我使用更高级的语言时,我不会费心以这种方式实现队列,因为我可以动态地增加和缩小列表,而不用太担心它。当然,这是要付出性能代价的,因为我对内存分配的时间控制较少,但这是我们能够拥有非常灵活的列表所付出的代价之一。

当数据结构由代码的需求决定时,您将倾向于看到更复杂的数据结构。通常,当您在较低级别处理更复杂的代码时,我会看到这一点,即在核心操作系统中,编写类库的基本部分(实现字符串、数组等),编写外部性能或多线程代码等。我认为它们在实现特定算法方面发挥着重要作用,搜索、采样、统计分析、优化等算法在编写时往往考虑到特定的数据结构。

我经常使用集合、排序集合(始终保持其元素的排序顺序,并支持快速元素插入)和惰性列表。

平衡树(红黑等)通常用于抽象数据类型的实现。

抽象数据类型的数量相对较少,例如

• 地图
• 有序映射
• 有序多重映射
• 优先级队列(看起来很像有序多重映射)

同样,集合看起来很像地图,但不需要值,只需要键。

你说的“字典”,可能是指地图或有序地图。

有些映射是无序的(通常作为散列实现)——这是有序映射的有用子集。

循环清单 用于缓存。

C++类模板提供了获取对象的接口( Cache<Obj, Len> )。它的多个安装返回不同类型的“屏幕”,如在图形界面的不同视图中。在幕后,如果请求的“屏幕”不可用,它将被创建(昂贵的操作)并推送到环形缓冲区的头部,将最旧的一个推出来(卸载其纹理等)。

因此,在始终从硬盘读取一组图像文件和将所有图像加载到RAM中并永久保存之间实现了一种折衷。折衷由各种缓冲区的长度控制。