Быстрый способ работы с файлом

← →
Piter © (2006-02-03 14:33) [0]

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

Файл может занимать несколько десятков мегабайт или даже больше сотни.

← →
Piter © (2006-02-03 14:35) [1]

проверил с Bred3.

Файл на 34 Mb достаточно быстро открывает, меньше секунды в нем ищет - устраивает.

А вот на 150 Mb открыть не смог - не хватает памяти написал. Думаю, чисто внутренние ограничения. Ну открывал бы 3 секунды.

А мне еще и отображать не надо...

Имеет смысл использовать TextFile? Или думаю лучше сразу с помошью WinApi работать с файлом?

← →
Игорь Шевченко © (2006-02-03 14:37) [2]

CreateFileMapping + MapViewOfFile

← →
TUser © (2006-02-03 15:05) [3]

Тут еще надо поискать оптимальный алгоритм поиска в этом файле. Есть много достойных алгоритмов.

← →
Piter © (2006-02-03 15:19) [4]

Игорь Шевченко © (03.02.06 14:37) [2]
CreateFileMapping + MapViewOfFile

TUser © (03.02.06 15:05) [3]
Тут еще надо поискать оптимальный алгоритм поиска в этом файле

я так понимаю спроецировать файл к себе в ВАП.

Тогда вытекающий вопрос - как оптимально искать в этом файле? Что-то типа PosEx, но работающей не со строками, а с PChar?
Есть у кого такое?

← →
TUser © (2006-02-03 16:07) [5]

> Тогда вытекающий вопрос - как оптимально искать в этом файле?

Ищи алгоритм Кнута-Мориса-Пратта или Бойера-Мура. Или один из им аналогичных - см. на алголисте.

← →
Piter © (2006-02-03 16:17) [6]

TUser © (03.02.06 16:07) [5]

мне б готовую реализацию :)

← →
Игорь Шевченко © (2006-02-03 16:40) [7]

> мне б готовую реализацию

http://www.google.ru ?

← →
TUser © (2006-02-03 17:37) [8]

> Piter © (03.02.06 16:17) [6]

КМП могу дать (из дома). Но все равно придется переписать под свою задачу, а для этого придется разобраться в алгоритме. У меня читает файл в поток и ищет там заданную строку.

← →
Leonid Troyanovsky © (2006-02-03 17:47) [9]

> Piter © (03.02.06 15:19) [4]

> я так понимаю спроецировать файл к себе в ВАП.

А зачем проецировать? Ищем одну последовательность,
затем - другую, а промежуток копируем в строку. Т.е.,
двигаемся вперед, сл-но, TFileStream вполне пригоден.
Буфера (пары) в 64К вполне достаточно. Искать прямо в лоб (inc),
сравнивать CompareMem. Оптимизировать что-то здесь сложно,
бо задача решается за один проход.

--
Regards, LVT.

← →
Игорь Шевченко © (2006-02-03 17:51) [10]

Leonid Troyanovsky © (03.02.06 17:47) [9]

Насколько мне известно, проецирование - наиболее быстрый механизм доступа к данным, кроме того, еще и удобный, не надо обременяться буферизацией :)

С уважением,

← →
Leonid Troyanovsky © (2006-02-03 18:01) [11]

> Игорь Шевченко © (03.02.06 17:51) [10]

> Насколько мне известно, проецирование - наиболее быстрый
> механизм доступа к данным, кроме того, еще и удобный, не
> надо обременяться буферизацией :)

Он, конечно, быстрый (я как-то, вроде здесь, приводил
результаты by Slava Usov), но, целиком его спроецировать
врядли удасться (учитывая неудачу Bred3), а значит о
разрыве на границе все равно придется думать.
А если Piter захочет использовать StrPos, то ему потребуется r/w
для записи последнего #0, значит, будет и не так уж быстро.

--
Regards, LVT.

← →
Игорь Шевченко © (2006-02-03 18:15) [12]

Leonid Troyanovsky © (03.02.06 18:01) [11]

Мне словосочетание bred3 ни о чем не говорит, поэтому я не могу сказать, что неудача с bred3 означает неудачу попыток проецирования вообще. Тем более, 150 Мб спроецировать вроде проблем не составляет :) Я вот только что полтора гигабайта спроецировал :)

