75

给定一个数据结构规范，例如具有已知复杂性界限的纯功能映射，必须在几种实现之间进行选择。关于如何选择正确的树有一些民间传说，例如红黑树通常被认为更快，但 AVL 树在具有许多查找的工作负载上具有更好的性能。

  1. 是否对这些知识（与集合/地图相关）进行了系统的介绍（已发表的论文）？理想情况下，我希望看到对实际软件进行的统计分析。例如，它可能会得出结论，有 N 种典型的地图使用类型，并列出每种类型的输入概率分布。

  2. 是否有系统的基准测试可以在不同的输入分布上测试地图和设置性能？

  3. 是否有使用自适应算法根据实际使用情况更改表示的实现？

4

1 回答 1

5

这些基本上都是研究课题，结果一般以结论的形式给出，而统计数据是隐藏的。不过，可以对自己的数据进行统计分析。

对于基准，最好通过实施细节。

第三部分的问题是一个非常主观的问题，实际意图在执行时可能永远不会知道。然而，像 perl 这样的语言尽最大努力为每个操作实现高度优化的解决方案。

以下可能会有所帮助：Chris Okasaki 的纯功能数据结构 http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

于 2013-11-27T17:22:54.053 回答