Search code examples
javascriptc++dynamic-programmingmemoization

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

This is what my canSum function needs to do:

Given a target sum x, return true iff it is possible to get that sum by adding elements from a given array, assuming array elements can be used any number of times.

Examples:

canSum(7, {2,3}) -> true
canSum(7, {2,4}) -> false

Below is the JavaScript code which I rewrote in C++. For some reason, even though I used memoization, the C++ version takes too long for big inputs.

The JavaScript code, which works fine:

const canSum = (targetSum, numbers, memo={}) => {
    if (targetSum === 0) return true;
    if (targetSum < 0) return false;
    for ( let num of numbers) {
        const remainder = targetSum - num;
        if (canSum( remainder, numbers, memo) === true) {
            return true;
        }
    }
    return false;
};


console.log(canSum(7, [2, 3])); // true
console.log(canSum(7, [5, 3, 4, 7])); // true
console.log(canSum(7, [2, 41])); // false
console.log(canSum(8, [2, 3, 5])); // true
console.log(canSum(300, [7, 14])); // false

My C++ code, which never gave any output for the last input item canSum(300, {7,14})

#include<bits/stdc++.h>
using namespace std;

unordered_map<int,bool> mymap;

bool canSum(int goal, vector<int> vec)
{
    if (goal<0)       return false;
    if (goal==0)      return true;
    if (mymap[goal])  return mymap[goal];

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

int main()
{
    cout<<canSum(7, {2,3})<<endl;
    cout<<canSum(7, {5,3,4,7})<<endl;
    cout<<canSum(7, {2,4})<<endl;
    cout<<canSum(8, {2,3,5})<<endl;
    cout<<canSum(300, {7,14})<<endl;

    return 0;
}

How can I optimize the C++ code, and why is the JavaScript code faster ?

Solution

  • 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.