Поиск в файле

[__Heaven__]

Привет друзья!
Имеется файл в сыром формате. Представляет из себя массив double.
Необходимо найти первое повстречавшееся значение 0.99, затем 0.98, далее 0.97 и так до 0.01.
Размеры файлов, в которых будет производиться поиск может превышать 500 Гб.
Существует большая вероятность, что числа в файле будут встречаться в убывающем порядке.
Также есть вероятность, что какое-либо число может не встретиться в файле вовсе.

Каким образом оптимально проиндексировать все повстречавшиеся в файле значения от 0.99 до 0.01 с шагом 0.01?

[Igors]

Любой ассоциативный контейнер, напр QHash <double, qint64>, но можно и QMap, std::map и.т.п.

[__Heaven__]

Что хранить в нем - это понятно.
А как искать? Чтением в QByteArray и дальнейшим перебором пока еще неповстречавшихся?

[Igors]

Что хранить в нем - это понятно.
А как искать? Чтением в QByteArray и дальнейшим перепором пока еще неповстречавшихся?

Читаете файл кусками по 64K напр в QByteArray и перебираете doublе за double. Если значение есть в хеше - сразу дальше, иначе сначала заносите в хеш

[vulko]

Читаете файл кусками по 64K напр в QByteArray и перебираете doublе за double. Если значение есть в хеше - сразу дальше, иначе сначала заносите в хеш

капитан говнокодинг вновь отличился)))


Читать посоветовал бы в 4 потока хотя бы.
Иначе есть вариант уснуть на клавиатуре

Хэш-таблица возможно не лучший вариант. Учитывая что искомые значения фиксированы, то их всего 100 штук. Лучше воспользоваться массивом либо вектором, главное чтобы он на стэке жил, а не в куче.

[__Heaven__]

Лучше воспользоваться массивом либо вектором, главное чтобы он на стэке жил, а не в куче.

Вот это не совсем понял. Как такое организовывается?

У меня пока что видется только такая мысль. Нужно в одном потоке вести чтение и создавать очередь из QByteArray'ев фиксированной длинны. Создать 4 потока, которые будут забирать к себе из очереди QByteArray. Далее поток будет перегонять QByteArray в QVector и там уже через indexof искать необходимые значения. Ну, и понятно, что будет список ненайденных пока еще значений, который должен быть обезопасен от двойного удаления и массив найденых (защита от перезаписи тут уже не важна).

Как такой вариант по производительности?

[vulko]

У меня пока что видется только такая мысль. Нужно в одном потоке вести чтение и создавать очередь из QByteArray'ев фиксированной длинны. Создать 4 потока, которые будут забирать к себе из очереди QByteArray. Далее поток будет перегонять QByteArray в QVector и там уже через indexof искать необходимые значения. Ну, и понятно, что будет список ненайденных пока еще значений, который должен быть обезопасен от двойного удаления и массив найденых (защита от перезаписи тут уже не важна).

Как такой вариант по производительности?

Скорее всего затык будет в чтении.
Ну допустим можно не более 100мб начитать в ОЗУ (зависит от конкретной машины), это 2% от 500гб файла.
Разбирать данные будут быстро. Читать с жесткого насителя куда медленнее.
В итоге 4 потока будут тут ни к чему, т.к. не дадут большой производительности.

В идеале было бы читать файл в 4 потока и в 4 потока обрабатывать. Ну или 2+2. Зависит от конкретной машины.

Я тут недавно смотрел за сколько 300мб файл прочитается в память + парсинг структур. Примерно 8 сек.
500гб это уже не шутки. Тут можно и на пару часов попасть в легкую...


Впрочем для начала вариант норм. Можно будет натыкать немного логов и посмотреть, не многовато ли 4 потока для обработки. Может и 2-х хватит, а то и вообще одного.
Скорее всего очередь из QByteArray'ев будет всегда пустой, значит затык в скорости чтения.

Вот это не совсем понял. Как такое организовывается?

Если искаться будет фиксированное количество значений, например 0.01-0.99, то значений будет всего 100.
Никаких Map'ов тут не нужно, для 100 элементов они куда медленнее обычного массива. Даже хэш таблица даст ощутимый прирост в скорости поиска начиная где-то с 10-100 тысяч элементов.

Соотв. найденные элементы не нужно запихивать в map. Используй обычный массив/вектор.

[__Heaven__]

В идеале было бы читать файл в 4 потока и в 4 потока обрабатывать. Ну или 2+2. Зависит от конкретной машины.

А наличие более одного потока на чтение одного файла это нормально? они не будут друг с другом конфликтовать? Я эту кухню не знаю, но ощущение такое, что чтение  одним потоком быстрее двух.

[vulko]

В идеале было бы читать файл в 4 потока и в 4 потока обрабатывать. Ну или 2+2. Зависит от конкретной машины.

А наличие более одного потока на чтение одного файла это нормально? они не будут друг с другом конфликтовать? Я эту кухню не знаю, но ощущение такое, что чтение  одним потоком быстрее двух.

Скорость чтения ессесно будет упираться в возможности физического устройства.
Соотв. нужно несколько устройств. Например 2 винта, на обоих один и тот же файл.
Читаем в ~ 2 раза быстрее. Обработка прочитанных данных не должна занимать много времени и будет работать быстрее чтения.

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

[Fregloin]

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

[__Heaven__]

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

Не, это что-то мощное
У меня обычный конвертер и программа пишется для себя. Будет правильнее все делать на одной машине. Просто хотелось добавить скорости. Сервер мне точно не дадут.

[Fregloin]

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

[vulko]

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

gpu не справится быстрее с этой задачей, т.к. тут весь затык в скорости чтения из файла.

[__Heaven__]

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

gpu не справится быстрее с этой задачей, т.к. тут весь затык в скорости чтения из файла.

Поддерживаю. Процессор обрабатывает значения (не хочу соврать) в тысячи раз быстрее, чем данные считываются с HDD.

[Fregloin]

ну как решение задачи - читать с SSD. ну это в зависимости от важности задачи.
если не критично, то пусть всю ночь колбасит поиски ). А если нужно часто, то я предложил вариант распределенного вычисления )