data-structures - 高级数据结构实践

Question

关闭。这个问题是 opinion-based 。目前不接受答案。

---

想要改进这个问题吗？更新问题，以便 editing this post 可以用事实和引文来回答它。 .

已关闭 16 天前。

Improve this question

在我编程的 10 年里，我一只手就可以数出我使用过的数据结构的数量:数组、链表(我将堆栈和队列与此合并在一起)和字典。这并不奇怪，因为我编写的几乎所有应用程序都属于数据之上的表单/CRUD 类别。

我从来不需要使用红黑树、跳跃列表、双端队列、循环链表、优先级队列、堆、图或任何已在该领域研究过的数十种奇特数据结构。过去50年。我感觉我错过了。

这是一个开放式问题，但这些“奇异”数据结构在实践中用在哪里？有人有使用这些数据结构解决特定问题的实际经验吗？

Answer 1

一些例子。它们很模糊，因为它们是为雇主工作:

• A heap获取 Google 式搜索中的前 N ​​个结果。 (从索引中的候选者开始，线性地遍历它们，通过最大大小 N 的最小堆筛选它们。)这是用于图像搜索原型(prototype)。

• Bloom filters将数百万用户所看到的某些数据的大小削减到适合现有服务器的数量(为了速度，所有这些数据都必须存储在 RAM 中)；最初的设计需要许多新的服务器来用于该数据库。

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

• 必须根据某些关联对用户进行分组； union-find使这一切变得简单、快速、准确，而不是缓慢、粗暴和近似。

• 一款根据附近居民的驾驶时间选择零售地点的应用 Dijkstra shortest-path具有优先级队列。其他 GIS 工作利用 quadtrees和 Morton索引。

了解数据结构领域的内容会派上用场——“在实验室呆上几周可以节省你在图书馆的时间”。布隆过滤器案例之所以有值(value)，只是因为它的规模:如果问题是在初创公司而不是雅虎出现的，我会使用普通的旧哈希表。我认为其他示例在任何地方都是合理的(尽管现在您不太可能自己编写它们)。