Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/11: Рейтинг темы: голосов - 11, средняя оценка - 5.00
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
1

Хеш-таблица (метод цепочек)

26.11.2015, 06:44. Просмотров 1950. Ответов 6

Дано: файл на 1ккк больших чисел.
Задача:
1. Построить хеш-таблицу любым методом.
2. Обчислить количество возможных разных значений S = x + y в диапазоне [-1000; 1000], где х и у -- два разных числа с файла которые удовлетворяют условие S.

Выполнение:

Хеш-функция:
C++
1
2
3
4
5
6
int Hash(lli k) // хеш-функция
{
    if (k < 0)  // <============== КАК ЕЩЕ МОЖНО ИНТЕРПРЕТИРОВАТЬ ОТРИЦАТЕЛЬНЫЕ ЧИСЛА???
        k *= -1;
    return k % M;
}
Функция вставки:
C++
1
2
3
4
void ChainedHashInsert(list<lli> *& HashList, lli x) // функция вставки новых значений
{
    HashList[Hash(x)].push_front(x);
}
Функция поиска по значению:
C++
1
2
3
4
5
6
7
8
9
10
11
12
lli ChainedHashSearch(list<lli> * HashList, lli x) // функция поиска по значению (возвращает это же значение в случае успеха)
{
    int k = Hash(x);
    list<lli>::iterator it = HashList[k].begin();
    while (it != HashList[k].end())
    {
        if (*it == x)
            return x;
        ++it;
    }
    return NULL;
}
ФУНКЦИЯ ПОИСКА S:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void SearchSum(list<lli> * HashList, int &n, vector<int> * pVec,  int Max) // <+============ Поиск значения S = x + y
{
    lli y(0);
    int Min = Max * (-1);
    list<lli>::iterator it;
    for (int i(0); i < M; ++i) // 1. цикл: Перебираем все ячейке хеш-таблици
    {
        it = HashList[i].begin();
        while (it != HashList[i].end()) // 2. цикл: Перебираем список в поточной ячейке хеш-таблици
        {
            for (int S(Min); S <= Max; ++S) // 3.  цикл: Перебираем все S в диапазоне от -1000 до 1000
            {
                y = S - (*it);
                if (ChainedHashSearch(HashList, y) != NULL) // проверка, существует значение Y или нет
                {
                    ++n; // счетчик подходящих ответов
                    pVec->push_back(S); // записываем значение S для подальшого отбора уникальных S
                    cout << " n = " << n << ",  " << y << " + " << *it << " = " << S << endl;
                }
            }
            ++it;
        }
    }
}
Весь код программы:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
// week6.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <io.h>
#include <list>
#include <ctime>
#include <vector>
 
 
static const int MAX_WORDS = 1000000;
static const int M = 196608;//24576; //по 4 списка
 
typedef long long lli;
 
void ReadFile(char *& pSymb, int * cSize, char * path = "E:\\input_06.txt");
void CharToInt(char * pSymb, int cSize, lli * pAr);
int Hash(lli k);
void ChainedHashInsert(list<lli> *& HashList, lli x);
lli ChainedHashSearch(list<lli> * HashList, lli x);
void SearchSum(list<lli> * HashList, int &n, vector<int> * pVec, int S = 1000);
void Del(vector<int> * pV);
 
 
int main()
{
    clock_t Start, End, tSec, tMin; // для замера времени
    char * pSymbReadF;
    int cSizeF(0);
    lli * pAr = new lli[MAX_WORDS];
    ReadFile(pSymbReadF, &cSizeF);  // читаем файл
    CharToInt(pSymbReadF, cSizeF, pAr); // переводим строки в числа
 
    list<lli> * HashList = new list<lli>[M]; // создаем хеш-таблицу
    vector<int> Answer;  // вектор куда запишим все подходящие S 
    Answer.reserve(100); 
    for (int i(0); i < MAX_WORDS; ++i)  // инициализируем хеш-таблицу 
        ChainedHashInsert(HashList, pAr[i]); 
    
    int n(0);
    Start = clock();
    SearchSum(HashList, n, &Answer);  // <========== поиск S (S = x + y, [-1000 <= S <= 1000])
    End = clock();
    cout << "   nCount = " << n << endl;
    tSec = (End - Start) / CLOCKS_PER_SEC;
    tMin = tSec / 60;
    tSec = tSec % 60;
    cout << "  TIME = " << tMin << "(m) " << tSec <<"(s) \n\n" << endl;
 
    Del(&Answer); // отбор уникальных значений S
    cout << " Answer = " << Answer.size() << endl;
    for (int i(0); i < Answer.size(); ++i)
        cout << i << "  -  " << Answer[i] << endl;
 
    delete[] HashList;
    delete[] pAr;
    return 0;
}
 
