Efficient "map over time"

1

  1. I have a structure of the form HashMap<u32, Rc<T>> for some generic T.

  2. I need to store multiple copies of this map at points in time, say m_0, m_1, m_2, ..., m_n

where m_(i+1) is "small edit" on m_i

where by "small edit" I mean a small number of insert/delete/update (far smaller than total # of elements in the actual map itself).

  1. Operations I need to be fast are:

3.1 for i: u32, k: u32, get me value of m_i[k] -> Option<T>
3.2 for i:u32, calc diff between m_i and m_(i+1)

=====

Any advice on what data structure (whether Rust has a builtin or not) to use?

2

The following should work for you. There's a data structure called a range map which would be more efficient than a BTreeMap, but this should get you going.

type Time = u32;
type MyMap<T> = HashMap<u32, BTreeMap<Time, Option<Rc<T>>>>;

fn operation_3_1<T>(map: &MyMap<T>, k: u32, i: Time) -> Option<&Rc<T>> {
    map.get(&k).and_then(|btree| btree.range(i..).next_back().and_then(|e| e.1.as_ref()))
}

Hopefully you can see how to write insert and operation_3_2 yourself.

3

To help your search, the formal computer science term for this is a "persistent data structure." (This is a different use of the word 'persistent' from e.g. saving something in a database.) There are a few crates that provide persistent data structures in rust, but I don't have experience with them so I can't recommend one over the others.

1 Like
4

I used to use Clojure so I'm familiar with persistent data structures (atleast persistent vectors + persistent maps). The issue here is that:

  1. I don't need persistence of every intermediate step, there are only certain steps I care about and
  2. I want efficient diffs

For the above reasons, there may be a better suited alterantive.

5

@zeroexcuses: check out im - Rust, it sounds like what you need.

6

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.