| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / 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-28 03:06:00) [161]> Насколько она быстрее при работе с обычными строками (длиной 30-100 символов)
Pos будет медленнее, так как в стадартной функции Pos две пары Push/Pop в основном цикле поиска и не рассмотривается вариант отбраковки подстроки по первому и последнему символам.
На сколько медленнее сказать сейчас не могу. На маленьких строках тяжело точно измерить скорость, куча побочных эффектов, например, просто факт вызова функции (команда Call) отнимает примерно столько времени сколько потребуется на просмотр 2-5 символов, согласитесь немало при длинне строки в 30 символов.
jack128 (2004-09-28 02:42:00) [162]Defunct © (28.09.04 2:29) [102]
работает более чем в два раза быстрее чем встроенная функция поиска подстроки в строке:
Ага, сели два чела, 4 дня провозились и еще и удивляются, как же у них получилась функция, которая быстрее стандартной реализации ;-)
зы Pos - не ориентирован на поиск подстроки в 1Гб файле. Насколько она быстрее при работе с обычными строками (длиной 30-100 символов)
ззы вашу функцию нужно в базу знаний отправить.
Defunct (2004-09-28 02:29:00) [163]> найти места где Вы не согласны с Borland и разобраться почему они всё же правы.
Знаете, не надо так свято верить в правоту Borland, функция [74] - быстрее Pos, а та к которой мы с вами в итоге пришли после усовершенствования [74] работает более чем в два раза быстрее чем встроенная функция поиска подстроки в строке: Pos. И это не первая функция на моем счету, которая доказывает, что не все решения от Borland оптимальны.
> F1 - интересно, Ctrl+Click - ещё интереснее,
Хелп сделан хорошо, здесь упреков нет.
> на самом деле, лучше вообще без except. тогда будет выведен текст исключения в сообщении
Это уж кому как, я предпочту чтобы программа умолчала об исключении вместо того чтобы показала, что исключение в ней не обрабатывается.
> почему именно не получилось. может не файл не найден а ещё что-то. хотя бы EOutOfMemory.
Ну что ж тогда увы и ах..:
<begin offtop>
.. в одном отдаленном селе Василий Певченко скачал шареварную версию нового "PuperCommander". С возгласом:
- ну наконец-то, догожданная новая версия,
Василий принялся изучать Readme файл со списоком новых возможностей и улучшений...
- О! быстрый поиск строки, сейчас посмотрю, что они там намутили, - улыбнулся Василий, который несколько лет ждал именно эту фичу.
Он задавал имя файла и ввел "смешные анеГДОТЫ" в раскрашенном поле строки поиска, к его глубочайшему удивлению на экране возникало сообщение "Да ну нет такого файла!". Василий повторял ввод имени раз за разом, раз за разом, но на экране в также весело красовалась пестрая надпись с заголовком PuperCommander, уведомляющая, что такого файла нет. Василий вспомнил, что вчера выпил не мало, об этом напиминали трясущиеся руки, и решил скопировать имя файла прямо из проводника самой модной операционки "ГунДоус" от корпорации "МодныйСофт". А на экране все также пестрилась веселая надпись "Да не найден, надо меньше пить". В гневе Василий нажал кнопку "ПЫтание" на корпусе своего модного компутера "ИВМ" от фирмы "Красночух Электроникс", замигали лампочки, в динамиках раздался приятный женский голос "подождите пожалуйста, ГунДоус приступил к первой фазе подготовки к выполнению завершения вашей работы". Василий ждал..
.....
...
..
Экран засветился, потом погас, потом опять засветился на этот раз с надписью "Красночух Электроникс БИОС, ждите", замигали лампочки. Василий потихоньку приходил в себя, он взял очередную бутылочку пива из холодильника и удобно развалился на кресле с мягкой спинкой. Наблюдая за меняющимися картинками, которыми обычно сопровождается загрузка модной системы "ГунДоус", он размышлял о том, что он самый счастливый человек на свете. Теперь у него есть "PuperCommander" и он сможет с гордостью похвастаться об этом своим друзьям. "ГунДоус" пригласил Василия ввести пароль, после чего Василий сразу же запустил "PuperCommander" ввели имя файла и.... О чудо! ни каких надписей, пестрая табличка с вопросом "смешные анеГДОТЫ найдены, показать?".
- Глючный ГунДоус, - подумал Василий, - когда уже эти олухи из корпорации "МодныйСофт" сделают что-то нормальное..
<end offtop>
И в чем-то Василий будет прав.
В данном конкретном случае меня не интересуют другие ошибки кроме "файл не найден" так как логически там их быть не может, кроме случая - ошибка ОС.
GuAV (2004-09-28 01:21:00) [164]знаете, как можно узнать про флаг D, отсутсвие результата при exception и т.д. ?
посмотреть исходники VCL, найти места где Вы не согласны с Borland и разобраться почему они всё же правы.
см. мою анкету -
F1 - интересно, Ctrl+Click - ещё интереснее,
Defunct © (28.09.04 01:00) [99]
на самом деле, лучше вообще без except. тогда будет выведен текст исключения в сообщении, почему именно не получилось. может не файл не найден а ещё что-то. хотя бы EOutOfMemory.
или уже например что-то типа
Try
If ConstantExists(Edit1.Text, Edit2.Text)>0 Then
ShowMessage('Found')
Else
ShowMessage('Not Found');
Except
on EInOutErrordo ShowMessage('file '+Edit1.Text+' not found');
End;
except без on следует использовать только если внутри raise; - т.е. исключение сохранится для дальнейшего использования.
Defunct (2004-09-28 01:03:00) [165]GuAV © (28.09.04 00:59) [98]
Ок, убедили, признаю - страдать фигней незачем.
Defunct (2004-09-28 01:00:00) [166]PS: код [97] серьезно не воспринимать, правильно должно быть так:
procedure TForm1.Button1Click(Sender: TObject);
begin
Try
If ConstantExists(Edit1.Text, Edit2.Text)>0 Then
ShowMessage('Found')
Else
ShowMessage('Not Found');
Except
ShowMessage('file '+Edit1.Text+' not found');
End;
end;
GuAV (2004-09-28 00:59:00) [167]Defunct © (28.09.04 00:56) [97]
Это похоже на уровне "повезло", попробуйте
Var Position : Int64; - глобальная переменная.
Defunct (2004-09-28 00:56:00) [168]> я не пробовал, но даже немного сомневаюсь что возможно получить результат в этом случае. если можете - покажите как Вы бы это делали.
Беру функцию [87]
Использую ее так:
procedure TForm1.Button1Click(Sender: TObject);
Var Position : Int64;
begin
Try
Position := ConstantExists(Edit1.Text, Edit2.Text);
Except
End;
If Position>0 Then
ShowMessage('Found')
Else
ShowMessage('Not Found');
End;
end;
В Edit1 ввожу какую-то лабуду типа "sdfsdf.asdasd" в Edit2 - "Test String" возникает исключение на экране вижу "Not Found". Хотя понятно, тест синтетический проще было бы в обработчике исключения написать, что файла с таким именем нет. ;)
GuAV (2004-09-28 00:38:00) [169]
> > более того я даже не вижу возможности им воспользоваться.
> А я вижу, когда "наплевать" на исключения, их просто проигнорируют,
> а результат функции будет верным.
> Тока не надо говорить, что так делать не правильно, сам
> знаю, но все равно делаю ;)
например если
I:=MyFunc
и в MyFunc - исключение, то в I остаётся старое значение
я не пробовал, но даже немного сомневаюсь что возможно получить результат в этом случае. если можете - покажите как Вы бы это делали.
Defunct (2004-09-28 00:32:00) [170]GuAV © (27.09.04 23:58) [93]
конечно принято!
GuAV © (28.09.04 00:09) [94]
> в случае исключения результат функции не нужен
почему бы не перестраховаться. пусть возвращает правильный результат даже в исключительной ситуации. (нам тока спасибо скажут)
> более того я даже не вижу возможности им воспользоваться.
А я вижу, когда "наплевать" на исключения, их просто проигнорируют, а результат функции будет верным.
Тока не надо говорить, что так делать не правильно, сам знаю, но все равно делаю ;)
GuAV (2004-09-28 00:09:00) [171]
> GuAV © (27.09.04 23:26) [88]
>
> Дык, в секции finally посмотрите If bufpos<0....
> и сброс перед поиском Result := FilePos
ок.
Всё же вариант [89] ничем не хуже, только проще.
If BufPos < 0 Then Result := -1;
кстати подобный код следует размещать после until перед finally, но не в finally. дело в том, что в случае отсутствия исключения он и так выполнится. в случае исключения результат функции не нужен, более того я даже не вижу возможности им воспользоваться.
GuAV (2004-09-27 23:58:00) [172]сорри, Ж нажал вместо КОД
Mov ECx, Ebx // ECx - constant chars amount
shr ECx, 2 // ECx - constant chars amount div 4
jz @@SkipDTest
Repe CmpsD
Jnz @@SkipBTest
@@SkipDTest:
Mov ECx, Ebx
and ECx, 3
jz @@Constant_Exists // two least significant bits
// of amount is zero so the Constantmatches
Repe CmpsB
Jz @@Constant_Exists
@@SkipBTest:
принято ?
GuAV (2004-09-27 23:57:00) [173]Mov ECx, Ebx // ECx - constant chars amount
shr ECx, 2 // ECx - constant chars amount div 4
jz @@SkipDTest
Repe CmpsD
Jnz @@SkipBTest
@@SkipDTest:
Mov ECx, Ebx
and ECx, 3
jz @@Constant_Exists // two least significant bits
// of amount is zero so the Constant matches
Repe CmpsB
Jz @@Constant_Exists
@@SkipBTest:
?
Defunct (2004-09-27 23:45:00) [174]GuAV © (27.09.04 23:26) [88]
Дык, в секции finally посмотрите If bufpos<0....
и сброс перед поиском Result := FilePos
Defunct (2004-09-27 23:38:00) [175]GuAV © (27.09.04 23:03) [86]
принимается с поправками, а то получим нехилую ошибку при Length(Constant)<=6 и при (Length(Constant)) mod 4 = 0.
@@CompareWholeString:
Mov ECx, Ebx // ECx - constant chars amount
shr ECx, 2 // ECx - constant chars amount div 4
jz @@SkipDTest
Repe CmpsD
Jnz @@SkipBTest
@@SkipDTest:
Mov ECx, Ebx
and ECx, 3
jz @@SkipBTest
Repe CmpsB
Jz @@Constant_Exists
@@SkipBTest:
Mov ESi, EBp // restore pointer to 2nd char of constant
В общем, получилось просто отлично. на том же файле (gladiator.avi) строка поиска ("01wbcb") время просмотра всего файла - 13.43 сек (было 13.71). Для больших строк конечно же ускорение будет выше.
Попробовал поиграться с размером буфера:
- 10MB скорость падает
- делаю 512Kb - скорость падает.
(Кеш L2 у меня 1Mb) потому 1Mb - оптимально как для машины на которой проводил тесты.
GuAV (2004-09-27 23:29:00) [176]
> Поправлю, вы забыли учесть откат на Length(Constant):
Тогда
Function ConstantExists(FileName, Constant: String): Int64;
Var
Buffer : PBuffer;
F : File;
BufSize : Integer;
BufPos : Integer;
Begin
New(Buffer);
try
AssignFile(F, FileName);
Reset(F,1);
try
Repeat
Result := FilePos(F);
BlockRead(F, Buffer^, MaxBufferSize, BufSize);
If BufSize < Length(Constant) Then Break;
BufPos := ConstantPos(Constant, Buffer, BufSize);
if BufPos > 0 then
begin
Inc(Result, BufPos);
Exit;
end;
{Inc(Result, BufSize);}
Seek(F, FilePos(F) - Length(Constant));
Until (BufSize<MaxBufferSize);
Result := -1;
finally
CloseFile(F);
end;
finally
Dispose(Buffer);
end;
End;
GuAV (2004-09-27 23:26:00) [177]
> If BufSize >= Length(Constant) Then
> BufPos := ConstantPos(Constant, Buffer, BufSize);
> Result := Result + BufPos;
Result будет накапливать -1.
Defunct (2004-09-27 23:13:00) [178][84]
Поправлю, вы забыли учесть откат на Length(Constant):
Function ConstantExists(FileName, Constant: String): Int64;
Var
Buffer : PBuffer;
F : File;
BufSize : Integer;
BufPos : Integer;
Begin
BufPos := -1;
New(Buffer);
try
AssignFile(F, FileName);
Reset(F,1);
try
Repeat
Result := FilePos(F);
BlockRead(F, Buffer^, MaxBufferSize, BufSize);
If BufSize >= Length(Constant) Then
BufPos := ConstantPos(Constant, Buffer, BufSize);
Result := Result + BufPos;
Seek(F, FilePos(F) - Length(Constant));
Until (BufPos>0) or (BufSize<MaxBufferSize);
finally
CloseFile(F);
end;
finally
If BufPos < 0 Then Result := -1;
Dispose(Buffer);
end;
End;
GuAV (2004-09-27 23:03:00) [179]такой вариант принимается ?
@@CompareWholeString:
Mov ECx, Ebx // ECx - constant chars amount
shr ECx, 2 // ECx - constant chars amount div 4
Repe CmpsD
Jz @@Constant_Exists
Mov ECx, Ebx
and ECx, 3
Repe CmpsB
Jz @@Constant_Exists
или наоборот, сначала B а потом D
Mov ECx, Ebx // ECx - constant chars amount
shr EBx, 2 // EBx - constant chars amount div 4
and ECx, 3
Repe CmpsB
Jz @@Constant_Exists
Mov ECx, Ebx
Repe CmpsD
Jz @@Constant_Exists
GuAV (2004-09-27 22:59:00) [180]
> if BufPos > 0 then
BufPos => 0 или BufPos <> -1.
| |
