Какая структура с лимитом памяти позволит ускорить поиск по огромному файлу с набором бинарных данных?

Question

[Владимир]

Имеется 10ГБ файл содержащий отсортированные 500млн записей byte[20].
Задача состоит в поиске индексов записей по префиксу размером byte[x], где x от 1 до 16.

Имеется лимит памяти в 1-2ГБ и времени 5 минут на создание файла-индекса, который будет использован для поиска.
Имеется лимит памяти в <100МБ на вспомогательные структуры при поиске, те не на результат поиска.

Подскажите куда копать и какие структуры использовать (+ желательно примеры).

Comments

[mayton2019]

А почему придуманы такие ограничения? 10 Гб и 5 минут на копирование это запредельно мало.

И 100 Мб на вспомогательные структуры это жлобство какое-то. В мобилах сейчас памяти больше.

Если тебе по честному надо решать данную задачу то ее можно решать эффективно.

Если тебе ее ставит преподаватель-садист то зачем нам в qna это надо?

[shurshur]

Можно начать писать базу данных :)

1. Индекс, в котором хранится offset начала каждого диапазона записей для префикса ключа (диапазона ключей).

2. Индекс можно сделать в виде дерева, где иерархически ключ разделен на части. Например, ключ длины 4, 8, 12 адресует смещение и длину блока с записями с префиксом ключа такой длины.

3. Можно использовать хеширование ключа, но скорее всего не получится быстрее для отсортированных данных, ведь индексироваться будет каждая запись отдельно.

А дальше научиться как базы выбирать, когда эффективнее full scan файла, а когда - хождение по ключу.

Пример (на базах данных, для понимания):

Пусть у нас есть таблица с записями о платёжных операциях, в котором есть поле bank (текст, bank_id - неважно, просто есть). Тогда если выбирать из таблицы маленький банк (какой-нить Мухосранский Народный Банк), то поиск по индексу эффективнее: мы сходим в индекс (который меньше самой таблицы), получим немного смещений в основной таблице и вычитаем немного блоков с диска с данными. Если же выбрать Сбербанк, который упоминается в более чем 80% записей, то хождение по индексу будет означать, что мы всё равно вычитаем всю или почти всю таблицу, и обращения к индексу увеличат наши расходы больше, чем мы сэкономим. Поэтому у зрелых баз данных есть разные сложные оценки запросов, включая всяческую эвристику и накопленную по предыдущим запросам статистику.

Ну так вот, плясать с файлом в 10 Гб надо от того, какие именно действия с ним производятся. Если, например, нужно всё равно перебирать все записи - то всё равно придётся перебирать все, и ничего мудрить тут вообще не надо. Дисковый кэш в ОС всё сделает за нас, если читать мы будем последовательно хоть по байту, хоть по мегабайту.

Если же профиль конкретный действий сильно разный (иногда читаем всё, иногда одну запись), то может оказаться эффективным реализовать два разных алгоритма, один из которых будет использовать индексирование, а другой нет.

В целом записи по 20 байт слишком маленькие, чтобы индексировать каждую запись. Но так как данные отсортированы, то индексировать диапазон может быть приемлемо - особенно если грамотно выбрать длину диапазона.

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

Answer 1

[Rsa97]

Если записи фиксированного размера и отсортированы, а поиск идёт по префиксу, то никаких дополнительных структур не надо, достаточно двоичного поиска.

Comments

[Владимир]

Да, но это значит, что надо постоянно читать файл.
Можно ли это ускорить как нибудь, чтобы уменьшить количество чтений файла?

[Сергей П]

Владимир, индекс в любом случае не поместится в оперативку, а если городить какой-то ещё индекс в файловой системе, то всё равно это доступ к файлу, какая разница?
Исходный файл уже отсортирован и бинарный поиск даст логарифмическую сложность поиска в нём. Логарифм от 500 лямов это примерно 30. То есть за 30 чтений с диска вы найдёте запись, если записи распределены примерно равномерно.
Если даже это проблема, то можно взять и попробовать линеаризовать индекс.
Ну или для простоты вы можете поделить весь массив на равные по количеству элементов блоки, а на ваших паре гигабайтов хранить урезанные до (скольки там поместится) бит индексы.
Фактически вы будете за первую фазу определять блок, а дальше в блоке будете искать бинарным поиском. Сильно ли это вам поможет? Не знаю, надо делать эксперименты на реальных данных. Думается что не очень поможет сильно.

