Может ли функция std :: unordered_map :: reha sh () уменьшить коллизию ha sh? - PullRequest
Новая
       16

Может ли функция std :: unordered_map :: reha sh () уменьшить коллизию ha sh?

0 голосов
/ 13 января 2020

Я столкнулся с проблемой алгоритма, при которой истекло время ожидания с использованием unordered_map в c ++.

Ha sh Карты на других языках работали нормально с этой проблемой.

Поэтому я попытался улучшить производительность unordered_map с помощью функции reha sh. Я ожидал передать проблему, но не смог.

Как я понял, функция reha sh создаст больше блоков, что приведет к уменьшению коллизии ha sh.

Так что мой вопрос - функция reha sh действительно может уменьшить коллизию , Если это так, я могу сделать вывод, что основная причина тайм-аута заключается в этой проблеме.

Отредактировано ===========
проблема

[вопрос]
Проблема СУММ может быть сформулирована следующим образом: с учетом четырех списков A, B, C, D целочисленных значений, вычислите, сколько квадруплетов (a, b, c, d) ∈ A x B x C x D таково, что a + b + c + d = 0 , Далее мы предполагаем, что все списки имеют одинаковый размер n.

[формат ввода]
Первая строка ввода содержит размер списков n (это значение может достигать 4000 ). Затем у нас есть n строк, содержащих четыре целочисленных значения (с абсолютным значением, равным 228), которые принадлежат соответственно A, B, C и D.

и моему коду ... 

using namespace std;


#define SIZE 4000

int A[SIZE];
int B[SIZE];
int C[SIZE];
int D[SIZE];

int main(void){
    int N;
    scanf("%d", &N);

    for(int i=0; i <N;i++){
        scanf("%d %d %d %d", &A[i], &B[i], &C[i], &D[i]);
    }

    unordered_map<int, int> LeftMap; // store all result of A[i] + B[i]
    //LeftMap.rehash(1000000);
    unordered_map<int, int> RightMap; // store all result of C[i] + D[i]
    unordered_map<int, int>::iterator iter;
    unordered_map<int, int>::iterator iter2;

    int k;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            k = A[i]+B[j];

            iter = LeftMap.find(k);
            if(iter == LeftMap.end())
                LeftMap.insert({k, 1});
            else
                iter->second++;

            k = C[i]+D[j];

            iter = RightMap.find(k);
            if(iter == RightMap.end())
                RightMap.insert({k, 1});
            else
                iter->second++;
        }
    }

    int sum =0;
    for(iter = RightMap.begin(); iter != RightMap.end(); ++iter){
        iter2 = LeftMap.find((iter->first)* -1);
        if(iter2 != LeftMap.end()){
            sum+= iter->second * iter2->second;
        }
    }

    printf("%d", sum);


    return 0;
}
...