Обработка текстовых файлов больших размеров (2

← →
bsframer (2006-04-26 08:59) [0]

Здраствуйте, Уважаемые. Может вопрос и глупый, но мучаюсь уже второй день. Есть текстовый файл большого размера (2-3 ГГб), строки порядка 200 символов. Вопрос, как можно провести в нем сортировку по возрастанию (убыванию)? Пробовал ReadLn, BlockRead, TFileStream - медленно (нужно чтоб 50 МГб примерно за 5 минут пробегало). Через TStringList можно (100 МГб - 2,5 минуты), но в него влазит порядка 500 МГб (Оперативки 1 ГГб), дальше сообщение Out of Memory и стопор. Разрезание файла на куски думал, но это геморойно. Слышал про FileMapping, но не знаю как с ним работать и подойдет ли он вообще. Может есть какой способ, чтоб оперативки меньше жрало и работало быстрее, или я не так пробовал?

← →
MBo © (2006-04-26 09:05) [1]

Нужно почитать о внешней сортировке.
Простая - слиянием, но для нее требуется дополнительное место (размер файла)

← →
Сергей М. © (2006-04-26 09:09) [2]

Воспользуйся готовой СУБД.

← →
bsframer (2006-04-26 09:16) [3]

СУБД можно, но не нужно. Нужно именно стандартными стредствами Delphi или WinAPI

← →
Anatoly Podgoretsky © (2006-04-26 09:21) [4]

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

← →
bsframer (2006-04-26 09:30) [5]

А это где?

← →
TUser © (2006-04-26 09:31) [6]

> Разрезание файла на куски думал, но это геморойно.

Смотри на алгоритмы внешней сортировки. От предков с гораздо меньшими ОЗУ, чем у тебя, много осталось. Например, в книге Вирта описаны, ад и много где еще.

← →
bsframer (2006-04-26 09:39) [7]

Спасибо, уже Кнута изучаю

← →
Сергей М. © (2006-04-26 09:48) [8]

> bsframer (26.04.06 09:16) [3]
>
> СУБД можно, но не нужно

Тогда тебе придется изобрести еще один велосипед.
Индексы так или иначе придется строить, но в случае с СУБД нет необходимости реализовывать механизм индексации - он там уже реализован.

← →
bsframer (2006-04-26 09:52) [9]

Хорошо, а какая СУБД наиболее подходящая, для решения данной задачи. Просто я использовал импорт в mdb с последующим экспортом обратно. Сортировка файла 1 ГГб заняла примерно 10 часов.

← →
ANB © (2006-04-26 09:52) [10]

> СУБД можно, но не нужно. Нужно именно стандартными стредствами
> Delphi или WinAPI

Ну прям как у нас на флоте :

- Бери лом и мети плац
- А можно я метлу возьму - будет быстрее и чище
- А мне не надо, чтобы было быстрее и чище, мне надо чтобы ты за<Удалено модератором>

Вам шашечки или ехать ?
Самый быстрый способ (если уж в файле все надо хранить) :
1. Загрузить все в таблицу БД
2. Проиндексировать
3. Выгрузить обратно в файл

← →
ANB © (2006-04-26 09:54) [11]

> bsframer (26.04.06 09:52) [9]

1. Самая доступная - FB или IB
2. Самая навороченная - Оракл - там можно вообще все на PL/SQL написать, он с файлами работать умеет и довольно шустро.

← →
bsframer (2006-04-26 09:57) [12]

Еще с собой Оракл таскать, нет уж увольте.

← →
Сергей М. © (2006-04-26 10:16) [13]

> bsframer (26.04.06 09:52) [9]

Подойдет даже FB Embedded

← →
Сергей М. © (2006-04-26 10:22) [14]

Если таки вариант с СУБД не устраивает никаким образом, построить самому индексную таблицу не так уж и сложно - читаешь последовательно строки исх.файла, фиксируешь их смещение и размер.
Далее сортируешь полученную таблицу (теперь обращение к строкам исх.файла - произвольное, а не последовательное) и уже имея ее отсортированную записываешь считываемые из исх.файла соотв.строки в результирующий файл.

← →
bsframer (2006-04-26 11:16) [15]

Неподскажите чем реализовать быстрое считывание строк. TFileStream не знает где конец у строки, Readln медленный, побайтно тоже медленно.

← →
Palladin © (2006-04-26 11:31) [16]

Общепринятый конец у строки там где есть #13 или #10 или #13#10

← →
bsframer (2006-04-26 11:52) [17]

Это понятно, значит всетаки побайтно брать? Другова способа нет?

← →
Сергей М. © (2006-04-26 12:24) [18]

> значит всетаки побайтно брать?

Зачем побайтно ?

Считывай сразу по 64кб и ищи там символы-разделители, учитывая при этом результаты поиска конца последней строки при анализе предыдущих считанных 64кб

← →
bsframer (2006-04-26 13:33) [19]

А через ADO (Microsoft Text Driver) реально подключить и обработать такой файл?

← →
Сергей М. © (2006-04-26 13:38) [20]

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

← →
GrayFace © (2006-04-26 13:42) [21]

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

← →
bsframer (2006-04-26 13:50) [22]

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

← →
bsframer (2006-04-26 13:59) [23]

Брать последнюю строчку в Memo (она будет либо полной либо нет) взять ее длинну, удалить. Затем установить указатель в файле на 64 кб - Длинна последней строчки и считывать следующие 64 кб.

> bsframer (26.04.06 13:50) [22]

Тебе сортировка нужна или "пихать" ?

← →
bsframer (2006-04-26 14:15) [25]

> читаешь последовательно строки исх.файла, фиксируешь их
> смещение и размер.
> Далее сортируешь полученную таблицу

Сортировка конечно, можно подробнее описать (какие типы и классы использовать)?

До 4Гб - тип DWORD.

Классы - на твой вкус.
Можешь вообще их не использовать.

← →
bsframer (2006-04-26 14:41) [27]

:) а пример кода можно?

