为什么此解决方案在 JavaScript 中有效，但在 C++ 中花费的时间太长？ （动态规划）
Why does this solution works in JavaScript but takes too long in C++? (Dynamic Programming)
这就是我的 canSum 函数需要做的事情：
给定目标总和 x，return true 当且仅当可以通过从给定数组中添加元素来获得该总和，假设数组元素可以可以使用任意次数。
示例：
canSum(7, {2,3}) -> true
canSum(7, {2,4}) -> false
下面是我用 C++ 重写的 JavaScript 代码。出于某种原因，即使我使用了记忆，C++ 版本对于大输入来说花费的时间也太长了。
JavaScript 代码，工作正常：
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
我的 C++ 代码，它从未为最后一个输入项提供任何输出 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;
}
如何优化 C++ 代码，为什么 JavaScript 代码更快？
您的 JavaScript 和 C++ 代码示例之间的区别是：C++ 函数只有两个参数而不是 3 个，地图对象作为全局实体进行管理。
在某种意义上，只有 2 个参数是“The Right Thing”。无序映射是关于算法的一些内部必要性。为什么用户代码必须知道这一点？
如果有一天您决定使用 ordered 映射或集合或位向量，那为什么要强制用户代码更改它拥有的头文件列表#include ?
所以只有 2 个参数很好，但是将地图作为外部 全局对象 进行管理并不是那么好。在 C++ 编程中，全局对象通常不受欢迎。在您的情况下，它会给用户代码带来不应有的负担，例如必须在两次调用 canSum() 之间重置地图对象？这种预防措施很容易被遗忘。
要解决这个问题，您可以使用两个 C++ 函数：一个外部函数和一个内部函数。
外部负责（内部）地图对象的生命周期。内部的只是传递一个指向周围地图对象的指针。
内部函数的C++代码：
#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;
}
请注意，地图和向量都是通过 reference 传递的，带有 '&' 字符，以避免在函数调用期间进行不必要的复制。
外部函数的C++代码，加上主程序：
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;
}
以上代码在我的半老式 Intel x86-64 机器上成功运行了 50 秒，GNU C++ v10.2，带有 -O2 选项。
程序输出：
$ 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
$
性能测量：
在我的机器上，您的 JavaScript 代码运行时间为 19 秒。而带有无序映射的 C++ 需要 50 秒，这有点令人失望。
从无序映射切换到普通（有序）映射将 C++ 时间减少到 36 秒，这仍然比 JavaScript 慢。
需要一个位向量，定义如下：
std::vector<bool> myMap(goal+1, false);
恢复正确的层次结构 :-) 并使 C++ 比 JavaScript 快 3 倍，挂起时间仅为 6 秒。
所以这是地图对象的一种情况，虽然功能非常强大且用途广泛，但可能比某些 ad hoc 数据结构慢得多。
这就是我的 canSum 函数需要做的事情：
给定目标总和 x，return true 当且仅当可以通过从给定数组中添加元素来获得该总和，假设数组元素可以可以使用任意次数。
示例：
canSum(7, {2,3}) -> true
canSum(7, {2,4}) -> false
下面是我用 C++ 重写的 JavaScript 代码。出于某种原因，即使我使用了记忆，C++ 版本对于大输入来说花费的时间也太长了。
JavaScript 代码，工作正常：
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
我的 C++ 代码，它从未为最后一个输入项提供任何输出 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;
}
如何优化 C++ 代码，为什么 JavaScript 代码更快？
您的 JavaScript 和 C++ 代码示例之间的区别是：C++ 函数只有两个参数而不是 3 个，地图对象作为全局实体进行管理。
在某种意义上，只有 2 个参数是“The Right Thing”。无序映射是关于算法的一些内部必要性。为什么用户代码必须知道这一点？
如果有一天您决定使用 ordered 映射或集合或位向量，那为什么要强制用户代码更改它拥有的头文件列表#include ?
所以只有 2 个参数很好，但是将地图作为外部 全局对象 进行管理并不是那么好。在 C++ 编程中，全局对象通常不受欢迎。在您的情况下，它会给用户代码带来不应有的负担，例如必须在两次调用 canSum() 之间重置地图对象？这种预防措施很容易被遗忘。
要解决这个问题，您可以使用两个 C++ 函数：一个外部函数和一个内部函数。
外部负责（内部）地图对象的生命周期。内部的只是传递一个指向周围地图对象的指针。
内部函数的C++代码：
#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;
}
请注意，地图和向量都是通过 reference 传递的，带有 '&' 字符，以避免在函数调用期间进行不必要的复制。
外部函数的C++代码，加上主程序：
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;
}
以上代码在我的半老式 Intel x86-64 机器上成功运行了 50 秒，GNU C++ v10.2，带有 -O2 选项。
程序输出：
$ 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
$
性能测量：
在我的机器上，您的 JavaScript 代码运行时间为 19 秒。而带有无序映射的 C++ 需要 50 秒，这有点令人失望。
从无序映射切换到普通（有序）映射将 C++ 时间减少到 36 秒，这仍然比 JavaScript 慢。
需要一个位向量，定义如下：
std::vector<bool> myMap(goal+1, false);
恢复正确的层次结构 :-) 并使 C++ 比 JavaScript 快 3 倍，挂起时间仅为 6 秒。
所以这是地图对象的一种情况，虽然功能非常强大且用途广泛，但可能比某些 ad hoc 数据结构慢得多。