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.