Questions tagged [persistent-data-structure]

A persistent data structure is a data structure that is never modified in place, but by creating a new data structure.

0
votes
0answers
15 views

Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)? [migrated]

The result by Driscoll et al 1989 states Any pointer-machine data structure with O(1) pointers to any node can be made partially persistent with O(1) ammortized multiplicative overhead and O(1) ...
0
votes
0answers
16 views

Do parent pointers affect path-copying in a persistent binary tree?

I am familiar with the concept of path-copying in the context of binary trees to achieve persistent modifications, but I am unsure if the inclusion of parent pointers has any effect on the complexity. ...
2
votes
0answers
17 views

Formal semantics of a mutable/imperative stack

When introducing formal semantics for data structures, immutable stacks are a nice simple example : $\mathit{is\_empty}(\mathit{create()})=\mathrm{True}$ $\mathit{is\_empty}(\mathit{push}(e, s))=\...
0
votes
0answers
24 views

How do Clojure's persistent data structure determine equality?

I'm trying to understand the time complexity of determining equality between persistent data structures in Clojure (Vectors, Maps, Sets, etc.). These are based on data structures pioneered by Phil ...
2
votes
0answers
23 views

Distributed Computing: Persistent Data Structures in Functional Programming versus Wait-Free Data Structures

Persistent (aka immutable) data structures in functional programming sidestep issues of shared memory mutual exclusion, and thus also issues such as data races that arise and which may be difficult to ...
3
votes
0answers
47 views

Persistent data structures representing a directed graph's paths

Are there any standard persistent data structures that facilitate the following? tabulating, for each arc in a rooted, oriented, acyclic multigraph, the set of root-emanating paths containing the arc ...
2
votes
0answers
43 views

Persistent data structure with double and subtract operations

I am seeking a data structure that maintains an array of N numbers and supports the following two operations: Double the first i numbers Subtract the first i numbers of a previous version from the ...
0
votes
0answers
155 views

Analysis of finding the k-th largest element in a subsegment of an array

Given an array $A$ of length $N$. There are $Q$ queries, each queries will be in the form ...
1
vote
0answers
53 views

combine divergent persistent red-black tree instances

Given a persistent red-black tree, I've been searching for an algorithm, approach, or equivalent data structure that allows me to efficiently merge two instances of the tree produced by divergent ...
4
votes
1answer
84 views

How do confluently persistent data structures handle merge conflicts?

From my limited understanding fully persistent data structures allow changes to be made to previous nodes, with new nodes creating a branch rooted at the changed node, resulting in a tree of nodes and ...
0
votes
0answers
34 views

What is a good rule-of-thumb for the size of leaf nodes in a rope?

The formal descriptions of ropes I’ve found use very small numbers like 4 or 8 characters per leaf node as the maximum size. Some also mention that this (obviously) is not a very efficient rope size ...
3
votes
2answers
568 views

What is the “Chairman Tree”?

My competitive programming coach told me of a balanced binary tree used by a lot of Chinese competitors that has all the functions of any other balanced binary tree and is fully persistent and runs ...
3
votes
2answers
118 views

Using persistence on a constant database

I'm quite new to understanding persistent data structures, so bear with me. Consider some database with data of the form $(\text{id}, d_1, d_2)$. The last two could e.g. mean production data and ...
5
votes
2answers
407 views

Is it possible to build a heap from the root to the leaves?

Most books on data-structures will briefly introduce heaps (aka priority queues) and then move to describe the "trick" allowing heaps to be implemented as arrays. I've been looking for a way to ...
3
votes
1answer
75 views

Guessing the structure of a finger tree from the number of elements

I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger ...
0
votes
0answers
69 views

Immutable data structures for 2d+ lattices

I would like to find an immutable/persistent data structure that allows efficient updating for 2d (or higher) lattices/arrays/matrices, and reasonable performance when appending in any direction. ...
3
votes
2answers
391 views

How append, prepend, and generally insertAt work in RRB-tree

I read the paper about Relaxed Radix Balanced trees (RRB trees) and am trying to implement them. What I can't get is how insertion at an index should be performed step by step. Can anyone proficient ...
11
votes
2answers
2k views

Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration

I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations. Clojure provides persistent Vector,...
5
votes
1answer
117 views

What progress has been made on persistent catenable deques in the last decade?

I'm interested in persistent catenable deques: deques that can be concatenated. Kaplan and Tarjan came up with the first such data structure in 1995; Okasaki came up with a simpler, amortized version ...
17
votes
1answer
1k views

What classes of data structures can be made persistent?

Persistent data structures are immutable data structures. Operations on them return a new "copy" of the data structure, but altered by the operation; the old data structure remains unchanged though. ...
1
vote
1answer
237 views

Multithreaded access to a persistent linked list data structure

I previously asked a question about persistent data structures here. After that I came across an article that introduced persistent data structures. I have got a question on the following figure from ...
21
votes
4answers
3k views

Why do we use persistent data structures in functional programming?

Functional programming employs persistent data structures and immutable objects. My question is why is it crucial to have such data structures here? I want to understand at a low level what would ...