Applying memoization makes golom sequence slower-CodePudding

I am trying to wrap my head around memoization using c , and I am trying to do an example with the "golom sequence"

int main(int argc, char* argv[])
{
    std::unordered_map<int, int> hashTable;

    
    int value = 7;
    
    auto start = std::chrono::high_resolution_clock::now(); 
    std::cout << golomS(4, hashTable) << std::endl;
    auto stop = std::chrono::high_resolution_clock::now();
    
    auto start1 = std::chrono::high_resolution_clock::now();
    std::cout << golom(4) << std::endl;;
    auto stop1 = std::chrono::high_resolution_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(stop1 - start1);

    std::cout << "Time taken by function 1: "
           << duration.count() << " microseconds" << std::endl;

    
    std::cout << "Time taken by function 2: "
          << duration1.count() << " microseconds" << std::endl;
    
    return 0;
}

int golom(int n)
{
    if (n == 1) {return 1;}
    return 1   golom(n - golom(golom(n - 1)));
}

int golomS(int n, std::unordered_map<int, int> golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1   golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}

As an output I get this:

Time taken by function 1: 687 microseconds //This is Golom S

Time taken by function 2: 242 microseconds //This is Golom

Shouldn't GolomS be faster with memoization? I tried wrapping my head around the debugger, but im not sure where the effective "slowness" is coming from.

My question is: How can I change the method I made golomS, to be faster than golom. Thank you. -Adam

CodePudding user response：

On top of the other answers, I would like to add that this could really benefit from proper benchmarking.

In order to get reliable results you want to run the tests multiple times, and take steps to ensure that memory caches and other system-level shenanigans aren't interfering with the results.

Thankfully, there are libraries out there that can handle most of these complexities for us. For example, here's a better benchmark of your code using google's

see on quick-bench

CodePudding user response：

int golomS(int n, std::unordered_map<int, int> golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1   golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}

In your goloms function, you pass golomb as a value, not a reference. That means that every time you call goloms, the compiler will make a copy of golomb and destroy that copy when it's out of scope, not changing the actual golomb value.

You should pass by reference instead.

int golomS(int n, std::unordered_map<int, int>& golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1   golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}

CodePudding user response：

There are two issues in your code. First main issue is that you pass unordered map by value. You have to pass it by reference to make it faster, to avoid copying whole map on every function call. Also if you pass map by value then on return newly computed values are not preserved, but if you pass it by reference then new values will give benefit to caller functions.

Second important issue is that you use very small value 4 as input of a function to measure time, it takes very little time for 4 to compute, you have to use bigger value like 50, so that it takes more time to compute and hence gives more accurate time measurement.

Fixed version of your code has already very improved timings of first function compared to second (for input 50):

13
13
Time taken by function 1: 110 microseconds
Time taken by function 2: 118345 microseconds

Fixed code:

Try it online!

#include <unordered_map>
#include <iostream>
#include <chrono>

int golom(int n)
{
    if (n == 1) {return 1;}
    return 1   golom(n - golom(golom(n - 1)));
}

int golomS(int n, std::unordered_map<int, int> & golomb)
{
    if(n == 1)
        return 1; 
    if(golomb.find(n) == golomb.end())
        golomb[n] = 1   golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    return golomb[n];
}

int main(int argc, char* argv[])
{
    std::unordered_map<int, int> hashTable;
    
    auto start = std::chrono::high_resolution_clock::now(); 
    std::cout << golomS(50, hashTable) << std::endl;
    auto stop = std::chrono::high_resolution_clock::now();
    
    auto start1 = std::chrono::high_resolution_clock::now();
    std::cout << golom(50) << std::endl;;
    auto stop1 = std::chrono::high_resolution_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(stop1 - start1);

    std::cout << "Time taken by function 1: "
           << duration.count() << " microseconds" << std::endl;
    
    std::cout << "Time taken by function 2: "
          << duration1.count() << " microseconds" << std::endl;
    
    return 0;
}