我只是在阅读Brodal 等人的纯功能最坏情况恒定时间可连接排序列表。他们对数据结构上下文中不同类型持久性的介绍给我留下了一个明显的问题：
融合持久化：所有版本都可以更新和查询，另外，两个版本可以组合产生一个新版本。请注意，在这种情况下，可以通过重复将其与自身连接来在多项式时间内创建指数大小的结构。
通过反复将其与自身连接来在多项式时间内创建“指数大小”结构的实际应用是什么？
问问题
1261 次
3 回答
11
这是一个示例用例。想象一个通用的“sequence”数据类型在预期数组是稀疏的情况下用作数组（即，大多数元素将包含相同的值，相对较少的点设置为其他值）。如果序列数据类型具有此属性，那么您可以使用您提到的技术构建（可能非常大）数组，并且在这种用法下它仍然具有合理的空间和时间效率。
当然，你可以为稀疏数组创建一个特殊用途的数据类型，它可能比通用数据类型更节省空间和时间，但关键是通用数据类型足够优雅地适应这种用法您甚至可能不需要创建专用数据类型的模式。
（诚然，这个例子是关于一般的融合持久性，而不是关于论文的“排序列表”。再一次，在论文中，他们对一般的融合持久性发表了有问题的评论，而不是专门针对他们自己的数据结构.)
于 2012-06-16T12:02:18.640 回答
1
我没有阅读这篇论文，但是通过查看您提供的 Confluent Persistence 的定义，我可以将其与二项式堆等数据结构相关联，其中合并操作是对数运行时间，它非常适合集合联合类型的算法。随着树呈指数增长并考虑到二项式堆，我们可能有几个，并且每个都可以在多项式时间内合并。执行联合操作将是我认为对于此类数据结构以及多项式时间内最好的应用程序。
于 2012-06-15T09:13:53.703 回答
0
您的问题表明您阅读论文时说此属性是表现出这种持久性的数据结构的优势。看看这篇论文，我不认为这就是作者的意图——这只是他们想要指出的这种数据结构的一个有点违反直觉的属性，以使读者感到有趣和愉悦。
作为进一步说明，我认为作者谈论的指数大小是“数学”大小（抽象意义上的节点数），而不是内存大小 - 不可能访问或编写多项式时间内的内存位置的指数数量！
于 2012-06-15T20:20:21.947 回答