С Новым годом! Форум программистов, компьютерный форум, киберфорум
Visual C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.69/13: Рейтинг темы: голосов - 13, средняя оценка - 4.69
3 / 3 / 0
Регистрация: 25.09.2009
Сообщений: 122

Хеш-таблица, большие объёмы, переход от C++ Builder к Visual C++

06.12.2011, 12:05. Показов 2615. Ответов 17
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Пытаюсь реализовать быстрый поиск в больших объемах данных (порядка миллиарда строк, до 4 миллиардов точно), SQL-сервер уже проходили, нужно ещё быстрее! Остановил свой выбор на хэш-таблице. Есть некая таблица соответствия текстовой строки до 20 символов и ее идентификатор.
Нужно возвращать идентификатор, а если строка не найдена - создавать новую запись.
Делал на C++ Builder, упёрся в 32-bit ограничение, решил переделать под Visual C++ c 64-bit.
Есть ряд вопросов в комментариях исходника, помогите плиз.

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
struct Record
{
   char Data[20];
   unsigned int Key;
   Record *Next;
};
 
Record *Table
 
//поиск/добавление значения в таблицу
Record Lookup(char *data, unsigned int key, bool create)
{
   unsigned int h = Hash(data); // вычисление хэша строки - сама функция тривиальна и пропущена
   Record temp;
   // поиск по цепочке записей с одинаковыми хэш-суммами
   for(temp=Table[h]; temp!=NULL; temp = temp.Next) // в этой строке главный вопрос: как сделать проверку на проининциализированность элементов таблицы (temp!=NULL) значение temp не NULL, а вполне определенное значение (не так как на Builder)?
   {
       //тут идет поиск и, если нужно - создание новых значение
   }
 
}
 
unsigned int TableSize;
 
int _tmain(int argc, _TCHAR* argv[])
{
   TableSize = 10000; //это для примера, вообще длина порядка 1 млрд!
   // в этом месте открываем файл со значениями в формате Data\tKey\n
   FILE *inFile = _wfopen("file.txt", "rt");
   unsigned int key;
   char buffer[20]; // нужно ли делать длину 21 (под \0), если максимальная длина 20 символов?
   for(unsigned int i=0; i<TableSize;i++)
   {
      //тут считываем данные из файла
      fscanf(inFile, "%d\t%s\n", &key, &buffer);
      //ищем в таблице и размещаем, если не найдено
      Lookup(buffer, key, false);
   }
   delete[] Table;
   fclose(inFile);
   return 0;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
06.12.2011, 12:05
Ответы с готовыми решениями:

Большие объемы печати
Что посоветуете для офиса с большими объемами печати? Варианты: -Canon imageRUNNER 1435i -Canon i-SENSYS MF522x Если честно,...

DataSet и большие объемы данных
Доброе время суток. Имеем Borland C++ Builder (по части работы с данными и соотв. библиотек одно и то же). В базе, с которой работает...

Нужно передавать большие объёмы текстов
всем привет. Такая проблемка вылезла. Мне нужно передавать большие объёмы текстов через &lt;Input value='здесь переменная с большим...

17
 Аватар для oxotnik
1665 / 1134 / 80
Регистрация: 21.08.2008
Сообщений: 4,734
Записей в блоге: 1
06.12.2011, 12:10
через std::map не пробовал сделать?
0
3 / 3 / 0
Регистрация: 25.09.2009
Сообщений: 122
06.12.2011, 12:18  [ТС]
Цитата Сообщение от oxotnik Посмотреть сообщение
через std::map не пробовал сделать?
нет, я пока даже не знаю, что это такое, сейчас почитаю, спасибо
0
 Аватар для oxotnik
1665 / 1134 / 80
Регистрация: 21.08.2008
Сообщений: 4,734
Записей в блоге: 1
06.12.2011, 12:26
Code
1
2
3
4
5
6
7
8
9
10
std::map<unsigned int, std::string>MyMap;
MyMap[0] = "some string 1";
MyMap[1] = "some string 2";
void find(unsigned int key, string data)
{
   if (MyMap.find(key) != MyMap.end()) // если такой ключ есть
   return MyMap[key];
   else
   MyMap[key] = data;
}
1
3 / 3 / 0
Регистрация: 25.09.2009
Сообщений: 122
06.12.2011, 12:42  [ТС]
Очень признателен за исходник, но ест ли у тебя уверенность в производительности/оптимальности std::map на таких объёмах (1-4 миллиарда строк)? Я как раз собирался уйти от универсальных предлагаемых реализаций, HashTable и пр.
0
 Аватар для oxotnik
1665 / 1134 / 80
Регистрация: 21.08.2008
Сообщений: 4,734
Записей в блоге: 1
06.12.2011, 13:48
Цитата Сообщение от some777 Посмотреть сообщение
но ест ли у тебя уверенность в производительности/оптимальности std::map на таких объёмах (1-4 миллиарда строк)?
производительней и оптимальней вряд ли найдешь
0
3 / 3 / 0
Регистрация: 25.09.2009
Сообщений: 122
06.12.2011, 14:07  [ТС]
Цитата Сообщение от some777 Посмотреть сообщение
struct Record
{
char *Data;
unsigned int Key;
Record *Next;
};
Record *Table[MaxSize];
То есть это даже менее эффективно?
0
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
06.12.2011, 15:39
Цитата Сообщение от some777 Посмотреть сообщение
То есть это даже менее эффективно?
Хэш эффективен только при наличии эффективной хэш-функции. Как ты собрался вычислять хэш-код? Если тупо складывать или ксорить символы в строке, то ничего хорошего у тебя не выйдёт.
Для миллиарда строк при поиске в дереве потребуется 31 сравнение в среднем. И я не буду упоминать тот факт, что миллиард строк не влезет в ОЗУ.)
0
 Аватар для oxotnik
