c++ - 使用 unordered_map 求解 2-sum
c++ - Solution to 2-sum using unordered_map
好的，所以我正在尝试解决 C++ 中的 2-SUM 问题。给定一个包含 1000000 个任意顺序数字的文件，我需要确定是否存在总和为 t 其中 t is each of [-10000, 10000] 的整数对。所以这基本上是 2-SUM 问题。
所以，我用 C++ 编写了我的解决方案，其中我使用 unordered_map 作为我的散列 table。我确保哈希 table 的低 load。但这仍然需要大约 1hr 15mins 才能完成（成功）。现在，我想知道它是否应该那么慢。进一步降低负载因子并没有带来任何可观的性能提升。
我不知道在哪里可以优化代码。我尝试了不同的负载系数，没有帮助。这是来自 MOOC 的问题，人们已经能够使用相同的散列 table 方法在大约 30 分钟内完成此问题。任何人都可以帮助我使这段代码更快。或者至少提示代码可能在哪里变慢。
这是代码 -
#include <iostream>
#include <unordered_map>
#include <fstream>
int main(int argc, char *argv[]){
if(argc != 2){
std::cerr << "Usage: ./2sum <filename>" << std::endl;
exit(1);
}
std::ifstream input(argv[1]);
std::ofstream output("log.txt");
std::unordered_map<long, int> data_map;
data_map.max_load_factor(0.05);
long tmp;
while(input >> tmp){
data_map[tmp] += 1;
}
std::cerr << "input done!" << std::endl;
std::cerr << "load factor " << data_map.load_factor() << std::endl;
//debug print.
for(auto iter = data_map.begin(); iter != data_map.end(); ++iter){
output << iter->first << " " << iter->second << std::endl;
}
std::cerr << "debug print done!" << std::endl;
//solve
long ans = 0;
for(long i = -10000; i <= 10000; ++i){
//try to find a pair whose sum = i.
//debug print.
if(i % 100 == 0)
std::cerr << i << std::endl;
for(auto iter = data_map.begin(); iter != data_map.end(); ++iter){
long x = iter->first;
long y = i - x;
if(x == y)
continue;
auto search_y = data_map.find(y);
if(search_y != data_map.end()){
++ans;
break;
}
}
}
std::cout << ans << std::endl;
return 0;
}
您可以提前预订 space 的 unordered 地图。它应该会稍微提高性能
先对数组进行排序，然后对数组中的每个元素进行排序，然后使用二进制搜索找到使其更接近 -10000 的数字，然后继续 "right" 直到总和达到 +10000
这样你将避免遍历数组 20000 次。
在所有和数均等概率的统一集上，以下将在几秒钟内完成。否则，对于任何遗漏的金额，在我的笔记本电脑上大约需要 0.75 秒来检查遗漏的金额。
与 OP 的代码相比，该解决方案有一个小的改进：检查重复项并消除它们。
然后通过一个Monte Carlo启发式打开：对于总数的1%左右，从集合中随机抽取一个，搜索[minSum, maxSum]范围内的所有和可以做出有一个术语作为随机选择的数字，其余的。这将预填充 sums 集...比如... 'sum that can be found trivially'。在我的测试中，使用在 -10M 和 10M 之间随机生成的 1M 数字，这是必要的一步，需要几秒钟。
对于病态数字分布，其中一些总和值缺失（或未通过随机启发式找到），第二部分对未找到的 sum 值使用有针对性的穷举搜索，与 OP 中的解决方案非常相似。
对random/Monte Carlo heuristic的额外解释（以解决@AneeshDandime 的评论）：
Though i do not fully understand it at the moment
嗯，很简单。可以这样想：天真的方法是获取所有输入值并将它们成对相加，但只保留 [-10k, 10k] 中的和。然而，它非常昂贵（O[N^2]）。一个直接的改进是：选择一个值 v0，然后确定其他哪些 v1 值有机会给出 [-10k, 10k] 范围内的总和。如果输入值是排序的，就更简单了：只需要在[-10k-v0, 10k-v0]中select v1-s；一个很好的改进，但如果您将此作为唯一方法，则穷举搜索仍然是 O(log2(N)N[-10k, 10k])。
但是，这种方法仍然有它的价值：如果输入值是均匀分布的，它会很快用最常见的值填充known sums集合（并且将剩下的时间花在寻找不常见或缺失的 sum 值上）。
要大写，而不是使用这个'直到最后，可以继续进行有限数量的步骤，希望填充大部分总和。之后，我们可以切换焦点，输入'targeted search for sum values'，但仅限于这一步没有找到的sum值。
[已编辑：更正了上一个错误。现在算法在输入中出现多次或单次出现的值方面是稳定的]
#include <algorithm>
#include <vector>
#include <random>
#include <unordered_set>
#include <unordered_map>
int main() {
typedef long long value_type;
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++
// substitute this with your input sequence from the file
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<value_type> initRnd(-5500, 10000000);
std::vector<value_type> sorted_vals;
for(ulong i=0; i<1000000; i++) {
int rnd=initRnd(gen);
sorted_vals.push_back(rnd);
}
std::cout << "Initialization end" << std::endl;
// end of input
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++
// use some constants instead of magic values
const value_type sumMin=-10000, sumMax=10000;
// Mapping val->number of occurrences
std::unordered_map<value_type, size_t> hashed_vals;
for(auto val : sorted_vals) {
hashed_vals[val]=hashed_vals[val]++;
}
// retain only the unique values and sort them
sorted_vals.clear();
for(auto val=hashed_vals.begin(); val!=hashed_vals.end(); ++val) {
sorted_vals.push_back(val->first);
}
std::sort(sorted_vals.begin(), sorted_vals.end());
// Store the encountered sums here
std::unordered_set<int> sums;
// some 1% iterations, looking at random for pair of numbers which will contribute with
// sum in the [-10000, 10000] range, and we'll collect those sums.
// We'll use the sorted vector of values for this purpose.
// If we are lucky, most of the sums (if not all) will be already filled in
std::uniform_int_distribution<size_t> rndPick(0, sorted_vals.size());
size_t numRandomPicks=size_t(sorted_vals.size()*0.1);
if(numRandomPicks > 75000) {
numRandomPicks=75000;
}
for(size_t i=0; i<numRandomPicks;i++) {
// pick a value index at random
size_t randomIx=rndPick(gen);
value_type val=sorted_vals[randomIx];
// now search for the values between -val-minSum and -val+maxSum;
auto low=std::lower_bound(sorted_vals.begin(), sorted_vals.end(), sumMin-val);
if(low==sorted_vals.end()) {
continue;
}
auto high=std::upper_bound(sorted_vals.begin(), sorted_vals.end(), sumMax-val);
if(high==sorted_vals.begin()) {
continue;
}
for(auto rangeIt=low; rangeIt!=high; rangeIt++) {
if(*rangeIt!=val || hashed_vals[val] > 1) {
// if not the same as the randomly picked value
// or if it is the same but that value occurred more than once in input
auto sum=val+*rangeIt;
sums.insert(sum);
}
}
if(sums.size()==size_t(sumMax-sumMin+1)) {
// lucky us, we found them all
break;
}
}
// after which, if some sums are not present, we'll search for them specifically
if(sums.size()!=size_t(sumMax-sumMin+1)) {
std::cout << "Number of sums still missing: "
<< size_t(sumMax-sumMin+1)-sums.size()
<< std::endl
;
for(int sum=sumMin; sum<=sumMax; sum++) {
if(sums.find(sum)==sums.end()) {
std::cout << "looking for sum: " << sum ;
// we couldn't find the sum, so we'll need to search for it.
// We'll use the unique_vals hash map this time to search for the other value
bool found=false;
for(auto i=sorted_vals.begin(); !found && i!=sorted_vals.end(); ++i) {
value_type v=*i;
value_type other_val=sum-v;
if( // v---- either two unequal terms to be summed or...
(other_val != v || hashed_vals[v] > 1) // .. the value occurred more than once
&& hashed_vals.find(other_val)!=hashed_vals.end() // and the other term exists
) {
// found. Record it as such and break
sums.insert(sum);
found=true;
}
}
std::cout << (found ? " found" : " not found") << std::endl;
}
}
}
std::cout << "Total number of distinct sums found: " << sums.size() << std:: endl;
}
好的，所以我正在尝试解决 C++ 中的 2-SUM 问题。给定一个包含 1000000 个任意顺序数字的文件，我需要确定是否存在总和为 t 其中 t is each of [-10000, 10000] 的整数对。所以这基本上是 2-SUM 问题。
所以，我用 C++ 编写了我的解决方案，其中我使用 unordered_map 作为我的散列 table。我确保哈希 table 的低 load。但这仍然需要大约 1hr 15mins 才能完成（成功）。现在，我想知道它是否应该那么慢。进一步降低负载因子并没有带来任何可观的性能提升。
我不知道在哪里可以优化代码。我尝试了不同的负载系数，没有帮助。这是来自 MOOC 的问题，人们已经能够使用相同的散列 table 方法在大约 30 分钟内完成此问题。任何人都可以帮助我使这段代码更快。或者至少提示代码可能在哪里变慢。
这是代码 -
#include <iostream>
#include <unordered_map>
#include <fstream>
int main(int argc, char *argv[]){
if(argc != 2){
std::cerr << "Usage: ./2sum <filename>" << std::endl;
exit(1);
}
std::ifstream input(argv[1]);
std::ofstream output("log.txt");
std::unordered_map<long, int> data_map;
data_map.max_load_factor(0.05);
long tmp;
while(input >> tmp){
data_map[tmp] += 1;
}
std::cerr << "input done!" << std::endl;
std::cerr << "load factor " << data_map.load_factor() << std::endl;
//debug print.
for(auto iter = data_map.begin(); iter != data_map.end(); ++iter){
output << iter->first << " " << iter->second << std::endl;
}
std::cerr << "debug print done!" << std::endl;
//solve
long ans = 0;
for(long i = -10000; i <= 10000; ++i){
//try to find a pair whose sum = i.
//debug print.
if(i % 100 == 0)
std::cerr << i << std::endl;
for(auto iter = data_map.begin(); iter != data_map.end(); ++iter){
long x = iter->first;
long y = i - x;
if(x == y)
continue;
auto search_y = data_map.find(y);
if(search_y != data_map.end()){
++ans;
break;
}
}
}
std::cout << ans << std::endl;
return 0;
}
您可以提前预订 space 的 unordered 地图。它应该会稍微提高性能
先对数组进行排序，然后对数组中的每个元素进行排序，然后使用二进制搜索找到使其更接近 -10000 的数字，然后继续 "right" 直到总和达到 +10000
这样你将避免遍历数组 20000 次。
在所有和数均等概率的统一集上，以下将在几秒钟内完成。否则，对于任何遗漏的金额，在我的笔记本电脑上大约需要 0.75 秒来检查遗漏的金额。
与 OP 的代码相比，该解决方案有一个小的改进：检查重复项并消除它们。
然后通过一个Monte Carlo启发式打开：对于总数的1%左右，从集合中随机抽取一个，搜索[minSum, maxSum]范围内的所有和可以做出有一个术语作为随机选择的数字，其余的。这将预填充 sums 集...比如... 'sum that can be found trivially'。在我的测试中，使用在 -10M 和 10M 之间随机生成的 1M 数字，这是必要的一步，需要几秒钟。
对于病态数字分布，其中一些总和值缺失（或未通过随机启发式找到），第二部分对未找到的 sum 值使用有针对性的穷举搜索，与 OP 中的解决方案非常相似。
对random/Monte Carlo heuristic的额外解释（以解决@AneeshDandime 的评论）：
Though i do not fully understand it at the moment
嗯，很简单。可以这样想：天真的方法是获取所有输入值并将它们成对相加，但只保留 [-10k, 10k] 中的和。然而，它非常昂贵（O[N^2]）。一个直接的改进是：选择一个值 v0，然后确定其他哪些 v1 值有机会给出 [-10k, 10k] 范围内的总和。如果输入值是排序的，就更简单了：只需要在[-10k-v0, 10k-v0]中select v1-s；一个很好的改进，但如果您将此作为唯一方法，则穷举搜索仍然是 O(log2(N)N[-10k, 10k])。
但是，这种方法仍然有它的价值：如果输入值是均匀分布的，它会很快用最常见的值填充known sums集合（并且将剩下的时间花在寻找不常见或缺失的 sum 值上）。
要大写，而不是使用这个'直到最后，可以继续进行有限数量的步骤，希望填充大部分总和。之后，我们可以切换焦点，输入'targeted search for sum values'，但仅限于这一步没有找到的sum值。
[已编辑：更正了上一个错误。现在算法在输入中出现多次或单次出现的值方面是稳定的]
#include <algorithm>
#include <vector>
#include <random>
#include <unordered_set>
#include <unordered_map>
int main() {
typedef long long value_type;
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++
// substitute this with your input sequence from the file
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<value_type> initRnd(-5500, 10000000);
std::vector<value_type> sorted_vals;
for(ulong i=0; i<1000000; i++) {
int rnd=initRnd(gen);
sorted_vals.push_back(rnd);
}
std::cout << "Initialization end" << std::endl;
// end of input
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++
// use some constants instead of magic values
const value_type sumMin=-10000, sumMax=10000;
// Mapping val->number of occurrences
std::unordered_map<value_type, size_t> hashed_vals;
for(auto val : sorted_vals) {
hashed_vals[val]=hashed_vals[val]++;
}
// retain only the unique values and sort them
sorted_vals.clear();
for(auto val=hashed_vals.begin(); val!=hashed_vals.end(); ++val) {
sorted_vals.push_back(val->first);
}
std::sort(sorted_vals.begin(), sorted_vals.end());
// Store the encountered sums here
std::unordered_set<int> sums;
// some 1% iterations, looking at random for pair of numbers which will contribute with
// sum in the [-10000, 10000] range, and we'll collect those sums.
// We'll use the sorted vector of values for this purpose.
// If we are lucky, most of the sums (if not all) will be already filled in
std::uniform_int_distribution<size_t> rndPick(0, sorted_vals.size());
size_t numRandomPicks=size_t(sorted_vals.size()*0.1);
if(numRandomPicks > 75000) {
numRandomPicks=75000;
}
for(size_t i=0; i<numRandomPicks;i++) {
// pick a value index at random
size_t randomIx=rndPick(gen);
value_type val=sorted_vals[randomIx];
// now search for the values between -val-minSum and -val+maxSum;
auto low=std::lower_bound(sorted_vals.begin(), sorted_vals.end(), sumMin-val);
if(low==sorted_vals.end()) {
continue;
}
auto high=std::upper_bound(sorted_vals.begin(), sorted_vals.end(), sumMax-val);
if(high==sorted_vals.begin()) {
continue;
}
for(auto rangeIt=low; rangeIt!=high; rangeIt++) {
if(*rangeIt!=val || hashed_vals[val] > 1) {
// if not the same as the randomly picked value
// or if it is the same but that value occurred more than once in input
auto sum=val+*rangeIt;
sums.insert(sum);
}
}
if(sums.size()==size_t(sumMax-sumMin+1)) {
// lucky us, we found them all
break;
}
}
// after which, if some sums are not present, we'll search for them specifically
if(sums.size()!=size_t(sumMax-sumMin+1)) {
std::cout << "Number of sums still missing: "
<< size_t(sumMax-sumMin+1)-sums.size()
<< std::endl
;
for(int sum=sumMin; sum<=sumMax; sum++) {
if(sums.find(sum)==sums.end()) {
std::cout << "looking for sum: " << sum ;
// we couldn't find the sum, so we'll need to search for it.
// We'll use the unique_vals hash map this time to search for the other value
bool found=false;
for(auto i=sorted_vals.begin(); !found && i!=sorted_vals.end(); ++i) {
value_type v=*i;
value_type other_val=sum-v;
if( // v---- either two unequal terms to be summed or...
(other_val != v || hashed_vals[v] > 1) // .. the value occurred more than once
&& hashed_vals.find(other_val)!=hashed_vals.end() // and the other term exists
) {
// found. Record it as such and break
sums.insert(sum);
found=true;
}
}
std::cout << (found ? " found" : " not found") << std::endl;
}
}
}
std::cout << "Total number of distinct sums found: " << sums.size() << std:: endl;
}