algorithm - 合流持久化的实际应用

Question

我正在阅读 Purely Functional Worst Case Constant Time Catenable Sorted Lists布罗达尔等人。以及他们对数据结构上下文中不同类型持久性的介绍给我留下了一个明显的问题:

Confluent persistence: all the versions can be updated and queried and additionally, two versions can be combined to produce a new version. Note that in this case it is possible to create in polynomial time an exponentially sized structure by repeatedly joining it with itself.

能够在多项式时间内通过反复将其与自身连接来创建“指数大小”的结构的实际应用是什么？

Answer 1

这是一个示例用例。想象一个通用的“序列”数据类型被用作一个数组，在这种情况下数组应该是稀疏的(即，大多数元素将包含相同的值，相对较少的点设置为某个其他值)。如果序列数据类型具有此属性，那么您可以使用您提到的技术构建(可能非常大的)数组，并且在这种用法下它仍然具有合理的空间和时间效率。

当然，您可以创建一个专门用于稀疏数组的专用数据类型，它可能比通用数据类型更节省空间和时间，但关键是通用数据类型足够优雅地适应对于这种使用模式，您甚至可能不需要创建专用数据类型。

(不可否认，这个例子是关于一般的汇合持久性，而不是关于论文的“排序列表”。然后，在论文中，他们再次对一般的汇合持久性发表了有问题的评论，而不是专门针对他们的自己的数据结构。)