Introduction to Persistent Data Structures

Introduction

A Persistent Data Structure always retains every historical version and supports the immutable property of operations.

Classification of Persistence

Partially Persistent

All versions are accessible, but only the latest version can be modified.

Fully Persistent

All versions are both accessible and modifiable.

If merging two historical versions is supported, it is also called Confluently Persistent.

Practical Applications

Geometric Computation

In geometric computation, there are many offline algorithms, such as sweep line algorithms that answer all queries in a single pass, offering excellent time complexity analysis. However, in a forced online scenario, scanning each time reduces the query operation's time complexity from logarithmic to linear. To address this, persistence technology provides an alternative approach: we treat the timeline of the sweep line as a basis for changes and persist the related structure. As long as we can navigate this timeline in logarithmic time for queries, we can dynamically solve the aforementioned problem.

String Processing

To achieve highly efficient merge operations and prevent performance degradation caused by generating a large number of duplicate strings, enabling various operations to be far below linear time. For example, C++ rope is a persistent data structure. Not only for string operations, but persistence concepts can also be applied when dealing with types that have a high degree of duplication.

Version Rollback

This corresponds to redo/undo in most application software. If database/operation changes are paired with complex structures for high efficiency (unlike hash or set, where reversal operations only require constant or logarithmic time), then to quickly revert changes, persistent structures aim to reduce the cost of redo/undo.

The database itself can revert in constant time by recording the changed parts. For application-layer computations, most implementations discard the cache and recalculate a new structure. Sometimes, the size of the rollback change is m, and recalculating the structure consumes n+m. If the difference between n and m is very large, the experience of continuous rollbacks becomes poor.

Functional Programming

Functional programming requires special data structures to align with language characteristics, where immutability is particularly important for parallel environments and debugging. For example, object-oriented programming languages like Java introduced the stream class after Java 8, supporting functional syntax design and providing special features such as lazy evaluation and infinite value domains.

References

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用