С уважением,

← →
Leonid Troyanovsky © (2006-02-03 18:22) [13]

> Игорь Шевченко © (03.02.06 18:15) [12]

> Мне словосочетание bred3 ни о чем не говорит, поэтому я
> не могу сказать, что неудача с bred3 означает неудачу попыток

Мне оно тоже ничего не говорит, просто, кажется, что на той
машине нет 2Г памяти.

> проецирования вообще. Тем более, 150 Мб спроецировать вроде
> проблем не составляет :) Я вот только что полтора гигабайта
> спроецировал :)

Проецировать можно, сложности с просмотром на все тело :)

--
Regards, LVT.

← →
Leonid Troyanovsky © (2006-02-03 18:53) [14]

> Игорь Шевченко © (03.02.06 17:51) [10]

> Насколько мне известно, проецирование - наиболее быстрый
> механизм доступа к данным

Во, я нашел про это (в треде есть и ссылка на Slava Usov)

http://groups.google.com/group/fido7.su.win32.prog/msg/b154ddb59929f5cb

Дмитрий, кстати, еще где-то рассказывал про большие тормоза
при чтении из файла размером более оперативки при чтении
из view порциями около 4кб. Т.е., для последовательного чтения
Дмитрий уверен в превосходстве обычного ReadFile, ну а спорить
я с ним не буду.

--
Regards, LVT.

← →
Игорь Шевченко © (2006-02-03 19:16) [15]

Leonid Troyanovsky © (03.02.06 18:53) [14]

Я охотно верю указанным авторам, но задача задаче рознь, кроме того, Windows сама использует проецирование файлов для своих задач чтения, о чем писал, если не ошибаюсь, Руссинович, а с ним спорить мне тем более не хочется. Искать что-либо наиболее просто, как мне кажется, в MMF, в данном случае для меня критерием является простота.

С уважением,

← →
Leonid Troyanovsky © (2006-02-03 19:37) [16]

> Игорь Шевченко © (03.02.06 19:16) [15]

> а с ним спорить мне тем более не хочется. Искать что-либо
> наиболее просто, как мне кажется, в MMF, в данном случае
> для меня критерием является простота.

Насчет простоты, я, кажется уже снабжал Piter"a ссылкой

http://groups.google.com/group/fido7.ru.delphi/msg/64b9f15bdadf6923

Но, видимо, она ему в этой задаче не очень пригодилась.
Кстати, в том обсуждении меня убедили, что CompareMem в [9]
будет нехорошо. Запамятовал, каюсь :)

--
Regards, LVT.

← →
TUser © (2006-02-03 19:40) [17]

Вот реализация алгоритм КМП. Отображение в память сам пиши.

program kmp; {$apptype console} uses Classes, SysUtils; function KMPPos (const Text: string; const Template: string): integer; var sp: array of integer; i, j, k: integer; begin result:=-1; SetLength (sp,length(Template)); j:=0; sp[0]:=0; for i:=2 to length(Template) do begin inc (j); while j <> 0 do if Template[i] <> Template[j] then j:=sp[j-1] else break; sp[i]:=j; end; j:=1; k:=1; for i:=1 to length(Text) do if Text[i] = Template[j] then begin inc (j); if j = length(Template)+1 then begin result:=k; Break; end; end else begin k:=k+j-sp[j]; j:=sp[j]+1; end; SetLength (sp,0); end; var List: TStrings; i: integer; begin List:=TStringList.Create; List.LoadFromFile(ParamStr(1)); i:=KMPPos(List.Text,ParamStr(2)); if i = -1 then writeln ("not found") else writeln ("first entry in "+inttostr(i)); List.Free; end.

← →
Leonid Troyanovsky © (2006-02-03 19:43) [18]

← →
Defunct © (2006-02-04 05:59) [19]

> Piter

Поиск по бинарнику должен подойти. Помните где-то полтора года назад мы тут с GuAV ветку раздули о бинарном поиске. Так вот тот метод не имеет впринципе такого понятия как "отрывает", а поиск производит достаточно быстро - 20-25 сек при скорости диска - 50-60MBps.