void ReadFile(char *& pSymb, int * cSize, char * path)
{
    FILE * f;
    fopen_s(&f, path, "rt");
    if (f == NULL)
        cout << "\n ERROR OPEN! " << endl;
    int iID = _fileno(f);
    *cSize = _filelength(iID);
    pSymb = new char[*cSize];
    fread(pSymb, sizeof(char), *cSize, f);
    fclose(f);
}
 
void CharToInt(char * pSymb, int cSize, lli * pAr)
{
    int nCount(0);
    //char * pWords[MAX_WORDS], *pToken;
    char ** pWords = new char*[MAX_WORDS];
    char * pToken;
    pToken = strtok(pSymb, "\n");
    while (pToken != NULL && nCount < MAX_WORDS)
    {
        pWords[nCount++] = pToken;
        pToken = strtok(NULL, "\n");
    }
 
    for (int i(0); i < MAX_WORDS; ++i)
    {
        pAr[i] = atoll(pWords[i]);
    }
    delete[] pWords;
}
 
int Hash(lli k) // хеш-функция
{
    if (k < 0)  // <============== КАК ЕЩЕ МОЖНО ИНТЕРПРЕТИРОВАТЬ ОТРИЦАТЕЛЬНЫЕ ЧИСЛА???
        k *= -1;
    return k % M;
}
 
void ChainedHashInsert(list<lli> *& HashList, lli x) // функция вставки новых значений
{
    HashList[Hash(x)].push_front(x);
}
 
lli ChainedHashSearch(list<lli> * HashList, lli x) // функция поиска по значению (возвращает это же значение в случае успеха)
{
    int k = Hash(x);
    list<lli>::iterator it = HashList[k].begin();
    while (it != HashList[k].end())
    {
        if (*it == x)
            return x;
        ++it;
    }
    return NULL;
}
 
 
void SearchSum(list<lli> * HashList, int &n, vector<int> * pVec,  int Max) // <+============ Поиск значения S = x + y
{
    lli y(0);
    int Min = Max * (-1);
    list<lli>::iterator it;
    for (int i(0); i < M; ++i) // 1. цикл: Перебираем все ячейке хеш-таблици
    {
        it = HashList[i].begin();
        while (it != HashList[i].end()) // 2. цикл: Перебираем список в поточной ячейке хеш-таблици
        {
            for (int S(Min); S <= Max; ++S) // 3.  цикл: Перебираем все S в диапазоне от -1000 до 1000
            {
                y = S - (*it);
                if (ChainedHashSearch(HashList, y) != NULL) // проверка, существует значение Y или нет
                {
                    ++n; // счетчик подходящих ответов
                    pVec->push_back(S); // записываем значение S для подальшого отбора уникальных S
                    cout << " n = " << n << ",  " << y << " + " << *it << " = " << S << endl;
                }
            }
            ++it;
        }
    }
}
 
void Del(vector<int> * pV) // функция удаления лишних (не уникальных) значений S 
{
    vector<int>::iterator it, it2;
    for (it = pV->begin(); it != pV->end(); ++it)
    {
        for (it2 = it + 1; it2 != pV->end(); ++it2)
        {
            if (*it == *it2)
            {
                pV->erase(it2);
                it = pV->begin();
                it2 = it + 1;
            }
        }
    }
}



Собственно программа выдала верный результат и задание, так сказать, пройдено. Но есть маленькое НО...
Функция SearchSum работала больше 4 часа.

