Lookup tables (finite maps) are a ubiquitous data structure. In pure functional languages they are best represented using trees instead of hash tables. In pure functional languages within constructive logic, without a primitive integer type, they are well represented using binary tries instead of search trees. In this work, we introduce canonical binary tries, an improved binary-trie data structure that enjoys a natural extensionality property, quite useful in proofs, and supports sparseness more efficiently. We provide full proofs of correctness in Coq. We provide microbenchmark measurements of canonical binary tries versus several other data structures for finite maps, in a variety of application contexts; as well as measurement of canonical versus original tries in a big, real system. The application context of data structures contained in theorem statements imposes unusual requirements for which canonical tries are particularly well suited.


翻译:查找表格( 无限地图) 是无处不在的数据结构。 在纯功能语言中, 他们最能代表的是树木而不是散列表格。 在建设性逻辑范围内的纯功能语言中, 没有原始整数类型, 他们完全能代表的是二进制尝试, 而不是搜索树。 在这项工作中, 我们引入了粗体二进制尝试, 改进的二进制数据结构, 具有自然延伸性属性, 在证明中非常有用, 并更高效地支持稀疏性 。 我们在 Coq 中提供了完整的正确性证据 。 我们提供了在各种应用背景下对定点地图的卡通性二进制尝试和若干其他数据结构的微比目标记测量 ; 以及在大型、 真实系统中的卡通式尝试和原始尝试的测量 。 语标中包含的数据结构的应用背景提出了不寻常的要求, 而 语法性尝试特别适合 。

0
下载
关闭预览

相关内容

【干货书】开放数据结构,Open Data Structures,337页pdf
专知会员服务
16+阅读 · 2021年9月17日
专知会员服务
84+阅读 · 2020年12月5日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
60+阅读 · 2020年3月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
CCF推荐 | 国际会议信息6条
Call4Papers
9+阅读 · 2019年8月13日
计算机 | 国际会议信息5条
Call4Papers
3+阅读 · 2019年7月3日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
已删除
将门创投
3+阅读 · 2019年4月19日
Gartner:2019 年 MSP 魔力象限
云头条
15+阅读 · 2019年3月6日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
计算机类 | ISCC 2019等国际会议信息9条
Call4Papers
5+阅读 · 2018年12月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Arxiv
9+阅读 · 2021年10月5日
Arxiv
4+阅读 · 2019年1月14日
Efficient and Effective $L_0$ Feature Selection
Arxiv
5+阅读 · 2018年8月7日
Arxiv
5+阅读 · 2018年5月31日
VIP会员
相关VIP内容
【干货书】开放数据结构,Open Data Structures,337页pdf
专知会员服务
16+阅读 · 2021年9月17日
专知会员服务
84+阅读 · 2020年12月5日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
60+阅读 · 2020年3月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
CCF推荐 | 国际会议信息6条
Call4Papers
9+阅读 · 2019年8月13日
计算机 | 国际会议信息5条
Call4Papers
3+阅读 · 2019年7月3日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
已删除
将门创投
3+阅读 · 2019年4月19日
Gartner:2019 年 MSP 魔力象限
云头条
15+阅读 · 2019年3月6日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
计算机类 | ISCC 2019等国际会议信息9条
Call4Papers
5+阅读 · 2018年12月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Top
微信扫码咨询专知VIP会员