Алгоритм предельно прост - тот же FileMapping только с применением оптимального объема окна +быстрая функция поиска подстроки в строке.
1. Берем окно (буфер) объемом L2, куда будем осуществлять считывание порции файла.
2. Считываем порцию файла
3. Ищем искомую строку.
4. Нашли - хорошо (выход).
5. Не нашли - позиционируем файловый указатель назад на длину искомой строки и продолжаем с п.2.

← →
Defunct © (2006-02-04 06:01) [20]

> "отрывает"

typo.. читать "открывает"..

← →
Defunct © (2006-02-04 06:03) [21]

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

> а поиск производит достаточно быстро - 20-25 сек при скорости диска - 50-60MBps.

20-25 сек на Гигабайт!

← →
Набережных С. © (2006-02-04 08:38) [22]

> Leonid Troyanovsky © (03.02.06 18:53) [14]

Хм.
Файл размером 1 ГБ, памяти в машине 2х256 Мб, хотя в данном случае это не важно.
Буффер выделен VirtualAlloc, т.е. выравнен по границе страницы. Размер его равен AllocationGranularity.
Для MMF размер отображенного окна равен размеру буфера.
Читаем последовательно весь файл в буфер, время измеряем посредством GetTickCount.
Выполнил по 20 тестов, начиная с MMF. Результат:

MMF: 47 - 63 ms
TFileStream: 1453 - 1469 ms
ReadFile: 1453 - 1469 ms

Может, они не умеют их готовить? Или это я что-то неправильно понял?

← →
Набережных С. © (2006-02-04 08:48) [23]

Да, забыл - система WiXP SP2. Хотя, как помнится, на W2k я получал примерно то же соотношение.

← →
Набережных С. © (2006-02-04 09:29) [24]

Пардон, ошибся с просонгья:)) Для MMF результат 470 - 630, забыл один оператор в тесте с MMF. Результат для MMF: 1171-1187.

← →
Piter © (2006-02-04 14:15) [25]

Defunct © (04.02.06 5:59) [19]

а если искомая строка будет разбита границой буфера? Тогда она может не найтись, хотя есть.

> а если искомая строка будет разбита границой буфера?
> Тогда она может не найтись, хотя есть.

см. внимательно п. 5

