CODEWITHSUNDEEP
c++dictionarymemoizationstdmap
Bruce
Bruce

Reputation: 955

Memoization in limited space

While trying to increase the speed for my answer for this contest, I have a function which takes two values n and k and produces an output. The calculations are repeated, so I'm memoizing it. I can't use a 2D array, since the constraints for n and k are 10^5! So I'm using a map:

std::map<std::pair<int,int>,double> m;

double solve(int n, int k)
{
    if(k==0) return n;
    if(k==1) return (n-1)/2.0;

    std::pair<int,int> p = std::make_pair(n,k);
    std::map<std::pair<int,int>,double>::iterator it;

    if( (it=m.find(p)) != m.end())
        return it->second;

    double ans = 0;
    for(int i=1 ; i<=n-1 ; i++)
        ans += solve(i,k-1);
    ans = ans/n;
    m[p] = ans;

    return ans;
}

But apparently, this approach is way too slow. Is there some problem with my memoization? Or can I get constant time fetches like an array instead of logarithmic fetches from a map?

This function solves this recurrence:

formula

f(x,0) = x and f(x,1) = (x-1)/2

Can this be solved in a better way? Thanks a lot in advance.

Upvotes: 0

Views: 254

Answers (2)

Derek Ledbetter
Derek Ledbetter

Reputation: 4895

You don't have to store a two-dimensional array of values. Instead of memoization, turn the problem around and use dynamic programming instead.

To save some time, note that f(x, y) = 0 if x <= y.

Calculate the values of f(i, 0) for 1 <= i <= x - k and store them into a one-dimensional array. Then calculate f(i, 1) for 2 <= i <= x - k + 1, f(i, 2) for 3 <= i <= x - k + 2, and so on, until you get f(i, k - 1) for k <= i <= x - 1. Then you can calculate f(x, k). At each step, you only need two arrays of length x - k.

Calculating f(i, j) takes i - j - 1 additions and a division. so the total time is ϴ((x - k)2 k). But it's faster if you compute the sums first and then divide, because each sum is just one element more than the previous, so then the total time is ϴ((x - k) k).

Upvotes: 0

SebastianK
SebastianK

Reputation: 3707

Minor improvement: Remember the iterator returned by find and dereference it instead of using operator[].

Upvotes: 2

Related Questions