Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 2006.06.11;
Скачать: [xml.tar.bz2];

Вниз

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

 
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 кб.


 
Сергей М. ©   (2006-04-26 14:00) [24]


> bsframer   (26.04.06 13:50) [22]


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


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


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


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


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

До 4Гб - тип DWORD.

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


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

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


 
GrayFace ©   (2006-04-28 11:08) [28]

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

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


 
Сергей М. ©   (2006-04-28 11:16) [29]


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


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


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


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


 
han_malign ©   (2006-04-28 11:47) [30]


> Слышал про 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;

- мапирует файл "целиком"(пытается), только для чтения...


 
GrayFace ©   (2006-04-29 08:12) [31]

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

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


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

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



Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2006.06.11;
Скачать: [xml.tar.bz2];

Наверх





Память: 0.53 MB
Время: 0.021 c
1-1146671592
justnick
2006-05-03 19:53
2006.06.11
Корректное создание массива из пользовательских структур.


15-1148047749
tesseract
2006-05-19 18:09
2006.06.11
Outlook , ну чего тут можно сказать :-)


2-1148517183
eJack
2006-05-25 04:33
2006.06.11
dbExpress


6-1139391853
WebSQLNeeder
2006-02-08 12:44
2006.06.11
Как програмно через TWebBrowser нажать на кнопку во ФЛЕШ?!


2-1148361462
Konnor
2006-05-23 09:17
2006.06.11
Reboot





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский