论文标题
提示词典：有效的功能有序集和地图
Hinted Dictionaries: Efficient Functional Ordered Sets and Maps
论文作者
论文摘要
本文介绍了提示的词典，以表达有效的有序集和地图功能。与具有对数操作的传统有序词典相反，暗示词典可以通过使用称为提示的光标式对象来实现更好的性能。暗示词典统一了命令有序词典（例如C ++映射）和功能性词（例如Adams的集合）的接口。我们表明，此类词典可以使用分类的阵列，不平衡的树木和平衡的树作为其基础表示。在整篇文章中，我们使用Scala介绍提示词典的不同组成部分。我们还提供了C ++实施，以评估提示词典的有效性。与C ++的标准库相比，提示的词典为设置操作提供了出色的性能。此外，与Scipy库相比，它们显示出竞争性的表现。
This article introduces hinted dictionaries for expressing efficient ordered sets and maps functionally. As opposed to the traditional ordered dictionaries with logarithmic operations, hinted dictionaries can achieve better performance by using cursor-like objects referred to as hints. Hinted dictionaries unify the interfaces of imperative ordered dictionaries (e.g., C++ maps) and functional ones (e.g., Adams' sets). We show that such dictionaries can use sorted arrays, unbalanced trees, and balanced trees as their underlying representations. Throughout the article, we use Scala to present the different components of hinted dictionaries. We also provide a C++ implementation to evaluate the effectiveness of hinted dictionaries. Hinted dictionaries provide superior performance for set-set operations in comparison with the standard library of C++. Also, they show a competitive performance in comparison with the SciPy library for sparse vector operations.
