 |
|
Модераторы: Daevaorn |
 
|
|
Быстрый поиск в большом множестве 
| xbarmaglot |
|
|||
|
Шустрый  Профиль Группа: Участник Сообщений: 149 Регистрация: 28.8.2012 Репутация: нет Всего: нет |
Есть большое количество блоков данных расчитанных по определенной формуле. Размер блока - 5 байт. Количество блоков - 2^24. Куда можно запихнуть данную таблицу и как оформить блоки для максимально быстрого поиска совпадающих значений?
|
|||
|
||||
Загрузка ...
| bsa |
|
|||
 Эксперт Профиль Группа: Модератор Сообщений: 9185 Регистрация: 6.4.2006 Где: Москва, Россия Репутация: 63 Всего: 196 |
если тебе надо сравнивать значения блоков, то для этого существует хэш (SHA1, MD5 и пр). Т.е. хэши сравниваются достаточно быстро. Поэтому ты сначала считаешь хэши для всех блоков, затем сравниваешь один хэш с другим, если совпадают, то сравниваешь блоки полностью. Если не совпадают, то блоки сравнивать смысла нет.
Хранить лучше на диске в виде одного файла, ИМХО. |
|||
|
||||
| baldina |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 32 Всего: 101 |
и зачем тут хеши? Добавлено через 9 минут и 54 секунды быстрее всего хеш-таблица std::unordered_map<int32_t> |
|||
|
||||
| bsa |
|
|||
|
Эксперт Профиль Группа: Модератор Сообщений: 9185 Регистрация: 6.4.2006 Где: Москва, Россия Репутация: 63 Всего: 196 |
ой. я подумал, что 5 килобайт
 Кстати, такой объем можно и в память загрузить. Сейчас у компов ее много. |
|||
|
||||
| baldina |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 32 Всего: 101 |
эти 80Мб и в планшет влезут
|
|||
|
||||
| xbarmaglot |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 149 Регистрация: 28.8.2012 Репутация: нет Всего: нет |
а как лучше - статически их в память поместить или считывать из файла при инициализации ?
P.S. И что для хэш-таблицы лучше - array, vector,... ? |
|||
|
||||
| baldina |
|
||||||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 32 Всего: 101 |
гы. а что вы понимаете под хэш-таблицей? хэш-таблица сама является структурой данных. её реализация есть стандартной библиотеке
изобретать велосипед не стоит
это не одно и то же? лучше, конечно, действие выполнить однократно. |
||||||
|
|||||||
| xbarmaglot |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 149 Регистрация: 28.8.2012 Репутация: нет Всего: нет |
Я имел ввиду данные какогого типа в нее лучше класть. Важна скорость поиска.
|
|||
|
||||
| baldina |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 32 Всего: 101 |
вы же сами сказали - блоки по 5байт
Добавлено через 3 минуты и 17 секунд целое кладите. для 2^24 подойдет int32_t, но если данные "размазаны" по блокам, кладите int64_t std::unordered_map<int64_t> Добавлено через 5 минут и 26 секунд на 64-разрядной платформе пожалуй это будет быстрее, чем 32 тонкую оптимизацию будете проводить, когда получите работающее решение (если оно покажется медленным) Это сообщение отредактировал(а) baldina - 19.7.2014, 23:51 |
|||
|
||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0482 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |