algorithm - 用已经支持它们的语言实现数据结构/算法

Question

用您选择的语言实现您自己的数据结构和算法版本是否有意义，即使它们已经受到支持，知道已经注意调整它们以获得最佳性能？

Answer 1

有时候是的。您可能需要针对特定​​情况优化数据结构，或为其提供一些特定的额外功能。

一个 java 示例是apache Lucene（一个成熟的、广泛使用的信息检索库）。尽管Map<S,T>接口和实现已经存在——出于性能问题，它的使用还不够好，int因为Integer它IntToIntMap把Map<Integer,Integer>.

Answer 2

该问题包含一个错误的假设，即存在“最佳性能”之类的东西。

如果已经存在的代码针对您的特定使用模式进行了优化以获得最佳性能，那么您就不可能在性能方面对其进行改进，并且尝试这样做是徒劳的。

但是，它并未针对您的特定用途进行调整以获得最佳性能。假设它完全经过调整，它的设计旨在平均具有良好的全面性能，涵盖许多可能的使用模式，其中一些与您无关。

因此，原则上可以通过自己实现代码，应用一些对您有帮助的调整，并且（如果实施者完全认为该调整）可能会在其他地方阻碍其他用户。但这没关系，他们不必使用您的代码。也许你喜欢杜鹃散列，而他们喜欢线性探测。

实施者可能没有考虑调整的原因包括：他们不如你聪明（很少见，但确实发生了）；当他们编写代码时并没有发明调整，并且他们没有遵循该结构/算法的最新技术；他们有更好的事情来处理他们的时间，而你没有。在这些情况下，一旦你完成，他们可能会接受你的补丁。

除了性能之外，还有一些其他原因，您可能想要一个与您的语言支持的数据结构非常相似的数据结构，但添加或删除了一些特定的行为。如果你不能在现有结构之上实现它，那么你可能会从头开始。显然，这样做的成本很高，无论是前期还是未来的支持，但如果值得，那么你就去做。

Answer 3

当您使用编译语言（如 C、Assembly..）时，这可能是有意义的。使用解释型语言时，您可能会损失性能，因为本机结构解析器已经编译，不会浪费时间“解释”新结构。只有当本机结构或算法缺少您需要的东西时，您才会这样做。