Если у вас SSD, то и так будет быстро работать

[Rsa97]

Владимир, В принципе, можете создать в памяти префиксную таблицу на два байта (на три уже выйдет за пределы 100 Мб), но для этого придётся один раз прочитать весь файл. В зависимости от равномерности распределения префиксов это, в лучшем случае, уменьшит количество чтений с диска во время поиска с 29 до 13. С SSD можно уложиться в 5 минут.

[mayton2019]

Я вот думаю о математической части этой постановки. Сортированный сет
чисел можно представить как график. Монотонный.

А 100 мб индекс можно представить как некую кусочно-линейную интерполяцию
этого графика. Причем интерполяцию не "внутри" а "снизу" графика.

Тогда поиск (или его оптимизация) будет заключаться просто в грубой оценке
первого прыжка на графике. Тоесть куда нам нужно прыгнуть чтоб
быстрее подойти и искомому интервалу чисел.

[Rsa97]

mayton2019, Один из вариантов такой интерполяции как раз префиксная таблица. Берём два первых байта, рассматриваем их как 16-битный индекс в таблице, сохраняем в этой таблице положение (смещение) первой и последней записей с таким двухбайтовым префиксом. Такая таблица займёт 2¹⁶ * 8 = 512 Кб.
Можно, конечно, брать не 16 бит, а 23, тогда получим таблицу 64 Мб.

[mayton2019]

В моем варианте шаг кусочно-линейной интерполяции может быть произвольным.

[Rsa97]

mayton2019, Но тогда будет O(log n), а у меня O(1).

[mayton2019]

Rsa97, согласен. Но я предполагаю что игры со 100Мб кешом нацелены на практическое
подавление константы которая стоит перед всеми формулами. Грубо говоря логарифмический
поиск in memory в некоторых случаях быстрее двух констант memory + disk.

[Rsa97]

mayton2019, Ну, поиск по диску всё равно у вас никуда не денется. Вряд ли записи распределены так, что их можно получить интерполяцией напрямую.

[mayton2019]

Да. Все что мы знаем о графике - он дискретный. И монотонный.

Answer 2

[Сергей Соловьев]

Первое - если файл отсортирован, то поможет бинарный поиск. Самое "в лоб", но возможно не подойдет.

В качестве индекса можно использовать бинарное дерево. Но здесь, я бы сделал так:
- В узлах храним записи фиксированного размера, чтобы не бегать постоянно и дополнительно высчитывать смещения (все 16 байт для хранения использовать можно)
- Само дерево будет содержать отрезки, т.е. не полный готовый ответ. В противном случае, будет нарушено ограничение на размер (10Гб ты никак не перепрыгнешь)

В итоге, путь будет такой:
1. Идешь в индекс ("дерево отрезков") и находишь левую и правую границу
2. Идешь в целевой файл и запускаешь бинарный поиск по нему

Если хранить индекс в памяти, то будет гораздо быстрее. Но высоту дерева надо найти импирически из-за ограничения в 100Мб в памяти

Answer 3

[alex_ak1]

10 гб разбить на файлы по 1 гб, отсортировать их.
Потом бинарным поиском по 10 файлам искать. Если будут добавлятся данные, то это просто файл№ 11 будет и искать данные потом по 11 файлам.
Либо же отсортированные 10 файлов можно слить в 1 большой.

Comments

[mayton2019]

Это вообще не решает задачу автора. Разбиение.

Для дихотомии, которую здесь правильно предлагают этот шаг тоже ничего не дает.

[alex_ak1]

А там уже сортированные данные. Не заметил. Тогда вообще проблемы не вижу-ищем диапазон первой буквы, потом в этом диапазоне следующую и всё

Answer 4

[mayton2019]

Коробочным решенеим задачи может быть префиксное дерево (Trie) с лимитом в 100Мб
которое в листовых узлах должно хранить списки искомых записей.

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

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