Реализация хеширования работает очень медленно - PullRequest
Новая
       111

Реализация хеширования работает очень медленно

0 голосов
/ 01 мая 2020

Я новичок в ха sh таблицах и сам пытался их реализовать. Но мой метод, кажется, работает очень медленно.

Вопрос был:

Цель этой проблемы - реализовать вариант алгоритма 2-SUM, описанный в лекциях этой недели. .

Файл содержит 1 миллион целых чисел, как положительных, так и отрицательных (может быть несколько повторений!). Это ваш массив целых чисел, в i-й строке файла указан i-й запись массива.

Ваша задача состоит в том, чтобы вычислить количество целевых значений t в интервале [-10000,10000] (включительно) таким образом, чтобы существовали различные числа x, y в входной файл, который удовлетворяет x + y = t. (ПРИМЕЧАНИЕ: для обеспечения отличимости требуется сложение алгоритма из лекции в одну строку.)

Напишите свой числовой ответ c (целое число от 0 до 20001) в предоставленном месте.

ДОПОЛНИТЕЛЬНАЯ ЗАДАЧА: Если эта проблема слишком проста для вас, попробуйте реализовать для нее собственную таблицу ha sh. Например, вы можете сравнить производительность при подходах цепочки и открытой адресации для разрешения коллизий.

Код, который я написал, решил проблему более чем за 10 минут !!! Я не могу понять, как я могу ускорить это. Это мой код: 

#include<bits/stdc++.h>

using namespace std;

struct entry
{
    long long val;
    entry* next;
};

int hf(long long x)
{
    int p= x%2000003;
    if(p>=0)return p;
    return -1*p;
}

void addentry(int y,long long x,vector<long long> arr[])
{
    int flag=0;
    for(long long t:arr[y])
    {
        if(t==x)
        {
            flag=1;
            break;
        }
    }
    if(flag==0)
        arr[y].push_back(x);
}

bool isthere(long long x,vector<long long> arr[])
{
    int y=hf(x);
    for(long long t:arr[y])
    {
        if(t==x) return true;
    }
    return false;
}

bool sd(vector<long long> arr[],int t,int a[],int size)
{
    for(int i=0;i<size;i++)
    {
        {
            if((a[i])>=t){continue;}
            if(isthere(t-(a[i]),arr))
            {
                return true;
            }

        }
    }
    return false;
}
int main()
{
    ifstream f("F:\sum1.txt");
    vector<long long> arr[2000003];
    int a[1000007];
    int size=0;
    long long x;
    while(f>>x)
    {
        int y=hf(x);
        addentry(y,x,arr);
    }
    for(int i=0;i<2000003;i++)
    {
        for(long long t:arr[i])
        {
            a[size]=t;
            size++;
        }
    }
    int sum=0;
    for(int t=-10000;t<=10000;t++)
    {
        if(sd(arr,t,a,size))sum++;
    }
    cout<<endl<<sum;
}

Может кто-нибудь помочь мне с ошибкой или как я могу это исправить?

РЕДАКТИРОВАТЬ: я не использую запись структуры и забыл чтобы стереть его из кода.

Я использовал arr в качестве сегментов для хэширования, а также использовал другой массив a для хранения различных элементов в таблице ha sh. Я использовал размер для хранения количества элементов, присутствующих в массиве.

Функция hf принимает число в качестве ввода и возвращает вывод функции ha sh этого числа.

Функция addentry принимает значение элемента, сегмент, которому оно принадлежит, и массив arr, представляющий таблицу ha sh, и добавляет этот элемент в таблицу ha sh.

Функция возвращает, если элемент присутствует в таблице ha sh.

Функция sd принимает массив arr, целое число t, массив a и количество уникальных элементов в размере таблицы ha sh и возвращает, если сумма любой отличной пары ha sh карта т. Чтобы избежать повторения и не получить одинаковые элементы, проверяются только элементы, которые меньше t. Для каждого проверенного элемента a [i] выполняется поиск элемента ta на карте i.

Как предположил Джим Мишель, я рассчитал количество сегментов, содержащих более 10 элементов. Там не было таких элементов. Было 29 ведер с более чем 5 элементами. Я думаю, что с этими числами функция ha sh создает какие-либо проблемы. Я не думаю, что нахождение среднего числа элементов в корзине полезно, поскольку оно будет зависеть только от количества отдельных элементов и количества корзин.

...