实践中的高级数据结构

在我编程的10年里,我可以计算我一方面使用的数据结构的数量:数组,链表(我将堆栈和队列放在一起)和字典.考虑到我编写的几乎所有应用程序都属于数据形式/ CRUD类别,这并不奇怪.

我从来不需要使用红黑树,跳过列表,双端队列,循环链表,优先级队列,堆,图或过去50年来研究过的数十种奇异数据结构中的任何一种.我觉得我错过了.

这是一个开放式的问题,但这些"异国情调"的数据结构在实践中使用在哪里？有没有人有使用这些数据结构解决特定问题的实际经验？

一些例子.他们很模糊,因为他们为雇主工作:

一个堆得到的谷歌风格的搜索的前N个结果.(从索引中的候选者开始,线性地遍历它们,将它们筛选到最大大小为N的最小堆中.)这是用于图像搜索原型.

Bloom过滤器减少了某些数据的大小,这些数据是关于数百万用户已经看到的适合现有服务器的数量(为了速度,它们都必须在RAM中); 原始设计只需要为该数据库提供许多新服务器.

甲三角形阵列表示减半致密对称阵列的大小为推荐引擎(出于同样的原因再次RAM).

用户必须根据某些关联进行分组; union-find使这简单,快速,准确,而不是缓慢,笨拙和近似.

根据附近人们的驾驶时间选择零售站点的应用程序使用Dijkstra最短路径和优先级队列.其他GIS工作利用了四叉树和莫顿指数.

了解数据结构中的内容 - 土地就派上用场了 - "实验室中的数周可以节省您在图书馆的工作时间".由于规模的原因,使用bloom-filter案例是值得的:如果问题出现在启动而不是Yahoo,我会使用一个普通的旧哈希表.我认为其他任何例子在任何地方都是合理的(尽管现在你不太可能自己编写代码).

B树在数据库中.

R树用于地理搜索(例如,如果我有10000个形状,每个形状都有一个散布在二维平面周围的边界框,这些形状中的哪一个与任意边界框B相交？)

双端队列中的形式的C++ STL是可扩展的矢量(多个存储器效率比链表,和恒定的时间来"偷看"在中间的任意元件).据我所知,我从来没有完全使用deque(从两端插入/删除),但它足够通用,可以将它用作堆栈(从一端插入/删除)或队列(插入)一端,从另一端删除)并且还具有高性能访问权限,可以查看中间的任意元素.

我刚读完Java Generics和Collections - "泛型"部分让我感到很伤心,但是收藏部分很有用,他们指出了跳过列表和树之间的一些区别(两者都可以实现地图/集合):skip list为您提供从一个元素到下一个元素的内置常量时间迭代(树是O(log n)),并且在多线程情况下实现无锁算法要简单得多.

优先级队列用于安排其他事项(这里是一个简要讨论应用程序的网页); 堆通常用于实现它们.我还发现heapsort(至少对我来说)是最容易理解和实现的O(n log n)种类.

它们经常在图书馆的幕后使用.例如,有序字典数据结构(即,通过键排序遍历的关联数组)很可能不使用红黑树来实现.

许多数据结构(splay trees浮现在脑海中)对于它们在某些情况下的最佳行为(在splay树的情况下的时间参考位置)很有意义,因此它们主要与这些情况相关.在大多数情况下,对这些数据结构的工作知识的真正好处是能够在适当的情况下使用它们并合理地理解它们的行为.

进行排序,例如:

在大多数情况下 ,当单个段足够小时,快速排序或修改后的快速排序会降至另一种方法,这通常是大多数用途中最快的排序算法.但是,快速排序往往会对近乎排序的数据显示次优行为.

堆排序的主要优点是它可以在最小的中间存储的情况下就地完成,这使得它非常适合在内存受限的系统中使用.虽然它平均较慢(尽管仍然是n log(n)),但它并没有遭受快速排序的最差情况.

第三个例子是合并排序,它可以按顺序完成,使其成为排序比主存大得多的数据集的最佳选择.另一个名称是"外部排序",这意味着您可以使用外部存储(磁盘或磁带)对中间结果进行排序.