Defunct © (05.10.04 4:39) [193] Итак долгожданный победитель заезда ;) Function ConstantPos(const Constant, Buffer: string): Integer; Assembler; Asm Test eax, eax Jz @@NotFound_Exit Test edx, edx Jz @@NotFound_Exit Mov ECx, [EDx-4] Test ECx, ECx Jz @@NotFound_Exit Cmp [EAx-4],1 Jnz @@WideSearch Cmp ECx,8 Ja @@WideScan // CharPos @@Scan4: Mov Ch,[EAx] // Ch - char // EDx - pointer to buffer // cl - length @@CharPos: Mov EAx,[EDx] Cmp Ch,Al Jz @Found1 cmp Ch,Ah Jz @Found2 Shr EAx,16 Cmp Ch,Al Jz @Found3 Cmp Ch,Ah Jz @Found4 Cmp Cl,4 Jna @NotFound Mov EAx,[EDx+4] Cmp Ch, Al Jz @Found5 Cmp Ch, Ah Jz @Found6 Shr EAx, 16 Cmp Ch, Al Jz @Found7 Cmp Ch, Ah Jz @Found8 @NotFound: XOr EAx, EAx Ret @Found1: Mov EAx,1 Jmp @Validation @Found2: Mov EAx,2 Jmp @Validation @Found3: Mov EAx,3 Jmp @Validation @Found4: Mov EAx,4 Jmp @Validation @Found5: Mov EAx,5 Jmp @Validation @Found6: Mov EAx,6 Jmp @Validation @Found7: Mov EAx,7 Jmp @Validation @Found8: Mov EAx,8 Jmp @Validation @Validation: Cmp Al,Cl Ja @NotFound ret nop nop // alignment for better performance @@SmallScan: Push ECx Mov Ch,[EAx] @@Scan8: Push ECx Call @@CharPos Pop ECx Test EAx, EAx Jz @Validation3 Sub Cl, Al Pop EAx Sub Al, Cl Ret @Validation3: Sub Cl, 8 Add EDx, 8 Cmp Cl, 0 Jg @@Scan8 Add ESP, 4 Ret @@LastDword2: Test ECx, ECx Js @@Exit_False2 Jz @@Exit_False2 MovD MM7, [EDx] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) MovD EAx, MM7 // get mixed dword Test EAx, EAx Jnz @@Loop2 Jz @@Exit_False2 @@WideScan: Cmp ECx, 16 Jb @@SmallScan Mov Al,[EAx] Mov Ah, Al MovD MM6, EAx PUNPCKLWD MM6, MM6 PUNPCKLDQ MM6, MM6 Push ECx @@Scan5: MovQ MM7, [EDx] PCMPEQB MM7, MM6 PACKSSWB MM7, MM7 MovD EAx, MM7 Test EAx, EAx Jnz @@CharFound2 Add EDx,8 Sub ECx,8 Cmp ECx,4 Jg @@Scan5 Jmp @@LastDword2 @@Exit_False2: Emms Pop EAx Xor EAx, EAx Ret @@CharFound2: MovQ MM7, [EDx] PCMPEQB MM7, MM6 MovD EAx, MM7 Test EAx, EAx Jnz @@Loop2 Sub ECx,4 PSRLQ MM7,32 MovD EAx, MM7 @@Loop2: Dec Ecx Test Al,Al Js @@Check2 Shr EAx,8 Jmp @@Loop2 @@Check2: Test ECx,ECx Js @@Exit_False2 Emms Pop EAx Sub EAx, ECx Ret @Small_String: Cmp ECx, [EAx-4] Jb @NotFound Mov Ch, [EAx] Push ECx Push EBx Push ESi Mov ESi, EAx Mov EBx,[ESi-4] Dec EBx @Scan6: Push ECx @Scan7: Call @@CharPos Pop ECx Test EAx, EAx Jz @Validation2 Sub Cl, Al Add EDx, EAx Cmp Cl, Bl Jb @NotFound2 Push ECx Mov ECx, EBx @Loop2: Mov Al, [ESi+ECx] Cmp Al, [EDx+ECx-1] Jnz @Scan7 Loop @Loop2 Pop ECx Mov Ah, 0 Pop ESi Pop EBx Pop EAx Sub EAx, ECx ret @Validation2: Sub Cl, 8 Add EDx, 8 Cmp Cl, 0 Jg @Scan6 @NotFound2: Pop ESi Pop EBx Add ESp, 4 Xor EAx, EAx Ret nop // code alignment nop @@WideSearch: Cmp ECx,32 Jb @Small_String Push EDi Push ESi Push EBx Push EBp MOV ESI, EAX Mov EDi, EDx Push ECx Mov EBX, [ESI-4] Test EBx, EBx Jz @@Exit_False Mov Al, [ESi] Cmp EBx, ECx Ja @@Exit_False Jnz @@Normal_Work Cmp AL, [Edi] Jnz @@Exit_False @@Normal_Work: Dec EBX Mov Ah, [ESi+EBx] Dec EBx Mov EDx,ECx Inc ESi Mov EBp, ESi Cmp ECx, 8 Ja @@Wide_String @@Scan3: Push EAx Mov Ch, Al Mov EDx, EDi Call @@CharPos Mov Ch, 0 Sub ECx, EAx Add EDi, EAx Pop EDx Test EAx,EAx Jz @@Exit_False Xchg EAx, EDx Jmp @@CheckLastChar nop nop @@LastDword: Test ECx, ECx Js @@Exit_False Jz @@Exit_False MovD MM7, [Edi] PCMPEQB MM7, MM6 MovD EAx, MM7 Test EAx, EAx Jz @@Exit_False Jmp @@Loop1 nop nop // Aligning code for greater performance @@Wide_String: MovD MM4, EAx Mov Ah, Al MovD MM6, EAx PUNPCKLWD MM6, MM6 PUNPCKLDQ MM6, MM6 @@Scan: MovQ MM7, [Edi] PCMPEQB MM7, MM6 PACKSSWB MM7, MM7 MovD EAx, MM7 Test EAx, EAx Jnz @@CharFound Add EDi, 8 Mov EAx, Edi And EAx, 7 Sub EDi,EAx // Aligning index Sub ECx,8 Add ECx,EAx Cmp ECx,4 Jnge @@LastDword @@Scan2: MovQ MM7, [Edi] PCMPEQB MM7, MM6 PACKSSWB MM7,MM7 MovD EAx, MM7 Test EAx, EAx Jnz @@CharFound Add EDi,8 Sub ECx,8 Cmp ECx,4 Jg @@Scan Jmp @@LastDword @@CharFound: MovQ MM7, [Edi] PCMPEQB MM7, MM6 MovD EAx, MM7 Test EAx, EAx Jnz @@Loop1 Add EDi,4 Sub ECx,4 PSRLQ MM7,32 MovD EAx, MM7 @@Loop1: inc EDi dec Ecx Test Al,Al Js @@Check Shr EAx,8 Jmp @@Loop1 @@Check: MovD EAx, MM4 @@CheckLastChar: // as proposed in Boyer-Mur alhorithm Mov EDx, ECx // store new residual buffer size Test EDx, EDx Js @@Exit_False Test EBx, EBx Js @@Constant_Exists Cmp Ah, [EBx+Edi] Jz @@CompareWholeString Cmp EDx,4 Jg @@Scan Jmp @@LastDWord @@Exit_False: Pop EAx Xor EAx,EAx Jmp @@Leave_Proc @@NotFound_Exit: Xor EAx, EAx Ret @@CompareWholeString: Test EBx, EBx Jz @@Constant_Exists Cmp EDx, EBx Jna @@Exit_False MOV ECX, EBX @@CW_Loop: SUB ECX, 4 JL @@CW_Last123bytes MOV EAX, [ESi+ECx] JZ @@CW_LastDWord CMP EAX, [EDi+ECx] JE @@CW_Loop

