Форум АНТИЧАТ

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)
-   С/С++, C#, Delphi, .NET, Asm (https://forum.antichat.xyz/forumdisplay.php?f=24)
-   -   бинарный поиск (https://forum.antichat.xyz/showthread.php?t=175759)

1n0y 02.02.2010 23:29
бинарный поиск
 
собстно решил проапгрейдить поиск в своём удоляторе до бинарного. всё бы нечего, но результаты простого перебора и бинарного поиска заметно отличаются - в объёмных базах бинарный не находит примерно 10% совпадений. wtf?!


вот кусок бинарного:
Код:
//f4, f5 - стринглисты

    f5.sort;
    f4.sort; 
      while I<=f4.Count-1 do
            begin
            verh:=0;
            niz:=f5.count;
            found:=FALSE;
              repeat
              sred:=trunc((niz-verh)/2)+verh;
                if  AnsiPos(f4.Strings[I],f5.strings[sred])<>0
                  then found:=TRUE
                else
                  if  f4.Strings[I < f5.strings[sred]
                    then niz:=sred-1
                  else verh:=sred+1;
              until (verh > niz) or found or (verh = f5.count);
            if found
            then
              begin
              form1.Memo6.Lines.Add(f5.Strings[sred]);
              I:=I+1;
              end
            else
            I:=I+1;
          end
естественно, все стринглисты сортирую перед поиском.
вчомпроблема? или это такая фича бинарного поиска? :)

AlexTheC0d3r 03.02.2010 08:24
Цитата:
Сообщение от 1n0y
собстно решил проапгрейдить поиск в своём удоляторе до бинарного. всё бы нечего, но результаты простого перебора и бинарного поиска заметно отличаются - в объёмных базах бинарный не находит примерно 10% совпадений. wtf?!


вот кусок бинарного:
Код:
//f4, f5 - стринглисты

    f5.sort;
    f4.sort; 
      while I<=f4.Count-1 do
            begin
            verh:=0;
            niz:=f5.count;
            found:=FALSE;
              repeat
              sred:=trunc((niz-verh)/2)+verh;
                if  AnsiPos(f4.Strings[I],f5.strings[sred])<>0
                  then found:=TRUE
                else
                  if  f4.Strings[I < f5.strings[sred]
                    then niz:=sred-1
                  else verh:=sred+1;
              until (verh > niz) or found or (verh = f5.count);
            if found
            then
              begin
              form1.Memo6.Lines.Add(f5.Strings[sred]);
              I:=I+1;
              end
            else
            I:=I+1;
          end
естественно, все стринглисты сортирую перед поиском.
вчомпроблема? или это такая фича бинарного поиска? :)
мб все из-за AnsiPos?

1n0y 03.02.2010 08:42
нублин, юзая простой перебор всё ведь чудесно работает с AnsiPos..

AlexTheC0d3r 03.02.2010 09:09
попробуй pos();

1n0y 03.02.2010 12:18
неа, не помогло..

sn0w 03.02.2010 12:24
это все потуму что строки терминируются ключевым символом, в дос (не помню какая инт) это был $, строковые функции си - 0, а в паскале понятия не имею. для поиска двоичных данных функции поиска подстрок вообще невозможно использовать.

сложного ниче нет. берешь массив паттерна и массив данных, и едешь по массиву сравнивая первый символ паттерна с текущим указателем, если не совпадет - следующий, если совпал - сверяешь второй и тд


Время: 12:38