Поиск по большой таблице в памяти

Добрый день, проконсультируйте плиииз!

Код сейчас НЕ нужен! Нужно "понимание темы" и "чтобы почитать"... (помогут ЛЮБЫЕ советы)
(кодить начну минимум через 2-3 месяца, когда будет сама таблица, а пока "подготовка инструмента")

Задача:
1) ОЧЕНЬ большая таблица в памяти. Сотни тысяч или миллионы записей вида строка(до 20 символов)-число (длинное целое). Строки могут повторяться, числа тоже, но "пары" строка-число - уникальны.
2) Функция МАКСИМАЛЬНО быстрого поиска 10 первых чисел по полной строке. Подозреваю что нужно строить индекс (btree? немного знаком из Posgtgres)
3) Записать/восстановить таблицу (и индексы?) на диск.
Таблица "статическая" (создается и не меняется, после создания скидывается на диск, а после этого только читается)

Есть для подобного ГОТОВЫЕ механизмы в С++?
Или что бы почитать?
Собирать буду под Линукс (хостинг), поэтому "готовые библиотеки от Windows" не помогут.

По сути нужен механизм аналогичный базам Redis, но заточенный под одну задачу.

0

Я знаю только префиксное дерево

1

Сообщение от andyj Есть для подобного ГОТОВЫЕ механизмы в С++?

Есть. Там вся ваша программа займёт порядка 20-30 строк кода вместе со чтением/записью. Вы слишком преувеличиваете сложность проблемы.

Сообщение от andyj поэтому "готовые библиотеки от Windows" не помогут

В С++ стандартные библиотеки кроссплатформленные.

0

Сообщение от andyj 1) ОЧЕНЬ большая таблица в памяти. Сотни тысяч или миллионы записей вида строка(до 20 символов)-число (длинное целое). Строки могут повторяться, числа тоже, но "пары" строка-число - уникальны.

Вы украли из музея компьютер с 128 мегабайтами памяти на борту? Если нет, то миллионы записей аж по двадцать символов каждая это не "ОЧЕНЬ большая". Работающий Файрфокс небось больше сожрет.

Сообщение от andyj 2) Функция МАКСИМАЛЬНО быстрого поиска 10 первых чисел по полной строке. Подозреваю что нужно строить индекс (btree? немного знаком из Posgtgres)

std::map по строкам, внутри std::set по числам. Нет, это не "МАКСИМАЛЬНО" быстро, можно еще аллокаторы потамагочить и с хеш-таблицами поиграться. Только заниматься этим надо после полевых испытаний показавших что скорости маловато будет.

1

Сообщение от Renji std::map по строкам, внутри std::set по числам. Нет, это не "МАКСИМАЛЬНО" быстро, можно еще аллокаторы потамагочить и с хеш-таблицами поиграться. Только заниматься этим надо после полевых испытаний показавших что скорости маловато будет.

Пока хватит! СПАСИБО! Начну вычитывать... "Аллокаторы памяти" скорее всего нужны (если я правильно понял что это) - хочу "одним блоком" читать базу из файла в память и "считать ее заготовкой map+set".

Поясните только если можно:
1) std::map - это полноценная "индексированая" не ограниченная таблица в памяти для ускоренного поиска по названию? где быстрее всего идет ПОИСК записи (а не добавление/изменение)?
2) можно ЕЩЕ ускорить поиск в подобной таблице добавив многопоточность? Или создав по ::map в каждом потоке?

0

Сообщение от andyj 1) std::map - это полноценная "индексированая" не ограниченная таблица в памяти для ускоренного поиска по названию? где быстрее всего идет ПОИСК записи (а не добавление/изменение)?