1665 / 1134 / 80
Регистрация: 21.08.2008
Сообщений: 4,734
Записей в блоге: 1
06.12.2011, 15:45
вот только если посчитать объем информации, то по минимуму получается 4 млрд * 28 (20 байт строка + 8 байт на ключ) одной информации в памяти должно содержаться 104 гига. Ни один комп в своем уме такое не осилит.
Выход один - юзать СУБД.
1
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
06.12.2011, 16:04
Цитата Сообщение от some777 Посмотреть сообщение
SQL-сервер уже проходили, нужно ещё быстрее!
А не пробовал индексировать таблицы? Как бы СУБД не дураки пишут...

Добавлено через 2 минуты
Цитата Сообщение от some777 Посмотреть сообщение
упёрся в 32-bit ограничение
Больше 2^32 строк или суммарный объём данных больше?
Соотнося размер хэш-ключа и самих данных, необходимость этого самого хэша встаёт под большой вопрос. 8 байт всего в 2.5 раза меньше 20 байт. Так что если тебе нужен 64 битный хэш, то на самом деле он тебе вообще не нужен.
0
Заблокирован
06.12.2011, 22:35
Цитата Сообщение от oxotnik Посмотреть сообщение
производительней и оптимальней вряд ли найдешь
Не сказать, что очень разбираюсь в этом. Однако, ГД оч неуважительно отзываются о мапе из-за его тормознутости. И вместо него предпочитают хэш-таблицу

Добавлено через 3 минуты
some777, может быть вот здесь вы найдете для себя нечто очень интересное:
http://www.rsdn.ru/article/alg/bintree/hash.xml
0
 Аватар для oxotnik
1665 / 1134 / 80
Регистрация: 21.08.2008
Сообщений: 4,734
Записей в блоге: 1
06.12.2011, 22:41
Цитата Сообщение от Bers Посмотреть сообщение
Однако, ГД оч неуважительно отзываются о мапе из-за его тормознутости. И вместо него предпочитают хэш-таблицу
Кто такой ГД? И чем map не хеш-таблица?
0
Заблокирован
06.12.2011, 22:52
Цитата Сообщение от oxotnik Посмотреть сообщение
Кто такой ГД? И чем map не хеш-таблица?
ГД - гейм девелоперы. Для них скорость - часто один из самых критичных параметров.

Map - это вообще то сбалансированное красно-черное дерево.
"map это не хеш, это дерево. Способ употребления тот же, ассимптотика другая"(ц)

Здесь нельзя выкладывать линки на конкурирующие порталы. Но там есть живейшие обсуждения мапа и различных хэш-таблиц.

Основной тезис сводится: "Мэп не нужен - либо хэши, либо отсортированные массивы".
1
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
07.12.2011, 06:32
Цитата Сообщение от Bers Посмотреть сообщение
Для них скорость - часто один из самых критичных параметров.
К сожалению, даже гранды гейм-дева, типа Андрэ ЛаМота, периодически пишут такую хню, что плакать хочется. Половина их советов ориентирована на разработку на допотопных компиляторах, для допотопных же компьютеров.
Хэш-таблица "работает" только при наличии хорошей хэш-функции. Ни на одном портале (тем более игровом) не найти хорошую хэш-функцию, а разработать её самостоятельно не самая лёгкая задача. Для новичков это вообще не решаемая задача.

