Форум: "Основная";
Текущий архив: 2006.03.12;
Скачать: [xml.tar.bz2];
ВнизБыстрый способ работы с файлом Найти похожие ветки
← →
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]
> Игорь Шевченко © (03.02.06 19:16) [15]
> а с ним спорить мне тем более не хочется. Искать что-либо
> наиболее просто, как мне кажется, в MMF, в данном случае
> для меня критерием является простота.
Насчет простоты, я, кажется уже снабжал Piter"a ссылкой
http://groups.google.com/group/fido7.ru.delphi/msg/64b9f15bdadf6923
Но, видимо, она ему в этой задаче не очень пригодилась.
Кстати, в том обсуждении меня убедили, что CompareMem в [9]
будет нехорошо. Запамятовал, каюсь :)
--
Regards, LVT.
← →
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]
а если искомая строка будет разбита границой буфера? Тогда она может не найтись, хотя есть.
← →
guav © (2006-02-04 15:19) [26]
> а если искомая строка будет разбита границой буфера?
> Тогда она может не найтись, хотя есть.
см. внимательно п. 5
← →
Piter © (2006-02-04 15:46) [27]guav © (04.02.06 15:19) [26]
а, понял. Ну так получается двойной проход одного места...
← →
kaZaNoVa © (2006-02-04 15:51) [28]
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
← →
kaZaNoVa © (2006-02-04 15:52) [29]
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;
← →
Defunct © (2006-02-04 18:46) [30]
> Набережных С. © (04.02.06 08:38) [22]
>
> Хм.
> Файл размером 1 ГБ, памяти в машине 2х256 Мб, хотя в данном
> MMF: 47 - 63 ms
Не реально. Скорость диска у Вас какая? для 60ms получается 1Gb/60ms? Нонсенс.
← →
Defunct © (2006-02-04 18:50) [31]
> Набережных С. © (04.02.06 09:29) [24]
> Пардон, ошибся с просонгья:)) Для MMF результат 470 - 630,
> забыл один оператор в тесте с MMF. Результат для MMF: 1171-
> 1187.
пардон, не заметил Ваш пост, но даже в этом случае что-то не то.
1171-1187 ms -> 1.171-1.187 c, что говорит о скорости диска ~1Gb/s.
← →
Набережных С. © (2006-02-05 17:53) [32]
> Defunct © (04.02.06 18:50) [31]
Проверил еще раз. Примерно те же цифры - пока система "голая". Когда были запущены некоторые "жоркие" приложения, типа офиса, картина "съезжает" в сторону ReadFile. хотя и не катоастрофически, процентов на 20 быстрее. Диск "Барракуда" SATA150.
← →
Leonid Troyanovsky © (2006-02-06 08:33) [33]
> Набережных С. © (05.02.06 17:53) [32]
Кинь, плиз, твой тест - вечером попробую на w2k, w2k3.
--
Regards, LVT.
← →
Игорь Шевченко © (2006-02-06 11:54) [34]Набережных С. © (05.02.06 17:53) [32]
Тест в студию не затруднит ? Мне тоже интересно :)
← →
Набережных С. © (2006-02-06 12:50) [35]
> Leonid Troyanovsky © (06.02.06 08:33) [33]
> Игорь Шевченко © (06.02.06 11:54) [34]
Тест-то простой, да только я его повторить не могу. В общем, тут у друга юбилей был, намерить мог что угодно. Все, сказанное мной с вечера пятницы по вечер воскресенья всерьез воспринимать не стоит. Прошу извинить. Пора мне, однако, отдохнуть от форума.
← →
Piter © (2006-02-06 13:42) [36]Ахха! Как зубры вступились - так сразу на попятную :)))
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2006.03.12;
Скачать: [xml.tar.bz2];
Память: 0.58 MB
Время: 0.014 c