| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Поиск в бинарном файле [D5, WinXP]
Dimaxx © (2004-09-24 23:32:00)
Страницы: < 1 2 ... 5 6 7 8 9 10 11 12 13 14 >
Сабж. Нужен алгоритм действительно быстрого поиска последовательности байт любой длины в файлах любого размера (до гигабайта). Читать кусками по-деревенски не катит. Раньше у меня был алгоритм, но с падением Фуджика все пропало.
Defunct (2004-09-26 02:52:00) [241]GuAV © (26.09.04 02:16) [23]
> да я знаю
сомнительно
> а Вы смотрите доку по BASM
Я сам такие доки пишу, опираясь на документацию к процессорам.
> например здесь "Result and" - лишнее а Constant[i] содержит лишний UniqueString.
лишний что?
Да.. на фоне всего кода это очень серъезное замечание. см. [16]. Не нравится? напишете лучше, за то же время?
Жаль только у вас будет пример перед глазами, какой-никакой, а все же рабочий.
> и потом я про
>> быстрее почти на 30-40% если оперировать DWORD
Скажите вы меня считаете полным васей или наполовину? С какой радости я должен забесплатнописать или делиться оптимальным кодом поиска?
GuAV (2004-09-26 02:16:00) [242]
> > что то мне не нравится что сег регистры задействованы.
> см. документацию по команде STOS, работает с регистровой
> парой ES:[EDI]. на входе в функцию ES может отличаться от
> DS для этого приняты меры предосторожности.
да я знаю, а Вы смотрите доку по BASM
Вы не должны никогда изменять содержимое сегментных регистров (ds, es и ss указывают на один и тот же сегмент; cs имеет свое собственное значение; fs используется Windows и gs резервирован).
> > и ваще код не нравится...
> хозяин-барин - напишите лучше.
> While Result and (I<Length(Constant)) Do
> Begin
> Inc(I);
> Result := Result and (Constant[i] = Chr(Buffer^[i-2]));
> End;
например здесь "Result and" - лишнее а Constant[i] содержит лишний UniqueString.
и потом я про
> быстрее почти на 30-40% если оперировать DWORD
Defunct (2004-09-26 02:09:00) [243]GuAV © (26.09.04 01:26) [21]
> что то мне не нравится что сег регистры задействованы.
см. документацию по команде STOS, работает с регистровой парой ES:[EDI]. на входе в функцию ES может отличаться от DS для этого приняты меры предосторожности.
> и ваще код не нравится...
хозяин-барин - напишите лучше.
default © (26.09.04 01:17) [20]
> и всё-таки я сомневаюсь что Ваш вариант самый быстрый
реализацию можно сделать быстрее почти на 30-40% если оперировать DWORD. Алгоритма более быстрого вы не найдете.
> скорее уверен что не самый
странно, что у вас доверие к алгоритмам 60-х годов выше чем к алгоритмам 2004 года.
GuAV (2004-09-26 01:26:00) [244]
> Push Ds
> Pop Es
что то мне не нравится что сег регистры задействованы.
и ваще код не нравится... хотя алгоритм может быть и быстрый.
default (2004-09-26 01:17:00) [245][19]
и всё-таки я сомневаюсь что Ваш вариант самый быстрый
скорее уверен что не самый
Defunct (2004-09-26 01:01:00) [246]> не понял "наезда"?
"наезд" был на ссылку, а не на вас.
> почему ерундовая ссылка?
потому что незная возможностей аппаратуры тобиш без практики, любая теория превращается в "пук".
> вообще за что купил за то продал(я её тут взял)
не спорю.
> не понял, вы хотите сказать что тот же к примеру алгоритм Бойера-Мура медленней обычного перебора Вами описанного в
Естественно, алгоритм [1] будет быстрее работать чем алгоритм Бойра-Мура, потому что алгоритм [1] опирается на особенности архитектуры Intel x86 процессора, а господа Бойер и Мур сей особенности не знали и предложили сдвигать всю строку и искать с конца. таким образом в алгоритме Бойера-Мура нелья воспользоваться линейной строковой функцией Repne Scas.
default (2004-09-26 00:51:00) [247]Defunct © (26.09.04 00:26) [17]
не понял "наезда"?
почему ерундовая ссылка?
вообще за что купил за то продал(я её тут взял)
"Это какие такие более серьезные алгоритмы позволят все просмотреть без пересмотра всего файла?"
не понял, вы хотите сказать что тот же к примеру алгоритм Бойера-Мура медленней обычного перебора Вами описанного в [1]?
Defunct (2004-09-26 00:26:00) [248]> конечно надо искать более серьёзные алгоритмы чем тупой перебор в данном случае...
Это какие такие более серьезные алгоритмы позволят все просмотреть без пересмотра всего файла?
default © (25.09.04 22:45) [14]
Куча теории, мало практики. Ссылка ерундовая.
сходите лучше сюда:
www.intel.com
строка поиска:
Pentium Processor Family
Developers manual
Defunct (2004-09-26 00:12:00) [249][15]
Оптимизпцией не занимался и не учитывал выход строки за границу буфера. Оставил эти задачи для вас.
Defunct (2004-09-26 00:04:00) [250]Держите, в 100 мегабайтном файле находит строку менее чем за 1 сек., возможно нужны поправки. Будут вопросы - задавайте.
Type TBuffer = Array[0..1000000-1] of byte;
PBuffer = ^TBuffer;
Function CharPos(AChar:Char; Buffer:Pointer; Size:Integer):Integer;Assembler;
Asm
Cld
Push Es
Push EDi
Push Ds
Pop Es
Mov Al , AChar
Mov EDi, Buffer
Mov ECx, Size
Push ECx
Repne ScasB
Pop EAx
Jnz @@NotMatch
Sub EAx, ECx
Mov Result, EAx // This is odd when optimization is on
Jmp @@Exit
@@NotMatch:
Mov Result, -1
@@Exit:
Pop EDi
Pop Es
End;
Function CompareStrings(Constant:String; Buffer:PBuffer):Boolean;
Var I:Integer;
Begin
Result := True;
I := 1;
While Result and (I<Length(Constant)) Do
Begin
Inc(I);
Result := Result and (Constant[i] = Chr(Buffer^[i-2]));
End;
End;
Function LoadBuffer(var Buffer; var F:File; var SeekPos:Int64):Integer;
Begin
Seek(F, SeekPos);
BlockRead(F, Buffer, 1000000, Result);
SeekPos := FilePos(F);
End;
Function ConstantExists(FileName, Constant: String):Boolean;
Var Buffer : PBuffer;
SeekPos : Int64;
F : File;
BufSize : Integer;
BufPos : Integer;
SearchResult : Integer;
Begin
Result := False;
If FileExists(FileName) Then
Begin
SeekPos := 0;
New(Buffer);
Assign(F, FileName);
Reset(F,1);
Repeat
BufSize := LoadBuffer(Buffer^, F, SeekPos);
BufPos := 0;
While (Not Result) and (BufPos>=0) Do
Begin
SearchResult := CharPos( Constant[1], @Buffer^[BufPos], BufSize-BufPos );
If SearchResult>0 Then BufPos := BufPos + SearchResult
Else BufPos := -1;
If SearchResult<>-1 Then
Begin
Result := CompareStrings(Constant, @Buffer^[BufPos]);
BufPos := BufPos + 1;
End;
If BufPos>=BufSize Then BufPos := -1;
End;
Until (BufSize=0) Or Result;
Close(F);
End;
End;
procedure TForm1.Button3Click(Sender: TObject);
begin
If ConstantExists(Edit1.Text, Edit2.Text) Then
ShowMessage('Found')
Else
ShowMessage('Not Found');
end;
default (2004-09-25 22:45:00) [251]http://www.3ka.mipt.ru/vlib/books/Programming/ComputerScience/StryngAnalysis/
вот тут недавно эту ссылку кидали
GuAV (2004-09-25 22:44:00) [252]
> конечно надо искать более серьёзные алгоритмы чем тупой
> перебор в данном случае...
Может я и ошибаюсь, но имхо тупой перебор - самое быстрое.
При этом буфер большой, и за один такт перебора обрабатывать данные размером в машинное слово, т.е. 4 байта.
default (2004-09-25 22:41:00) [253]конечно надо искать более серьёзные алгоритмы чем тупой перебор в данном случае...
GuAV (2004-09-25 22:34:00) [254]
> Dimaxx (25.09.04 21:52) [9]
Надо через SCASB/SCASW/SCASD искать первые 1/2/4
а потом CompareMem.
Defunct (2004-09-25 22:18:00) [255]Dimaxx (25.09.04 21:52) [9]
Значит криво сделал.
Сейчас потрачу полчаса, и докажу обратное. Не может там тратиться 2-5 секунд.
Dimaxx (2004-09-25 21:52:00) [256]2 Defunct: Подобное делал. Туфта, ибо кусок в 1 метр файла просматривается около 2-5 секунд, а это очень много. А если мне нужно искать в одном файле несколько разных образцов? Тогда ваще тормоз получается. TotalCommander просматривает за это время 30-40 метров.
А хде посмотреть про алгоритм Кнута-Мориса-Пратта?
TUser (2004-09-25 15:06:00) [257]См. например, алгоритм Кнута-Мориса-Пратта. Серьезные люди его придумали ...
Anatoly Podgoretsky (2004-09-25 11:18:00) [258]GuAV © (25.09.04 01:37) [3]
А раз не катит, то путей немного - все в память, можно через MMF
Defunct (2004-09-25 02:39:00) [259]Германн © (25.09.04 02:08) [5]
винт такой, они сейчас почти все сыпятся.
Германн (2004-09-25 02:08:00) [260]А кто такой "Фуджик" и куда он упал?
| |
