什么时候实现数据结构而不是使用内置数据结构是个好主意?

When would it be a good idea to implement data structures rather than using built-in ones?

为某些编程语言创建自己的链表或其他数据结构(如映射、队列或哈希函数)而不是使用内置的有什么目的,或者我为什么要自己创建它?谢谢。

好问题!您可能想要这样做的原因有多种。

对于初学者来说,并非所有编程语言都附带您可能想要使用的所有良好数据结构。例如,C 没有用于 any 数据结构的内置库(尽管它确实有用于数组的 bsearchqsort),所以如果你想要在 C 中使用链表、散列 table 等,您需要自己构建或使用自定义第三方库。

其他语言(例如,JavaScript)内置支持某些但不是所有类型的数据结构。例如,没有对链表或二叉搜索树的原生 JavaScript 支持。而且我不知道 任何 主流编程语言具有 tries 的内置库,但如果不是这种情况请告诉我!

以上示例指出了某些数据结构缺乏支持的地方,需要您自己编写。但是还有其他原因可能会导致您想要实现自己的自定义数据结构。

一个重要的是效率。将自己置于必须为特定编程语言实现动态数组、散列 table 和二叉搜索树的人的位置。您不可能知道人们将使您的数据结构受制于哪些工作流程。他们是要进行大量的插入和删除操作,还是主要用于查询?例如,如果您正在编写一个二叉搜索树类型,其中插入和删除很常见,您可能希望查看类似 red/black 树的东西,但如果插入和删除很少见,那么 AVL 树就可以工作好了很多。但是您无法预先知道这一点,因为您必须编写一个经得起时间考验并且适用于所有应用程序的实现。这可能会建议您选择一个 "reasonable" 选项,该选项在许多应用程序中都能很好地工作,但不会针对您的特定应用程序进行积极的性能调整。因此,编写自定义数据结构可能会让您利用正在解决的问题的特定结构。

在某些情况下,语言规范使得不可能或难以使用数据结构的快速实现作为语言标准。例如,C++ 要求其关联容器允许元素的删除和插入,而无需将任何迭代器插入其中。这使得使用 B 树等类型的容器实现更具挑战性/效率更低,由于缓存的影响,这些容器实际上可能比常规二叉搜索树执行得更好。类似地,无序容器的实现有一个假定链式散列的接口,这不一定是您想要实现散列的方式 table。这就是为什么,例如,有 Google 的 alternatives to the standard containers 被优化以使用不容易适应语言框架的自定义数据结构。

图书馆可能无法提供最快容器的另一个原因是提供简单界面方面的挑战。例如,cuckoo hashing 是一种较新的哈希方案,它在实践中具有出色的性能并保证最坏情况下的高效查找。但是要使 cuckoo 散列有效,您需要能够为给定的数据类型 select 多个 散列函数。大多数编程语言都有一个概念,即每个数据类型都有 "a" 哈希函数(std::hash<T>Object.hashCode__hash__ 等),这与这个想法不相符。这些语言原则上可能要求用户编写散列函数系列,因为每个对象都有许多不同的散列可供选择,但这会使编写您自己的自定义类型的逻辑复杂化。让程序员为需要它的类型编写散列函数族,然后让语言保持简单。

最后,space 中有简单的创新。新的数据结构一直在被发明,而语言的发展和变化往往很缓慢。最近对新的更快的二叉搜索树(以 WAVL trees 为例)或新的散列策略(布谷鸟散列和 Google 开发的 "Swiss Table")和语言进行了大量研究设计者和实施者并不总是能够跟上他们的步伐。

所以,总的来说,答案是 "because you can't assume your favorite data structure will be there" 和 "because you might be able to get better performance rolling your own implementations."

的混合

我能想到的最后一个原因是 "to learn how the language and the data structure work." 有时构建自定义数据类型只是为了提高您的技能是值得的,当您做!

综上所述,我不建议每次需要时都默认编写自己的数据结构版本。库版本通常是一个非常安全的选择,除非您正在寻找额外的性能或者您缺少一些您需要的功能。但希望这能让您更好地理解为什么您可能要考虑搁置默认的、经过良好测试的工具并构建您自己的工具。

希望对您有所帮助!