| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Быстрый способ работы с файлом
Piter © (2006-02-03 14:33:00)Ищется быстрый способ открыть текстовый файл, найти там нужную последовательность символов, скопировать в строку от этой последовательности до другой последовательности.
Файл может занимать несколько десятков мегабайт или даже больше сотни.
Piter (2006-02-06 13:42:00) [1]Ахха! Как зубры вступились - так сразу на попятную :)))
Набережных С. (2006-02-06 12:50:00) [2]
> Leonid Troyanovsky © (06.02.06 08:33) [33]
> Игорь Шевченко © (06.02.06 11:54) [34]
Тест-то простой, да только я его повторить не могу. В общем, тут у друга юбилей был, намерить мог что угодно. Все, сказанное мной с вечера пятницы по вечер воскресенья всерьез воспринимать не стоит. Прошу извинить. Пора мне, однако, отдохнуть от форума.
Игорь Шевченко (2006-02-06 11:54:00) [3]Набережных С. © (05.02.06 17:53) [32]
Тест в студию не затруднит ? Мне тоже интересно :)
Leonid Troyanovsky (2006-02-06 08:33:00) [4]
> Набережных С. © (05.02.06 17:53) [32]
Кинь, плиз, твой тест - вечером попробую на w2k, w2k3.
--
Regards, LVT.
Набережных С. (2006-02-05 17:53:00) [5]
> Defunct © (04.02.06 18:50) [31]
Проверил еще раз. Примерно те же цифры - пока система "голая". Когда были запущены некоторые "жоркие" приложения, типа офиса, картина "съезжает" в сторону ReadFile. хотя и не катоастрофически, процентов на 20 быстрее. Диск "Барракуда" SATA150.
Defunct (2006-02-04 18:50:00) [6]
> Набережных С. © (04.02.06 09:29) [24]
> Пардон, ошибся с просонгья:)) Для MMF результат 470 - 630,
> забыл один оператор в тесте с MMF. Результат для MMF: 1171-
> 1187.
пардон, не заметил Ваш пост, но даже в этом случае что-то не то.
1171-1187 ms -> 1.171-1.187 c, что говорит о скорости диска ~1Gb/s.
Defunct (2006-02-04 18:46:00) [7]
> Набережных С. © (04.02.06 08:38) [22]
>
> Хм.
> Файл размером 1 ГБ, памяти в машине 2х256 Мб, хотя в данном
> MMF: 47 - 63 ms
Не реально. Скорость диска у Вас какая? для 60ms получается 1Gb/60ms? Нонсенс.
kaZaNoVa (2006-02-04 15:52:00) [8]
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;
kaZaNoVa (2006-02-04 15:51:00) [9]
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
Piter (2006-02-04 15:46:00) [10]guav © (04.02.06 15:19) [26]
а, понял. Ну так получается двойной проход одного места...
guav (2006-02-04 15:19:00) [11]
> а если искомая строка будет разбита границой буфера?
> Тогда она может не найтись, хотя есть.
см. внимательно п. 5
Piter (2006-02-04 14:15:00) [12]Defunct © (04.02.06 5:59) [19]
а если искомая строка будет разбита границой буфера? Тогда она может не найтись, хотя есть.
Набережных С. (2006-02-04 09:29:00) [13]Пардон, ошибся с просонгья:)) Для MMF результат 470 - 630, забыл один оператор в тесте с MMF. Результат для MMF: 1171-1187.
Набережных С. (2006-02-04 08:48:00) [14]Да, забыл - система WiXP SP2. Хотя, как помнится, на W2k я получал примерно то же соотношение.
Набережных С. (2006-02-04 08:38:00) [15]
> 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
Может, они не умеют их готовить? Или это я что-то неправильно понял?
Defunct (2006-02-04 06:03:00) [16]блин, коряво получилось из-за того, что первый вариант ответа, который я написал - пропал из-за ошибки соединения с сервером, а второй уже писал с меньшим энтузиазмом и с большим числом ошибок.
> а поиск производит достаточно быстро - 20-25 сек при скорости диска - 50-60MBps.
20-25 сек на Гигабайт!
Defunct (2006-02-04 06:01:00) [17]> "отрывает"
typo.. читать "открывает"..
Defunct (2006-02-04 05:59:00) [18]> Piter
Поиск по бинарнику должен подойти. Помните где-то полтора года назад мы тут с GuAV ветку раздули о бинарном поиске. Так вот тот метод не имеет впринципе такого понятия как "отрывает", а поиск производит достаточно быстро - 20-25 сек при скорости диска - 50-60MBps.
Алгоритм предельно прост - тот же FileMapping только с применением оптимального объема окна +быстрая функция поиска подстроки в строке.
1. Берем окно (буфер) объемом L2, куда будем осуществлять считывание порции файла.
2. Считываем порцию файла
3. Ищем искомую строку.
4. Нашли - хорошо (выход).
5. Не нашли - позиционируем файловый указатель назад на длину искомой строки и продолжаем с п.2.
Leonid Troyanovsky (2006-02-03 19:43:00) [19]
> Игорь Шевченко © (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:00) [20]Вот реализация алгоритм КМП. Отображение в память сам пиши.
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.
| |
Страницы: 