c++ - c++-使用unordered_map解决2和的方法

Question

好的，我正在尝试解决c++中的2-SUM问题。给定一个任意顺序的1000000数字文件，我需要确定是否存在整数对，其和为t其中t is each of [-10000, 10000]。所以这基本上是2-SUM问题。

因此，我用C++编写了解决方案，其中我使用unordered_map作为哈希表。我确保哈希表上的load低。但这仍然需要1hr 15mins完成(成功)。现在，我想知道是否应该那么慢。进一步降低负载系数并不会显着提高性能。

我不知道在哪里可以优化代码。我尝试了不同的负载系数，但无济于事。这是来自MOOC的问题，人们已经能够使用相同的哈希表方法在大约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;
}

Answer 1

在所有可能性均等的统一集上，以下将在几秒钟内完成。否则，对于任何遗漏的款项，我的笔记本电脑上大约需要0.75秒来检查遗漏的款项。

与OP的代码相比，该解决方案有一点改进:检查重复项并消除重复项。

然后通过蒙特卡罗启发式方法打开:对于总数的大约1％，从集合中随机选择一个，然后搜索[minSum, maxSum]范围内的所有总和，该总和可以使一个术语为随机选择的数字，其余为他们。这将使用...说...'可以轻易找到的总和'预先填充sums集。在我的测试中，使用-10M到10M之间仅生成1M的数字，这是必要的一步，需要花费几秒钟。

对于缺少某些和值(或未通过随机启发式法找到的值)的病理数字分布，第二部分对未找到的sum值进行有针对性的详尽搜索，与odt_code值非常接近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]范围内的总和。如果对输入值进行了排序，则更加简单:您只需在v1中选择[-10k-v0, 10k-v0] -s即可；是一个很好的改进，但是如果您将此作为唯一方法，则穷举搜索仍将是O(log2(N)N [-10k，10k])。
但是，这种方法仍然有其值(value):如果输入值是均匀分布的，它将用最常用的值快速填充known sums集合(并花费其余时间尝试查找不频繁或缺少的sum值)。
为了大写，而不是最终使用大写字母，人们可以采取有限数量的步骤，以希望将大部分金额都用到。之后，我们可以切换焦点并输入“针对sum值的目标搜索”，但仅针对此步骤中未找到的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;
}