Xpoint
   [напомнить пароль]

Сложная запись в файл

Метки: [без меток]
2007-12-21 12:45:57 [обр] firestorm[досье]

Коллеги, есть следующая задача.

Необходимо записать большой файл (размер порядка 4х Гб).
Сложность заключается в том, что данные необходимо записывать "вразброс":
строку a b c d e f g
необходимо записать в файл как
a f
c b g
d e

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

Из-за того, что запись идет 'вразброс' эта схема ДИКО перегружает диски, и процесс становится фантастически медленным.

Как можно ускорить такую запись в файл?

спустя 3 минуты [обр] firestorm[досье]
Забыл отметить, что из-за большого объема данных все целиком записывать в память не получается. То есть под этот процесс есть ограничение, скажем, в 500 Мб.
спустя 1 час 11 минут [обр] Thirteensmay(0/157)[досье]
Кусков много ?
спустя 2 минуты [обр] firestorm[досье]
очень. каждый кусок - примерно 20 символов
спустя 1 час 31 минуту [обр] firestorm[досье]
Были идеи кусочно засунуть это в хеш, а потом сделать квиксорт... Правда непонятно, что тут можно выиграть...
спустя 22 минуты [обр] Thirteensmay(0/157)[досье]

Тогда конечно...

Может быть будет толк если сделать в несколько шагов, но быстрых, поточных, в ОЗУ ?

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

Затем в ОЗУ загружаем некоторую достаточно существенную порцию, скажем первые 250 Мб из исходного файла (с конкретными цифрами прикиньте сами). Далее в ОЗУ выбираем из этой порции заголовки смещение-результирующий адрес, и кладем тут же отдельно, получится еще к примеру 100 Мб.

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

В конце склеиваем файлы-полуфабрикаты.

Делать это все на чистом C c указателями, возможно поможет...

?

спустя 38 минут [обр] firestorm[досье]

Как вариант, но если так делать, то имеет смысл сразу дерево строить.

На самом деле, я строю обратный инвертированный индекс:
то есть структуру типа

1 -> 001 005 010 013 056
2 -> 002 004 045 098 099
3 -> 032 043 046 056 089

для каждого числа xxx я знаю его номер - 1,2 или 3.

Номера - 1,2,3 - сидят в памяти, в хеше.
числа xxx поступают потоково, но для каждого известен номер.

Просто есть ощущение, что можно как-то просто и красиво решить эту задачу...

спустя 5 минут [обр] Thirteensmay(0/157)[досье]
Можно конечно, купите нормальную x64 машинку о 8Г памяти, и никаких проблем ;)
спустя 7 минут [обр] Thirteensmay(0/157)[досье]
Хм, это Вы хотите сказать что некие правила композиции всеже существуют ? похоже я это у Вас просмотрел, рассчитывал на то что все может быть абсолютно случайным образом, так что конечно на этом можно сыграть.
спустя 23 минуты [обр] firestorm[досье]

композиция существует. Извините, что-то не очень хорошо объясняю.

Входные данные:
(Номер строки) (Позиция в строке) (Абсолютная позиция в файле, сдвиг от начала файла) (кусок текста фиксированной длины)
Типа:
...
2 1 345 "001"
5 5 674 "012"
19 198 8763 "014"
2 2 346 "016"
2 3 347 "028"
3 8 174 "039"
...

вот этот кусок должен превратиться в

2 001 016 128
3 039
...
5 012
...
19 014

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

спустя 1 час 21 минуту [обр] Thirteensmay(0/157)[досье]

Да, представил себе рассвопленный 4Г файл в который миллиардами сиков посимвольно в случайные места пишутся данные, и правда фантастически ;)

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

спустя 43 минуты [обр] firestorm[досье]

Кажется есть идея - продолжение Вашей.

Устанавливаем размер распила - 250Мб.

Читаем первые 250 мб. Упорядочиваем так как надо (в памяти). складываем (линейно без сиков).
Берем следующие 250 мб ...

Таким образом, получится 16 файлов по 250 мб. Упорядоченные. Склеим их.

Далее проходим по первой паре файлов - линейным проходом. Для пары файлов будет только 2 указателя, которые будут двигаться 1 раз вперед (алгоритм слияния списков).
Берем результат и повторяем процедуру.

Минусы подхода - лишние 4 гб на харде - чепуха.
Количество операций по чтению/записи - сумма максимальных длин файлов (250 + 500 + 750 + 1000 + ... +3500 - столько мегабайт надо переворошить)

спустя 1 час 24 минуты [обр] Thirteensmay(0/157)[досье]
Отлично !
Открываем сразу все 16 файлов и запускаем по ним указатели, смотрим кто из них указывает
на меньшую файловую позицию - те данные и пишем в результат, использованный указатель наращиваем :)
спустя 37 минут [обр] firestorm[досье]
Точно :) Вот так рождаются хорошие идеи :) Большое спасибо Вам за помощь!
спустя 8 минут [обр] firestorm[досье]
:) Забавно :) Файловый квиксорт получился
спустя 1 час 29 минут [обр] Thirteensmay(0/157)[досье]
Еще можно попробовать оптимизировать процесс сбора результирующего файла за счет буферов чтения исходных файлов. Выделить на каждый из них буфер метров по 10, 16х10 Мб в нашем случае погоды не делают, зато ползти можно будет не напрямую по файлам а по их буферам в памяти, может получится существенно быстрее. Ну естественно по исчерпании буфера загружать в них новые порции данных из исходных файлов. Теоретически операционка это сама делает, но с размерами буферов у нее может быть напряг, мы же сделаем их большими и сможем сэкономить на лишних обращениях к диску.
спустя 1 день 13 часов [обр] Maxim Penzin[досье]

firestorm[досье] на самомделе это все давно инвестные идеи.

Рекомендую посмотреть "Искусство Программирования для ЭВМ" (Дональд Кнут) - сортировка на лентах.
Там есть всякие варианты с применением очень малого объема ОЗУ, оценки их применимости, производительности и т.п.

Powered by POEM™ Engine Copyright © 2002-2005