Да, полноценная таблица для поиска. По названию или по числам ей в общем-то все равно, главное функцию сравнения ключей дайте (для std::string сама подцепит). Если нужно именно быстрый поиск, ценой всего остального:
1) std::unordered_map. Скорость поиска в большинстве случаев вне конкуренции. Там хэш-функция, она с равным успехом переварит и миллион ключей, и миллиард. Но есть небольшой шанс что таки подавится. Правда, любители хэш-таблиц поговаривают что вероятность падения метеорита выше.
2) Свалить все записи в массив, один раз отсортировать его std::sort и потом кататься по нему std::lower_bound. Быстрый и простой поиск, очень удобно выгружать таблицу в файл и выгружать обратно. Но любая попытка исправления потребует нового вызова std::sort, а он дорогой.

Сообщение от andyj 2) можно ЕЩЕ ускорить поиск в подобной таблице добавив многопоточность? Или создав по ::map в каждом потоке?

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

Сообщение от andyj Я из Node.js! Там попытка создать В ПАМЯТИ таблицу на миллион значений с индексами = однозначное зависание без пояснения причин... и "сбросить на диск"/"восстановить с диска" таблицу не реально без перебора КАЖДОЙ записи (в цикле)...

Запускаем, проверяем сколько времени таблицу строит. Ну, не мгновенно конечно, но за пару секунд с работой справляется. И это построение таблицы, а не поиск в ней.

1

Сообщение от andyj Таблица "статическая" (создается и не меняется, после создания скидывается на диск, а после этого только читается)

Почему базы данных не использовать?

0

Сообщение от JaponDemon Почему базы данных не использовать?

потому что это будет то-же самое, но не в памяти и без оптимизации. Постгрес меня в этом вопросе подвел (по скорости поиска)
У меня данные "статические" - один раз заполнил, сохранил и больше не меняю.

Думал на Редис, но это для ноды
1) отдельная программа работающая через TCP/IP (а не встроенный плагин) = лишняя потеря времени. Если можно этого избежать небольшими усилиями...
2) умеющая искать по части слова(там "ключи"), а значит не так сильно оптимизирована. Как и механизмы "добавления" наверняка понижают скорость "чтения/поиска".
3) у меня он уже используется, и не уверен насколько тяжело там "разделить" данные по нескольким задачам в одном проекте.

Добавлено через 15 минут
Как я уже писал выше, база у меня УЖЕ есть. Она полупустая и 2-4 месяца будет ее заполнение (полу-автоматическое). И я на 80-90% уверен что она начнет сильно тормозить (уже на 800 записях получил лимит в 100 запросов в секунду, а планируется минимум 50тыс). Поэтому решил сделать "внешний индекс" - поиск по моей таблице (по ЛЮБОЙ части слова), а детальные данные уже по ключам(id) полученным из заранее сформированного кеш-мапа. После окончательного заполнения базы, новые записи будут ОЧЕНЬ редко добавляться (10-20 в месяц) и можно будет в "полуручном" режиме дополнять таблицу или в "автоматическом" (запустив "формирование нового мапа" хоть на всю ночь)

...вопрос ЗДЕСЬ задал чтобы иметь представление куда двигаться в разработке/оптимизации когда/ЕСЛИ база начнет тормозить (реально мешая работе).


Пока не могу найти "полу-готового" решения для сброса ::map в БИНАРНЫЙ файл и чтения файла в память сразу как ::map. Только "построчная запись". Не подскажите, такое решение Вам встречалось? (например в связке с аллокаторами)

0

Сообщение от andyj Пока не могу найти "полу-готового" решения для сброса ::map в БИНАРНЫЙ файл и чтения файла в память сразу как ::map.

Там красно-черное дерево. Так что чтобы загружать map сильно быстрее "построчного варианта", вам нужно скинуть в файл структуру этого дерева. А map доступа к этой структуре не предусматривает. Хотя в принципе никто не мешает вам поковыряться в исходниках какого ни будь AVLMap и попытаться добавить нужный функционал самостоятельно.

Впрочем, есть и лайт-вариант - добавлять записи по одной, но строго в порядке возрастания ключа, через метод insert и выставив hint в myMap.end(). Теоретически это должно ускорить загрузку.

1

delete

0