Возникает несколько вопросов:
1. Насколько адекватный алгоритм функции SearchSum?
2. Как можно улучшить эту функцию или алгоритм построения хеш-таблицы?
3. Какие есть стандартные методы/функции/библиотеки для построения хеш-таблиц?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2015, 06:44
Ответы с готовыми решениями:

Хеш таблица с функцией (метод цепочек)
1) Не смотрите на хеш функцию, она наитупейшая, я еще над ней не работал....

Хэш-таблица. Метод цепочек. C++
Уважаемые, программисты, задание звучит так: &quot;Таблица строится по методу...

Хэш-таблица (метод цепочек)
Пишу частотный словарь текста: Массив списков узлов. В узле значение и частота...

Хэш - таблица методом цепочек
Всем привет! Есть задание реализовать хеш-таблицу методом цепочек + с хэш -...

Хэширование метод цепочек
Помогите пожалуйста с заданием, даже не знаю с чего тут начать. Построить...

6
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
26.11.2015, 06:46  [ТС] 2
Вот файл с 1ккк числами и скрин результата работы программы.
0
Миниатюры
Хеш-таблица (метод цепочек)  
Вложения
Тип файла: zip input_06.txt.zip (5.50 Мб, 12 просмотров)
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
26.11.2015, 06:49  [ТС] 3
Так же есть тестовый файл из 100000 числами. Для него правильный ответ 22 уникальных S.
0
Вложения
Тип файла: zip test_06.txt.zip (563.8 Кб, 13 просмотров)
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
28.11.2015, 06:57  [ТС] 4
У некоторых выполнение этой программы заняло 4-5 часов (видимо алгоритм решения подобный моему).
Но были люди, которые хвастались, что их программа все сделала за время до 1 минуты!

Добавлено через 5 часов 52 минуты
Может перенести тему в С++ для экспертов?

Добавлено через 17 часов 41 минуту
Я так понял никто ничем мне не поможет.

Добавлено через 10 часов 10 минут
Просто удивительно...

Добавлено через 14 часов 20 минут
Ей ей ей....
0
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
30.11.2015, 17:59  [ТС] 5
...хоть бы перекинули тему куда то
0
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
04.01.2016, 06:08  [ТС] 6
Ап, по прежнему актуально.
0
Renji
2123 / 1561 / 476
Регистрация: 05.06.2014
Сообщений: 4,518
04.01.2016, 07:46 7
Но были люди, которые хвастались, что их программа все сделала за время до 1 минуты!
Как же я горд за свой старенький суперкомпьютер, обсчитывающий ваш файлик на 100 000 чисел за секунду.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cassert>
 
using namespace std;
 
void create_hash()
{
    //впишите сюда код создания хеша
    //конкретная реализация роли не играет, так как нафиг здесь не нужна
}
 
int main()
{
    create_hash();
 
    std::vector<int64_t>array;
    bool res[2001]={false};
    std::ifstream stream("test_06.txt");
    for(int64_t buf;stream>>buf;)
        array.push_back(buf);
    std::sort(array.begin(),array.end());
    for(std::vector<int64_t>::iterator pos=array.begin();pos!=array.end()-1;++pos)
    {
        for(std::vector<int64_t>::iterator pos1=std::lower_bound(pos+1,array.end(),-1000-*pos);
            pos1!=array.end() && *pos+*pos1<=1000;
            ++pos1)
        {
            assert(*pos+*pos1>=-1000);
            res[*pos+*pos1+1000]=true;
        }
    }
 
    int count=0;
    for(int i=0;i<2001;++i)
        if(res[i])
            ++count;
    std::cout<<count<<std::endl;
    return 0;
}
1
04.01.2016, 07:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.01.2016, 07:46

Хеш Таблица
я хочу, чтобы у меня был массив структур, каждая из которых содержала некоторое...

Хеш таблица
Нужно написать прогу которая подсчитает количество слов, с помощью хеш таблицы....

Хеш-таблица
Почитав теорию найденную в поисковике, не особо понял как реализовать их на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru