Answers are grounded in this paper and cite their sources.
Computational study demonstrates an efficient transient sequence data structure with fast splitting and concatenation, suggesting a versatile general-purpose candidate.
A transient data structure is a combination of an ephemeral data structure, a persistent data structure, and fast conversions between them. We present a transient sequence data structure that supports efficient read and write access at an arbitrary index with worst-case time complexity O ( K log K n ), pushing and popping at either end with complexity O ( K log K n ), and splitting and concatenation with complexity O ( K log K n +log K 2 n ), where K is a user-defined chunk size and n is the length of the sequence. We provide a detailed analysis of this data structure and show that, in many favorable scenarios, it performs much better than these pessimistic bounds might suggest. Furthermore, we describe its implementation, and provide a synthetic benchmark to evaluate the performance of push and pop . We believe that it is a good candidate for a one-size-fits-all, general-purpose sequence data structure.
No takes yet. Share an insight, caveat, or question.
Charguéraud et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: