[Solved] Why does this solution works in JavaScript but takes too long in C++? (Dynamic Programming)

Question

A difference between your JavaScript and C++ code samples is: the C++ function has just two parameters instead of 3, the map object being managed as a global entity.

In some sense, having just 2 parameters is “The Right Thing”. The unordered map is about some internal necessity of the algorithm. Why should user code have to know about that ?

And should you some day decide to use instead an ordered map or a set or a bit vector, why should that force user code to change the list of header files it has to #include ?

So having just 2 parameters is fine, however managing the map as an external global object is not that good. In C++ programming, global objects are generally frowned upon. In your case, it puts an undue burden on user code, such as having to reset the map object between two calls to canSum() ? Such a precaution is all too easily forgotten.

To solve the problem, you could use two C++ functions: an external one, and the internal one.

The external one takes care (internally) of the life cycle of the map object. The internal one just passes a pointer to the map object around.

C++ code for the internal function:

#include  <vector>
#include  <unordered_map>
#include  <iostream>

using  MyMapType = std::unordered_map<int, bool>;  // ad hoc map type
using  std::vector;

bool canSumWithMap(int goal, const vector<int>& vec, MyMapType& myMap)
{
    if (goal < 0)   return false;
    if (goal == 0)  return true;

    if (myMap[goal])
        return myMap[goal];

    for (auto& ell : vec)
    {
        if (canSumWithMap(goal-ell, vec, myMap)) 
        {
            myMap.insert({goal, true});
            return true;
        }
    }
    myMap.insert({goal, false});
    return false;
}

Please note that both the map and the vector are passed by reference, with a ‘&’ character, in order to avoid unnecessary copying during function calls.

C++ code for the external function, plus main program:

bool canSum(int goal, const vector<int>& vec)
{
    MyMapType  myMap;  // new map object initialized as empty

    bool rc = canSumWithMap(goal, vec, myMap);

    return rc;
    // myMap automagically deallocated here
}


using  std::cout;
using  std::endl;


int main()
{
    cout << std::boolalpha;  // want to print true or false rather than 0 or 1
    cout << canSum(7, {2,3})      << endl;
    cout << canSum(7, {5,3,4,7})  << endl;
    cout << canSum(7, {2,4})      << endl;  // no, can only do multiples of 2
    cout << canSum(8, {2,3,5})    << endl;
    cout << canSum(300, {7,14})   << endl;  // no, can only do multiples of 7

    return 0;
}

The above code runs successfully on my semi-vintage Intel x86-64 machine in 50 seconds, GNU C++ v10.2, with -O2 option.

Program output:

$ g++ --version
g++ (GCC) 10.2.1 20201125 (Red Hat 10.2.1-9)
Copyright © 2020 Free Software Foundation, Inc.
  ...  
$ 
$ g++ -O2 q66720598.cpp  -o q66720598.x
$ time q66720598.x
true
true
false
true
false

real   0m49,986s
user   0m49,841s
sys    0m0,003s
$

Performance measurements:

On my machine, your JavaScript codes runs in 19 seconds. And C++ with unordered maps takes 50 seconds, which is a bit disappointing.

Switching from unordered maps to plain (ordered) maps decreases the C++ time to 36 seconds, that’s still slower than JavaScript.

It takes a bit vector, defined like this:

    std::vector<bool>  myMap(goal+1, false);

to restore proper hierarchy 🙂 and make C++ 3 times faster than JavaScript, with a wall time of only 6 seconds.

So this is one of those situations where map objects, though functionally quite powerful and versatile, can be way slower than some ad hoc data structure.

Accepted Answer