Mov ECx, EDx JMP @@SkipBTest1 @@CW_LastDWord: CMP EAX, [EDi] JE @@Constant_Exists Mov ECx, EDx JMP @@SkipBTest1 @@CW_Last123bytes: ADD ECX, 2 JS @@Last1 @@Last3: MOV AX, [ESi] JZ @@Last2 CMP AX, [EDi] JNE @@SkipBTest MOV AL, [ESi+2] CMP AL, [EDi+2] JE @@Constant_Exists Mov ECx, EDx JMP @@SkipBTest1 @@Last2: CMP AX, [EDi] JE @@Constant_Exists Mov ECx, EDx JMP @@SkipBTest1 @@Last1: MOV AL, [ESi] CMP AL, [EDi] JE @@Constant_Exists @@SkipBTest: Mov ECx, EDx @@SkipBTest1: Cmp EDx,4 Jg @@Scan Jmp @@LastDWord @@Constant_Exists2: Add ESp, 4 @@Constant_Exists: Pop EAx Sub EAx, EDx @@Leave_Proc: EMMS Pop EBp Pop EBx Pop ESi Pop EDi End;

> Набережных С. © (04.02.06 08:38) [22]
>
> Хм.
> Файл размером 1 ГБ, памяти в машине 2х256 Мб, хотя в данном
> MMF: 47 - 63 ms

Не реально. Скорость диска у Вас какая? для 60ms получается 1Gb/60ms? Нонсенс.

> Набережных С. © (04.02.06 09:29) [24]
> Пардон, ошибся с просонгья:)) Для MMF результат 470 - 630,
> забыл один оператор в тесте с MMF. Результат для MMF: 1171-
> 1187.

пардон, не заметил Ваш пост, но даже в этом случае что-то не то.
1171-1187 ms -> 1.171-1.187 c, что говорит о скорости диска ~1Gb/s.

> Defunct © (04.02.06 18:50) [31]

Проверил еще раз. Примерно те же цифры - пока система "голая". Когда были запущены некоторые "жоркие" приложения, типа офиса, картина "съезжает" в сторону ReadFile. хотя и не катоастрофически, процентов на 20 быстрее. Диск "Барракуда" SATA150.

> Leonid Troyanovsky © (06.02.06 08:33) [33]

> Игорь Шевченко © (06.02.06 11:54) [34]

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

Ахха! Как зубры вступились - так сразу на попятную :)))

Быстрый способ работы с файлом Найти похожие ветки