Memoization of Fibonacci series program to find nth term and using the OOPs concepts in rust to not recompute the sequence.

Today, while discussing how to lower demand on computing resources while generating the Fibonacci sequence, especially when it is to be queried a lot of times within a program, we came to experiment with memoization. In a simple program by @shanavas786, he implemented memoization with HashMaps, but to make it simpler, and since the concepts are almost the same, I would like to use Vec instead.

The struct in rust are sort of like classes, they can hold data and associated methods. Let's see how we can arrange the data.

struct Fib {
    cache: Vec<u64>
}

Yes, that's it! The objects of Fib will hold a Vec cache. But there's more, while we could simply make an object with let seq = Fib { cache: vec![0] };, that won't help us achieve our goal, we need constructors and methods. To define methods for a struct we impl, as we do below.

impl Fib {
    // Generate initial cache sequence
    fn new() -> Self {
        Fib{ cache: vec![1,1] }
    }
    ...
}

While we have defined the constructor and we are now able to do let seq = Fib::new();, we haven't achieved much more than we already had. We need to generate the cache beyond the current 2 elements, upto the nth element, so that we can really solve the problem at hand.

// Update sequence cache to include upto nth element of sequence
fn gen(&mut self, n: u8) {
    let li = self.cache.len() - 1; // last index of current cache
    // generate elements from current last index to n, hence update cache
    for i in li..(n as usize) {
        self.cache.push(self.cache[i] + self.cache[i-1]);
    }
}

Calling seq.gen(n) will now update cache to hold n terms and the last element of the cache will be the nth term of the Fibonacci sequence.

But, what if we are trying to get an nth term, where n might not be the length of cache, currently. This is a situation where n could either be lesser than or greater than the n with which the cache was previously generated. This also means that we can access the nth term without changing the cache if n is smaller than the current length of cache Vec, but have to update the cache upto n elements if it isn't. Let's define a get function to achieve this, appropriately.

// Procure nth element of sequence or generate the same
fn get(&mut self, n: u8) -> u64 {
    match self.cache.get(n as usize) {
        Some(&a) => a,
        None => {
            self.gen(n);
            *self.cache.last().unwrap()
        }
    }
}

Run in playground

Now, we will be able to call our Fib object and obtain the nth term of the series, multiple times.

fn main() {
    let mut seq = Fib::new();
    for i in 0..100u8 {
        println!("{} - {}", i, seq.get(i));
    }
}

Run in playground

NOTE: The use of u8 is because it's not possible to generate terms of the series where n is greater than 92, and hence it is impractical to use any unsigned integer values larger than the minimum. This is personal opinion.

de-sh/fiboops_rs.md

de-sh commented May 1, 2020

Uh oh!