Цитата Сообщение от oxotnik Посмотреть сообщение
И чем map не хеш-таблица?
Доступ к контейнерам в хэш таблице интдексированный, а не за log2(N). Именно к контейнерам, а не к объектам, т.к. хрен кто напишет такую хэш-функцию, чтобы все объекты имели разный хэш-код для достаточно большого количества объектов, при условии, что сам хэш-код меньше объекта по "длине".
0
 Аватар для xAtom
935 / 760 / 299
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
07.12.2011, 09:37
Цитата Сообщение от some777 Посмотреть сообщение
SQL-сервер уже проходили, нужно ещё быстрее!
Неучто сможешь быстрее что-то придумать.
some777, для вычислений хэша используй встроенный-asm, инструкции MMX или SSE, кто мешает.
0
 Аватар для oxotnik
1665 / 1134 / 80
Регистрация: 21.08.2008
Сообщений: 4,734
Записей в блоге: 1
07.12.2011, 09:40
есть еще hash_map, но сдается мне, что для числовых ключей рояли она не сыграет
0
3 / 3 / 0
Регистрация: 25.09.2009
Сообщений: 122
07.12.2011, 23:19  [ТС]
Цитата Сообщение от Deviaphan Посмотреть сообщение
А не пробовал индексировать таблицы? Как бы СУБД не дураки пишут...
СУБД пишут действительно не дураки, но и объём данных обрабатываемых в единицу времени чрезвычайно велик, поэтому ищу иное решение. Конечно индексировал!

Цитата Сообщение от oxotnik Посмотреть сообщение
вот только если посчитать объем информации, то по минимуму получается 4 млрд * 28 (20 байт строка + 8 байт на ключ) одной информации в памяти должно содержаться 104 гига. Ни один комп в своем уме такое не осилит.
Выход один - юзать СУБД.
Насчёт 4 млрд я загнул, на сегодняшний день эта таблица около 300 тысяч строк и вряд ли станет более 1 миллиарда => 26Gb
А если в моём распоряжении сервер, который имеет 64Gb мозгов и 4xQuadCore проца и гипотетически предположить возможность параллельной обработки данных разными процессами, было бы гораздо быстрее, чем под SQL.

Добавлено через 5 минут
Цитата Сообщение от xAtom Посмотреть сообщение
для вычислений хэша используй встроенный-asm, инструкции MMX или SSE, кто мешает.
К сожалению, ассемблером я абсолютно не владею.
0
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
08.12.2011, 07:04
Цитата Сообщение от some777 Посмотреть сообщение
4xQuadCore проца
Параллельный поиск? В сортированном массиве (хэше/мапе, не важно)? В общем, тут многопроцессорность не поможет.


Цитата Сообщение от some777 Посмотреть сообщение
К сожалению, ассемблером я абсолютно не владею.
Пока не придумаешь качественную хэш-функцию о хэш-таблице лучше не думай.

Цитата Сообщение от some777 Посмотреть сообщение
Конечно индексировал!
Поиск в индексированной таблице СУБД не намного медленнее бинарного поиска в дереве. При использовании хэш-таблицы у тебя всё равно не будет индексированного доступа с константным временем. Ты же не сможешь для миллиарда строк миллиард разных хэш-кодов генерировать. Поэтому в каждом узле таблицы будет храниться какой-либо контэйнер со строками. От списка до мапа, всяко можно.
В общем, сперва напиши хорошую хэш функцию и если сможешь, тогда уже о хэш таблице думай.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
08.12.2011, 07:04
Помогаю со студенческими работами здесь

Как быстро копировать большие объемы информации?
Всем добрый вечер! У меня такая ситуация, нужно копировать объемы от 500гб до 3тб очень часто. почти каждый день. Но скорость USB 2.0...

Как оптимально обрабатывать большие объемы данных в DataGridView
Добрый день. Загрузил данные из access в datagridview, в 4 разные таблицы, в одной из таблиц до 1000000 строк, подскажите, как лучше...

Считать/записать большие объемы строк в txt файле
Доброго времени суток. Суть есть файл *.txt, в нем порядка 100-200 тыс. строк нужно раскидать его в несколько файлов. Как это...

Хеш-функция и хеш-таблица
Всем привет, написал хеш-функцию для строки: #include &lt;iostream&gt; //Главная библиотека #include &lt;string&gt; //Библиотека для...

Выбор базы данных, поддерживающей большие объемы данных
Доброго времени суток. Прошу совета в подборе клиента баз данных. Необходимо выполнять следующие задачи: -...


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Новые блоги и статьи
сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru