Оптимизация алгоритма поиска Бойера-Мура

Знаю, что тема поднималась не один раз, перечитал много всяких статей, но там работы со строками почти всегда =\

Ну ближе к делу...

Значит заюзал я для поиска алгоритма Бойера-Мура. (с воможностью масок "??") делаю так, читаю буфер,

и ищу уже в нём... (чуть изменил алго, чтобы он работал с массивом байт) Пока только для 2-ух сигн, но уже получается не очень быстро... где я косячу, или быстрее уже нельзя (могу ещё периписать работу с файлами через маппирование)...

Код (Text):

1.  
2. // если делать таблицу в цикле поиска, то получается
3. // очень накладно...
4.   sData:=sign(1); // получаем строку для поиска
5.   GetMem(BMT[1], SizeOf(TIntVect)*Length(sData));
6.   WCMakeBMTable(BMT[1], sData);//делаем таблицу
7.   sData:=sign(2); // получаем строку для поиска
8.   GetMem(BMT[2], SizeOf(TIntVect)*Length(sData));
9.   WCMakeBMTable(BMT[2], sData); //делаем таблицу
10.   _Read:=0;
11.   DD:=65536; //рамер буфера
12.   Speed:=GetTickCount; // засекаем
13.   _Size:=LfstFile.Size;
14.   repeat
15.     If (_Size-_Read) < DD then
16.     begin
17.       fillchar(buf,sizeof(buf),0);
18.       dd:=_Size-_read;
19.     end;
20.     LfstFile.Seek(_Read,soBeginning);
21.     LfstFile.Read(buf,DD);
22.     update; //чтоб форма не подвисала =)
23.     For i:=1 to 2 do
24.     begin
25.       sData:=sign(i);
26.       n:=BMSearch(1,length(sData),buf,BMT[i]); //ищем
27.       If n <> 0 then
28.       begin
29.         Edit1.text:=inttostr(_Read+n);
30.         memo1.Lines.Add('Found ! ['+inttostr(i)+']');
31.         FreeMem(BMT[1]);
32.         FreeMem(BMT[2]);
33.         LfstFile.Free;
34.         exit;
35.       end;
36.     end;
37.     PG.Position:=_Read; // отмечаем прогресс
38.     _Read:=_Read+DD;
39.   until _Read >= _Size;
40.  

 

imho в выборе языка

 

разве на другом будет быстрее? =\

ну можно и асм встаку заюзать...

на будет ли ощутимый прирост в скорости?

а то я уже замучился +) ну никак быстро

не получается...

 

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

Код (Text):

1.       end;
2.     end;
3.     GlobalVar:=_Read; // отмечаем прогресс
4.     _Read:=_Read+DD;
5. ...
6. // где-то в потоке
7. while(Working)
8. {
9.   PG.Position:=GlobalVar; // отмечаем прогресс
10.   Wait(SomePeriod);
11. }
12.  

 

Hellspawn

Я не пойму, а где здесь алгоритм?

 

Hellspawn

разве на другом будет быстрее? =\



Забей. Всяк сектант свое болото хвалит. А чужое, соответственно, ругает. Это мода такая, ей либо следуют, либо на нее плюют. Я практикую второй путь.



LfstFile.Seek(_Read,soBeginning); - Это явно лишняя деталь



update; //чтоб форма не подвисала =) - Ага, и чтобы ТОРМОЗИИИИЛА



Edit1.text:=inttostr(_Read+n);

memo1.Lines.Add('Found ! ['+inttostr(i)+']'); - 2 обращения к окнам, дикий тормоз по определению



FreeMem(BMT[1]);

FreeMem(BMT[2]); - Это тоже рабоатет небыстро. Причем в семерке - замтно медленней, чем в Delphi 2006. Надо использовать самые прогрессивные продукты

 

а где на форуме/сайте написано что здесь собираются любители дельфи?

 

Asterix

Здесь собираются любители кода, а не языков программирования

Что касается задачи, код явно надо выполнять в отдельном потоке... Или накрайняк вызывать Update не чаще 5 раз/сек (функция GetTickCount в помощь, и не только).

 

ну да, под маппирование перепишу...

дык оно уже обращается после поиска =)

а вот убрать update х.м. но тогда форма будет подвисать...

спс попробую...



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



добавлено... а можно так...

допустим будет у меня 3 потока... и 30 сигн

1-ый ищет 1-10 сигну в данном буфере

2-ой 11-20 и т.д.

имеет ли смысл данное разделение? ли 1-ого потока будет вполне достаточно?

 

можно было бы и подробней обрисовать ситуацию.

Что за сигнатура (какова длина)?

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



Маппирование будет только тормозить. Даже если файл не влазит целиком в озу, выгоднее читать частями, чем постоянно крутить винт. Маппировать имеет смысл, если тебе нужны произвольные части всего файла в случайном порядке, как например при сортировке. При поиске идет последовательный перебор, скакать по разным частям файла не надо.



Отдельные потоки скорости поиска не прибавят, только появится возможность разморозить апдейт формы.

 

длина сигн разная... от 20 байт до 200 где-то так...

хм... просто у меня в проге файл по умолчанию маппируется (для других целей) значит сделать что-то типа MOVE(FP,BUF^,SIZE) - будет долго?

 

Преимущества маппирования - возможность получения доступа к любой части файла большого размера, который невозможно целиком поместить в озу. Это свойство при поиске не нужно (ты же не ищешь в начале файла, затем скачок в конец файла, затем поиск где-нибудь в середине). А при маппировании постоянно крутится винт - вот это и есть главный тормоз.



И какого порядка получается время поиска (при какой сигнатуре и размере файла?)

 

файл порядка 7 метров...

2 сигнатуры байт по ~25

GetTickCount до и после.. разность ~150

можно ещё быстрее... но главный вопрос вот в чём...

я для сигн до поиска делаю

GetMem(...)

WCMakeBMTable(...)

а если их будет порядка 100 =\



значит предлагаешь использоать FileStream? Или всё таки можно ещё через createfile а потом readfile? =)

и какой самый быстрый способ работы с файлами? а то

меня во всех статьях убеждали, что маппирование рулит =)

 

7 метров - дак этож копейки... Можно просто статик-массив зафигачить и не париться с GetMem и иже с ними..



„n:=BMSearch(1,length(sData),buf,BMT); //ищем“



Где алгоритм??? Чтоб асмовый, оптимизированый под MMX/SSE!



Цитата by CyberManiac

Всяк сектант свое болото хвалит.





семерке - замтно медленней, чем в Delphi 2006. Надо использовать самые прогрессивные продукты





Вопрос по фичам (и вообще)BDS2006. Че там за совместимость с .NET? D9 - уж не псевдокодовый ли?

В обджи делать умеет? MS-Linker эти обджи хавает??

 

7 метров в статик массив? =\ а не будет ли компьютеру больно +) а алго взят из одной статьи...

http://www.rsdn.ru/article/alg/textsearch.xml

 

а не будет ли компьютеру больно

фик его знает, опиши что за компутер (проц/памить/винт/операционка)...



У меня P3_1300T/RAM256Mb/20Гб/Win200SP2...



Со статическим аллокачиванием 64МВ вроде ноу проблем...





{$apptype console}

program hello;

var i : cardinal;

var j : array [0..65000000] of byte;

begin

for i:=0 to 65000000 -1 do j := 123;

end.



Грузиться и сканирует 64MB меньше чем за секунду...

 

Ха, попробовал сейчас сравнить с ReadFile и с MapViewOfFile.

Файл 7 Мб, сигнатуры по 25 байт. Искал 12 сигнатур (6 в середине файла и 6 в конце файла).

с ReadFile получается 12 сигнатур - 120 мс

с MapView получается 12 сигнатур - 110 мс.



Разница ~10%

Хотя предыдущий опыт с сортировкой файлов ReadFile был в 2-3 раза быстрее.



Теперь уверенности нет, надо видимо тебе самому пробовать два способа и сравнивать.

 

Вот нашел алго в сорцах MASM'а...



[]



Хм... оптимизировать есть что...

 

значит маппирование не так плохо и для моих целей подходит?

каким поиском то? bm?

ну в принципе мне досточно... =) единственное для таблиц надо будет что-то придумать, если их много будет =\ ведь память под них динамически резервируется...



и ещё... целесообразно ли весь файл грузить в оперативку?

или всё таки лучше частями?