先进的数据结构在实践中
在编程的10年中，我可以统计一下我使用的数据结构的数量：数组，链表（我正在堆栈和排队）和字典。 考虑到我写的几乎所有的应用程序都落在了data-over-form / CRUD类别上，这并不奇怪。
我从来不需要使用红黑树，跳过列表，双端队列，循环链表，优先级队列，堆，图，或过去50年来研究的几十种奇特数据结构中的任何一种。 我觉得我错过了。
这是一个开放式的问题，但在实践中这些“异国情调”的数据结构在哪里呢？ 有没有人有任何使用这些数据结构解决特定问题的实际经验？
一些例子。 他们是模糊的，因为他们是为雇主工作：
-
获得排名前N的堆会导致Google风格的search。 （从索引中的候选人开始，通过线性遍历它们，筛选出最大大小为N的最小堆）。这是一个图像search原型。
-
布隆filter将某些数据的大小减less了几百万用户已经看到的数量，这些数据适合现有的服务器（为了提高速度，这些数据都必须在RAM中）。 原来的devise将需要许多新的服务器，只为该数据库。
-
三angular形arrays表示将推荐引擎的密集对称arrays的大小减半（出于同样的原因再次使用RAM）。
-
用户必须根据某些关联进行分组; 联盟发现使这个简单，快速，准确，而不是慢，哈克和近似。
-
根据附近人们的行车时间select零售网站的应用程序使用具有优先级队列的Dijkstra最短path 。 其他GIS工作利用四叉树和Morton索引。
了解数据结构中的内容 – 土地派上用场 – “实验室里的数周可以节省你在图书馆的时间”。 bloom-filter的情况只是值得的，因为规模：如果问题出现在一个启动而不是雅虎，我会使用一个普通的旧的哈希表。 我认为其他的例子在任何地方都是合理的（虽然现在你不太可能自己编码）。
B树在数据库中。
R树是用于地理search（例如，如果我有10000个形状，每个边界框分散在二维平面周围，哪些形状与任意边界框B相交？）
在C ++ STL中，forms的deques是可生成的向量（比链表更具有内存效率，并且可以不间断地在中间“偷看”任意元素）。 据我所知，我从来没有使用双端（从两端插入/删除），但它足够一般，你可以使用它作为一个堆栈（从一端插入/删除）或队列（插入到另一端删除），也有高性能的访问查看中间的任意元素。
我刚刚读完Javagenerics和集合 – “generics”部分伤害了我的头，但集合部分是有用的，他们指出跳过列表和树之间的一些区别（都可以实现地图/集）：skip列表为您提供了从一个元素到下一个元素的内置恒定时间迭代（树是O（log n）），并且在multithreading情况下实现无锁algorithm要简单得多。
优先级队列用于调度等（这里是一个简要讨论应用程序的网页 ）; 堆通常用来实现它们。 我也发现，heapsort（至less对我来说）是O（n log n）类中最容易理解和实现的。
他们经常在图书馆的幕后使用。 例如，一个有序的字典数据结构（即，一个关联数组 ，允许按键遍历遍历）很可能不会使用红黑树实现。
许多数据结构（浮现树浮现在脑海中）对于它们在某些情况下的最佳行为（在张开树的情况下的参考时间局部性 ）而言是有趣的，因此它们主要与在这些情况下使用有关。 在大多数情况下，对这些数据结构的工作知识的真正好处是能够在合理的情况下使用它们并对其行为有合理的理解。
以sorting为例，如：
-
在大多数情况下， 快速sorting或修改后的快速sorting，当单个段足够小时，可以使用另一种方法，通常是大多数情况下最快的sortingalgorithm。 但是，快速sorting往往在近似sorting的数据上显示出不理想的行为。
-
堆sorting的主要优点是可以在最小中间存储的情况下就地完成，这使得它在内存受限系统中非常有用。 虽然它平均速度较慢（尽pipe仍然是n log（n）），但它不会受到快速sorting的糟糕的最差情况的影响。
-
第三个例子是一个合并sorting ，可以顺序完成，这是sorting比您的主内存大得多的数据集的最佳select。 另一个名称是“外部sorting”，这意味着您可以使用外部存储（磁盘或磁带）进行sorting以获得中间结果。
这取决于你工作的抽象级别。
我知道我有和你一样的经验。 在目前大多数软件开发的抽象层面上。 Dictionary和List是我们使用的主要数据结构。
我认为，如果你低头看低层次的代码，你会看到更多的“异国情调”的数据结构。
我在embedded式工作中不断使用环形缓冲区/循环队列来服务中断（如串行端口）。
树结构大量用于计算机graphics学。
如果你使用STL映射或设置数据结构，那么你甚至可能在不知道它的情况下使用红黑树！
我想你会看到很多高级algorithm中使用的数据结构。 我想到的主要例子是A *，它使用一个Graph和一个由Heap实现的Priority Queue。
在财务中，您需要使用树来计算依赖于许多其他dynamic值的工具的价值。 电子表格具有类似的依赖关系树，编译器在转换为机器码之前创build一个抽象语法树。
斐波那契堆用于Dijkstraalgorithm的有效实现。
是的，有时。 我看到的问题是，一些人虽然知道他们，但他们不知道如何去真正地运用他们。 大多数人回到数组链表等。他们会在大多数情况下完成工作作为一个更先进的数据结构（有时你真的不得不“踢”到位），他们只是低效率。 人们倾向于做他们更容易的事情，但不一定是做事的最好方式。 我不能辜负他们，我相信我也是这样做的，但这就是为什么你在编程中看不到很多“先进”的概念。
我只是通过在stackoverflow上提出一个问题来find图的用法:)
大多数情况下，复杂的数据结构被认为是有害的。 引用经典：“我们应该忘记小效率，约97％的时间：过早的优化是万恶的根源。
但是，有一些用例是必需的。 比如，没有它们就很难想象内核编程。 红黑树的使用是pf是最快分组filter之一的原因之一。
另外，我知道很less有人写定量的金融图书馆和应用程序。 他们必须关心速度很多。
我已经使用循环链表来实现队列（以C语言），我将永远遍历队列，即networking连接队列。
但是我发现当我使用更高级的语言时，我并不觉得自己很难用这种方式实现队列，因为我可以dynamic地增长和缩小列表，而不用担心太多。 当然，这样做的性价比很高，因为我对内存分配发生的时间控制不了多less，但这是我们为了能够拥有非常灵活的列表而付出的代价之一。
当需要代码时，你会看到更复杂的数据结构。 通常我会在较低级别处理更复杂的代码时看到这一点，例如在核心操作系统中，编写类库的基本部分（实现string，数组等），编写出色的性能或multithreading代码等等。另外一个我认为他们扮演着重要angular色的地方是实现特定的algorithm，search，采样，统计分析，优化等algorithm通常都是用特定的数据结构来编写的。
我经常使用集合，sorting的集合（总是保持他们的元素sorting顺序，并支持快速元素插入）和惰性列表。
平衡树（红黑等）通常用于抽象数据types的实现。
只有相对较less的抽象数据types，比如
- 名单
- 地图
- 有序的地图
- 多地图
- 订购多地图
- 优先级队列（看起来很像一个有序的多图）
同样，一组看起来很像一张地图，但是你不需要这些值，只有键。
我发现这些东西中的大部分都是有用的。 优先级队列是一个非常有用的数据结构，并在各种algorithm（例如调度，寻路等）中有应用。
你说“字典”，你可能是指地图或有序的地图。
有些地图是无序的（通常作为散列实现） – 这是有序地图的有用子集。
