Need help with memory size of data structure tracking all changes (no deletions)

help
1

I'm trying to build a data structure that keeps track of every value it ever had with respect to time. Obviously it requires quite a bit of memory. This is where I'm at after trying a few variants of radix tries (the adaptive kind). The a huge win was the SortedVec which is just a Vec<(u64, A)> sorted by time.

pub enum TCell<A: Clone + Default + Debug + PartialEq> {
    TCellEmpty,
    TCell1(u64, A),
    TCellVec(SortedVec<u64, A>),
    TCellN(BTreeMap<u64, A>),
}

    pub fn new(t: u64, a: A) -> Self { ... }
    pub fn set(&mut self, t: u64, a: A) { ... }
    pub fn iter_window_t(&self, r: Range<u64>) -> Box<dyn Iterator<Item = (&u64, &A)> + '_> { ... }
    pub fn iter_window(&self, r: Range<u64>) -> Box<dyn Iterator<Item = &A> + '_> { ... }

I'm flexible in reducing the performance if I can get reductions in memory usage.

2

I don't see a question here.

3

Is there a better suited sorted map that could result in a smaller memory footprint?

4

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.