为什么 unordered_map 的执行速度比 look-ups 的二维向量慢 100 倍？

Question

我尝试为大型数据集实现背包算法。
二维向量解决方案非常适合大约 100 项的中型数据集。
由于二维向量对于涉及大约 1000 项的大型数据集不可行，我决定使用哈希表并根据需要缓存值。
我使用 hash_value() 从提升到散列 std::pair 进入 unordered_map.
但我不明白为什么这个解决方案比二维矢量解决方案。哈希表不是用于超快速查找的吗？
两种实现都无法在有限时间内处理大数据集。
我附上了代码和 "medium" 和 "large" 数据集。
该代码同时具有 unordered_map 和二维矢量实现，后者被注释掉。
如果有人能指出性能低下的原因并提出一些优化建议以便它能够处理大型数据集，那将非常有帮助。
输入文件的格式为。（例如）：

6 4 //重量，物品数量 3 4 2 3 4 2 4 3

最优解是8。

Download Link for Large dataset (1000 items)

Download Link for Medium dataset (100 items)

Download Link for Source Code

//代码如下：

//Headers，宏和全局变量：

#include<iostream>
#include<vector>
#include<algorithm>
#include<fstream>
#include<string>
#include<sstream>
#include<unordered_map>
#include<boost/functional/hash.hpp>
using namespace std;

typedef vector< vector<long long> > vii;
typedef vector< pair<int,int> > vp;
typedef pair<int,int> myPair;
typedef unordered_map< myPair, long long, boost::hash<myPair> > myMap;

vp elmnts;
//vii arr2d;
myMap arr;

//背包函数:

long long knapsack(int n, int w)
{
//arr2d.resize(n+1, vector<long long>(w+1));
int vi,wi;

for(int j=0; j<=w; ++j)
//  arr2d[0][j] = 0;
    arr.emplace(make_pair(0,j), 0);

for(int i=1; i<=n; ++i)
{
    vi = elmnts[i-1].first;
    wi = elmnts[i-1].second;

    for(int j=0; j<=w; ++j)
    //  arr2d[i][j] = (wi > j) ? arr2d[i-1][j] : max(arr2d[i-1][j], arr2d[i-1][j-wi] + vi);
        arr.emplace(make_pair(i,j), (wi > j) ? arr[make_pair(i-1,j)] : max(arr[make_pair(i-1,j)], arr[make_pair(i-1,j-wi)]+ vi));
}

//return arr2d[n][w];
return arr[make_pair(n,w)];
}

//主要功能

int main()
{
ifstream file("/home/tauseef/Desktop/DAA2/knapsack1.txt");
int n,w;
string line;
pair<int,int> elmnt;

getline(file, line);
stringstream ss(line);
ss >> w;
ss >> n;

while(getline(file, line))
{
    stringstream ss1(line);
    ss1 >> elmnt.first;
    ss1 >> elmnt.second;
    elmnts.push_back(elmnt);
}

cout<<"\nThe optimal solution is: "<<knapsack(n,w)<<endl;
file.close();
}

Answer 1

没想到差别这么大：在我的机器上数组版本比hash_map版本快100倍。但是转念一想...

你应该预料到地图会更慢 - 有很多开销：调用 make_pair，创建对象对，计算哈希，在地图中搜索它，构造 return 值，来回复制对象与仅查找值相反！

另一方面，您根本不会从切换到地图中获利，因为最后，正如现在编码的那样，您在你的地图在数组中。如果您从地图中遗漏一些元素，但您没有这样做，那么您的更改是有意义的。

但是您的代码中更大的问题是您使用维基百科中的伪多项式算法，它需要 O(n*W) 内存。这意味着您将需要 32GB 内存用于更大的测试用例，这可能意味着要用硬盘交换内存，具体取决于您的系统有多大并且变得非常慢。

解决方案是采用需要O(W)内存的算法版本：

long long knapsack(const vector<myPair> &objects, int W)
{
    vector<long long> bests(W+1, -1L);//-1 = this value is not reachable
    //the only possible configuration at start: an empty set, value is also 0
    bests[0]=0;


    for(const myPair &object:objects){//try out all objects
        int v = object.first;
        int w = object.second;
        //update all possible configurations:
        for(int cur=W;cur>=0;--cur){//backwards->object at most once in every configuration!
          int next=cur+w;
          if(bests[cur]!=-1 && next<=W)//consider only reachable configurations and discard too big weights
            bests[next]=std::max(bests[next], bests[cur]+v);
       }
    }

    return *max_element(bests.begin(), bests.end());
}

最重要的部分是我们向后遍历可能的配置，因此可以就地更新配置（更新的配置是在当前扫描中已经进行的配置）。

我想这个版本对于更大的情况应该需要不到 1 分钟的时间（考虑到输入有多大，这是相当合理的）。我不保证这没有错误，但希望你能理解它的要点。

为什么 unordered_map 的执行速度比 look-ups 的二维向量慢 100 倍？

Why does the unordered_map perform about 100 times slower than a 2d vector for look-ups?

c++

algorithm

stl

unordered-map

knapsack-problem