t0y*_*yv0 74 statistics functional-programming avl-tree red-black-tree data-structures
给定数据结构规范,例如具有已知复杂性边界的纯函数映射,必须在若干实现之间进行选择.有一些关于如何选择正确的民间传说,例如红黑树被认为通常更快,但AVL树在工作负载上具有更好的性能和许多查找.
是否有关于这种知识的系统性介绍(发表的论文)(与集合/地图相关)？理想情况下,我希望看到对实际软件进行统计分析.例如,它可能得出结论,有N种典型的地图用法,并列出每种地图的输入概率分布.
是否有系统基准测试地图并设置不同输入分布的性能？
是否存在使用自适应算法根据实际使用情况更改表示的实现？
这些基本上都是研究课题，结果一般以结论的形式给出，而统计数据则是隐藏的。不过，可以对自己的数据进行统计分析。
对于基准测试，最好查看实现细节。
问题的第三部分是一个非常主观的问题，在实施时可能永远不会知道实际意图。但是，像 perl 这样的语言会尽力为每个操作实现高度优化的解决方案。
以下内容可能会有所帮助：Chris Okasaki http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf 的Purely Functional Data Structures