Jon*_*rop 4 algorithm persistence purely-functional data-structures
我只是阅读Brodal等人的Purely Functional Worst Case Constant Time Catenable Sorted Lists.他们在数据结构的背景下对不同类型的持久性的介绍给我一个明显的问题:
汇合持久性:可以更新和查询所有版本,另外,可以组合两个版本以生成新版本.注意,在这种情况下,可以通过重复地将其与自身连接来在多项式时间内创建指数大小的结构.
通过反复加入自身,能够在多项式时间内创建"指数大小"结构的实际应用是什么？
Chr*_*aki 11
这是一个用例示例.想象一下通用"序列"数据类型在数组预期稀疏的情况下用作数组(即,大多数元素将包含相同的值,相对较少的点设置为某个其他值).如果序列数据类型具有此属性,那么您可以使用您提到的技术构建(可能非常大)数组,并且在此用法下仍然可以合理地节省空间和时间.
当然,你可以制作一个特殊用途的数据类型,特别是对于稀疏数组,它可能比通用数据类型更多的空间和时间效率,但重点是通用数据类型适应这种用法您可能甚至不需要创建特殊用途数据类型的模式.
(不可否认,这个例子是关于一般的融合持久性,而不是关于论文的"排序列表".然后,在本文中,他们正在对有关一致性持久性的问题提出质疑,而不是关于他们自己的数据结构.)
| 归档时间： |
|
| 查看次数： |
1125 次 |
| 最近记录： |