> Да куда мне это запихать, вся информация будет чуть меньше
> размером чем сам файл.
Длина строк ~ 200 символов, размер файлов = 2-3 GB. Если хранить смещения и первые 4 символа, получаем 3000/200*8=120 MB. Максимальный размер обрабатываемого файла = 2/8*200=50GB. Думаю, достаточно. Конечно, при подобных размерах своп придется подергать.
А хранить размер не нужно. Он = разность смещений - размер перевода строки.
Быструю сортировку см. в TStringList.Sort.

> GrayFace © (28.04.06 11:08) [28]

> хранить размер не нужно

> разность смещений

О какой разности смещений можно говорить для последней строки ?

> Слышал про FileMapping, но не знаю как с ним работать и подойдет ли он вообще.

- File mapping поможет мало, все равно окно больше максимального доступного не фрагментированного диапазона виртальных адресов не сделаешь(MapViewOfFile), т.е. примерно такое же ограничение как StringList...
Но для общего развития:
type TFileMappingData = class private F_hFile: THandle; F_hMap: THandle; F_sFileName: string; F_pData: pointer; F_cbSize: integer; F_dwError: DWORD; public constructor Create(const aFileName: string= ""); destructor Destroy; override; function Reset(const aFileName: string= ""): boolean; property Data: pointer read F_pData; property Size: integer read F_cbSize; property Error: DWORD read F_dwError; end; implementation constructor TFileMappingData.Create(const aFileName: string= ""); begin F_hFile:=INVALID_HANDLE_VALUE; Reset(aFileName); end; destructor TFileMappingData.Destroy; begin Reset; end; function TFileMappingData.Reset(const aFileName: string= ""): boolean; begin Result:=F_pData<>nil; if(CompareString(LOCALE_USER_DEFAULT, NORM_IGNORECASE, PChar(aFileName), Length(aFileName), PChar(F_sFileName), Length(F_sFileName))=2) then exit; if(F_pData <> nil)then UnmapViewOfFile(F_pData); if(F_hMap <> 0)then CloseHandle(F_hMap); if(F_hFile <> INVALID_HANDLE_VALUE)then CloseHandle(F_hFile); F_pData:=nil; F_hMap:=0; F_hFile:= INVALID_HANDLE_VALUE; Result:= true; F_dwError:= ERROR_NO_DATA; if(aFileName <> "")then begin F_hFile:= CreateFile(PChar(aFileName),GENERIC_READ, FILE_SHARE_READ, nil, OPEN_EXISTING, 0, 0); if(F_hFile <> INVALID_HANDLE_VALUE)then begin F_hMap:= CreateFileMapping(F_hFile, nil, PAGE_READONLY, 0, 0, nil); if(F_hMap<>0)then begin F_pData:= MapViewOfFile(F_hMap, FILE_MAP_READ, 0, 0, 0); if(F_pData <> nil)then begin F_cbSize:= GetFileSize(F_hFile, nil); F_sFileName:= aFileName; F_dwError:= NO_ERROR; exit; end else F_dwError:=GetLastError; CloseHandle(F_hMap); end else F_dwError:=GetLastError; CloseHandle(F_hMap); end else F_dwError:=GetLastError; Result:=false; end else begin F_sFileName:=""; end; end;
- мапирует файл "целиком"(пытается), только для чтения...

> Сергей М. © (28.04.06 11:16) [29]
> О какой разности смещений можно говорить для последней строки?

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

← →
SYSCON (2006-05-02 09:30) [32]

А виндовая Sort.exe для этой задачи не подойдет?

Обработка текстовых файлов больших размеров (2 - 3 ГГб) Найти похожие ветки