Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2010.08.27;
Скачать: CL | DM;

Вниз

Задачка   Найти похожие ветки 

 
oldman ©   (2010-03-29 13:03) [40]

А сейчас возникнет второй вопрос -
Как проверить, что слово Б есть слово, а не абракадабра?


 
Думкин ©   (2010-03-29 13:16) [41]

> oldman ©   (29.03.10 13:03) [40]

У меня словарь был. 80 тыс. слов где-то.


 
Sha ©   (2010-03-29 13:52) [42]

в [35] есть еще одна ошибка, отсутсвует проверка
       if CharCount=0 then goto NextString;
перед
       TestNo:=j;
       CharFound:=1;


Вот исправленная и несколько оптимизированная версия.
Здесь присваивание строк не выполняется до тех пор, пока это действительно не будет необходимо.

type
 TStringArray= array of string;
 TIntegerArray= array of integer;

 TCharCounters= packed record
   TestNo: integer;
   CharCount: byte;
   CharFound: byte;
   Rest1:     byte;
   Rest2:     byte;
   end;

procedure ShaFilterDictionaryByString2(var aFiltered: TStringArray;
                                     const aDictionary: TStringArray;
                                     const s: string);
var
 Filter: array[char] of TCharCounters;
 i, j, found: integer;
 ch: char;
 p: pointer;
label
 NextString;
begin;
 SetLength(aFiltered,0);
 SetLength(aFiltered,Length(aDictionary));
 for ch:=Low(char) to High(char) do with Filter[ch] do begin;
   TestNo:=0;
   CharCount:=0;
   CharFound:=0;
   end;
 for i:=1 to Length(s) do inc(Filter[s[i]].CharCount);

 found:=0;
 for j:=0 to Length(aDictionary)-1 do begin;
   p:=pointer(aDictionary[j]);
   for i:=1 to Length(string(p)) do with Filter[string(p)[i]] do begin;
     if TestNo<>j then begin;
       if CharCount=0 then goto NextString;
       TestNo:=j;
       CharFound:=1;
       end
     else if CharFound<CharCount then inc(CharFound)
     else goto NextString;
     end;
   aFiltered[found]:=string(p);
   inc(found);
NextString:
   end;
 SetLength(TIntegerArray(aFiltered),found);
 end;

procedure TForm1.Button2Click(Sender: TObject);
var
 aFiltered, aDictionary: TStringArray;
 s: string;
 i: integer;
begin
 SetLength(aDictionary, Memo1.Lines.Count);
 for i:=0 to Memo1.Lines.Count-1 do aDictionary[i]:=Memo1.Lines[i];
 s:=Edit1.Text;
 ShaFilterDictionaryByString2(aFiltered, aDictionary, s);
 Memo2.Clear;
 for i:=0 to Length(AFiltered)-1 do Memo2.Lines.Add(aFiltered[i]);
 aFiltered:=nil;
 aDictionary:=nil;
 end;


 
Демо ©   (2010-03-29 14:27) [43]

function CheckWordInWord(const A,B: String): Boolean;
var
 i: Integer;
 Symbols: array[0..255] of Byte;
begin
 Result := False;
 ZeroMemory(@Symbols,255);
 for i := 1 to Length(B) do Inc(Symbols[Ord(B[i])]);
 for i := 1 to Length(A) do if Symbols[Ord(A[i])]=0 then Exit;
 Result := True;
end;


Вызов:

 A,B: String;
 i: Integer;
begin
 B := "абракадабра";
 A := "бардак";
 if CheckWordInWord(A,B) then ShowMessage("OK");



 
Демо ©   (2010-03-29 14:29) [44]

Поторопился.
Вот такая функция:

function CheckWordInWord(const A,B: String): Boolean;
var
 i: Integer;
 Symbols: array[0..255] of Byte;
begin
 Result := False;
 ZeroMemory(@Symbols,255);
 for i := 1 to Length(B) do Inc(Symbols[Ord(B[i])]);
 for i := 1 to Length(A) do if Symbols[Ord(A[i])]<=0 then Exit else Dec(Symbols[Ord(B[i])]);
 Result := True;
end;


 
Демо ©   (2010-03-29 14:30) [45]

Блин, да что такое.

function CheckWordInWord(const A,B: String): Boolean;
var
 i: Integer;
 Symbols: array[0..255] of Byte;
begin
 Result := False;
 ZeroMemory(@Symbols,255);
 for i := 1 to Length(B) do Inc(Symbols[Ord(B[i])]);
 for i := 1 to Length(A) do if Symbols[Ord(A[i])]<=0 then Exit else Dec(Symbols[Ord(A[i])]);
 Result := True;
end;


 
Демо ©   (2010-03-29 14:41) [46]


> @!!ex ©   (28.03.10 14:42) [20]
> > [19] [true]TRIx ©   (28.03.10 14:05)pos - ВЕСЬМА не быстрая
> операция.


очень быстрая-)


 
@!!ex ©   (2010-03-29 17:05) [47]

> [46] Демо ©   (29.03.10 14:41)

С каких пор тупой перебор стал быстрым?


 
Демо ©   (2010-03-29 21:53) [48]

А с каких пор, не зная алгоритма, говорят, что он тупой?


 
Демо ©   (2010-03-29 22:03) [49]


> @!!ex ©   (29.03.10 17:05) [47]
> > [46] Демо ©   (29.03.10 14:41)С каких пор тупой перебор
> стал быстрым?


Добавлю, что "тупой перебор" - это цикл FOR.


 
@!!ex ©   (2010-03-29 22:39) [50]

> [48] Демо ©   (29.03.10 21:53)
> А с каких пор, не зная алгоритма, говорят, что он тупой?

Откроешь секрет, как сделать pos быстрым?


 
Демо ©   (2010-03-29 22:49) [51]


> @!!ex ©   (29.03.10 22:39) [50]
> > [48] Демо ©   (29.03.10 21:53)> А с каких пор, не зная
> алгоритма, говорят, что он тупой?Откроешь секрет, как сделать
> pos быстрым?


Открою - ничего делать не надо.


 
@!!ex ©   (2010-03-30 08:03) [52]

> [51] Демо ©   (29.03.10 22:49)
> Открою - ничего делать не надо.

Понятно все с вами.


 
И. Павел ©   (2010-03-30 08:19) [53]

Демо ©, @!!ex ©

Можно же просто протестировать:

var
 s:string="Это пример некоторой довольно-таки длинной строки для проверки команды pos";
 chislo:integer;

...

procedure TForm1.btn1Click(Sender: TObject);
var i, j:integer;
begin
 chislo:=0;
 for i:=1 to 100000000 do
   for j:=1 to Length(s) do
     if s[j]="p" then
     Begin
       chislo:=chislo+j div 10;
       break;
     end;
end;


Результат - 8 сек.

procedure TForm1.btn1Click(Sender: TObject);
var i, j:integer;
begin
 chislo:=0;
 for i:=1 to 100000000 do
     chislo:=chislo+Pos("p", s) div 10;
end;


А этот код выполняется в 2 раза дольше.


 
MBo ©   (2010-03-30 08:27) [54]

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


 
@!!ex ©   (2010-03-30 08:36) [55]

> [53] И. Павел ©   (30.03.10 08:19)

Мне то что тестировать?? Я и так знаю, что pos медленный.


 
Демо ©   (2010-03-30 11:16) [56]


> > [51] Демо ©   (29.03.10 22:49)> Открою - ничего делать
> не надо.Понятно все с вами.


Ну и замечательно. Заблуждайся дальше.


> И. Павел ©   (30.03.10 08:19) [53]


Ты break убери в первом цикле, чтобы уж корректно сравнивать?

PS.

Стоит всё же глянуть исходник... Хоть для того, чтобы знать, о чём спор ведёшь...


 
@!!ex ©   (2010-03-30 11:18) [57]

> [56] Демо ©   (30.03.10 11:16)
> Ты break убери в первом цикле, чтобы уж корректно сравнивать?

то есть "нормальный" алгоритм должен продолжать свою работу и после того как данные уже найдены? :)))


> [56] Демо ©   (30.03.10 11:16)
> Стоит всё же глянуть исходник... Хоть для того, чтобы знать,
> о чём спор ведёшь...

Достаточно знать что он медленный. Смотреть для этого исходники совсем не обязательно.


 
Демо ©   (2010-03-30 11:21) [58]


> @!!ex ©   (30.03.10 11:18) [57]
>Достаточно знать что он медленный.
>  Смотреть для этого исходники совсем не обязательно.


Успехов и дальше в осознании столь значительных собственных знаний.


> то есть "нормальный" алгоритм должен продолжать свою работу
> и после того как данные уже найдены? :)))


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


 
И. Павел ©   (2010-03-30 11:39) [59]


> Ты break убери в первом цикле, чтобы уж корректно сравнивать?

У меня там ищется латинская "p", тоесть почти все символы проходятся. Замедление Без break почти не чувствуется - тоже 8 сек.


 
И. Павел ©   (2010-03-30 11:52) [60]

Демо ©, конечно, партизанит, но думаю, что он имеет ввиду алгоритм, основанный на поиске байта в памяти. В ассемблере я не силен, но думаю, что это довольно быстро, но врят ли быстрее использования массива символов. А преобразование char->string сводит быстроту post на нет.


 
Главный Советник   (2010-03-30 11:57) [61]

Господа, а Вам не кажется, что ветка "потеряла" актуальность?
Автор последний раз отметился
Kerk ©   (28.03.10 15:03) [21]


 
@!!ex ©   (2010-03-30 12:04) [62]

> [60] И. Павел ©   (30.03.10 11:52)

А какая разница что имеет ввиду Демо?
Он пытается спорить с моим утверждением, что Pos - медленно работает.
Как бы не был реализован pos, один фиг его скорость близко не может конкурировать с алгоритмами предложенными ранее(тот же массив, например).


 
oldman ©   (2010-03-30 12:06) [63]


> Как бы не был реализован pos, один фиг его скорость близко
> не может конкурировать с алгоритмами предложенными ранее


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


 
Демо ©   (2010-03-30 12:11) [64]


> И. Павел ©   (30.03.10 11:39) [59]


Не показательно, к сожалению.

Простой - "тупой" перебор (как выразился @!!ex) в случае подстановки констант для поиска будет быстрее любых других способов. (to @!!ex - вот ведь странно как).

Лучше бы привести пример функции, в которой подстрока ищется.
Мне что-то с ходу не представляется вариант такой функции, которая оптимальнее Pos...


 
Демо ©   (2010-03-30 12:12) [65]


> @!!ex ©   (30.03.10 12:04) [62]
> > [60] И. Павел ©   (30.03.10 11:52)А какая разница что
> имеет ввиду Демо?Он пытается спорить с моим утверждением,
>  что Pos - медленно работает.Как бы не был реализован pos,
>  один фиг его скорость близко не может конкурировать с алгоритмами
> предложенными ранее(тот же массив, например).


Вот твои слова:

> @!!ex ©   (28.03.10 14:42) [20]
> > [19] [true]TRIx ©   (28.03.10 14:05)pos - ВЕСЬМА не быстрая
> операция.


Ни про какие массивы ни звука нет.


 
@!!ex ©   (2010-03-30 12:44) [66]

> [65] Демо ©   (30.03.10 12:12)
> Ни про какие массивы ни звука нет.

А ниче, что мы тут конкретный вопрос обсуждаем?


 
Демо ©   (2010-03-30 12:54) [67]


> @!!ex ©   (30.03.10 12:44) [66]
> > [65] Демо ©   (30.03.10 12:12)> Ни про какие массивы ни
> звука нет.А ниче, что мы тут конкретный вопрос обсуждаем?
>


А ничё. Говори конкретно, тогда и вопросы будут конкретные.


 
TUser ©   (2010-03-30 14:32) [68]


> И. Павел ©   (27.03.10 15:56) [8]
>
> Если задача состоит в том, чтобы искать в текущем слове
> много других слов, то можно представить текущее слово в
> виде массива, где 1-ый элемент - количество букв "А" в слове,
>  2-ой - "Б" и т.д. Тогда не нужно будет искать буквы, и
> это, наверное, ускорит алгоритм. Повторюсь - только если
> сравниваемых слов много.

Почему только? Оценка времени такого алгоритма О(Len_1 + Len_2 + Len_A), где Len_1/2 - длина слов, Len_A - размер алфавита. Для метода "в лоб" [2] будет О(Len_1*Len_2). Можно предварительно отсортировать оба слова, тогда получится O(Len_1*ln(Len_2)), но все равно это медленнее, чем О(Len_1 + Len_2 + Len_A).


 
Главный Советник   (2010-03-30 18:47) [69]

@!!ex ©  &  Демо ©

:(
продолжим ...
но лучше в личной перепИске


 
Демо ©   (2010-03-30 19:44) [70]


> Главный Советник   (30.03.10 18:47) [69]
>
> @!!ex ©  &  Демо ©
>
> :(
> продолжим ...
> но лучше в личной перепИске


Здесь однозначно лучше.



Страницы: 1 2 вся ветка

Текущий архив: 2010.08.27;
Скачать: CL | DM;

Наверх




Память: 0.61 MB
Время: 0.177 c
15-1264887010
Юрий
2010-01-31 00:30
2010.08.27
С днем рождения ! 31 января 2010 воскресенье


2-1271934182
Константин
2010-04-22 15:03
2010.08.27
Как удалть объёкты из TObjectList и не уменьшишь при этом ....


15-1274775765
bss
2010-05-25 12:22
2010.08.27
D2006, не работает "Find declaration" на DevExpress объектах


2-1266841096
darts116
2010-02-22 15:18
2010.08.27
Рисуем в Delphi


15-1271414136
ocean
2010-04-16 14:35
2010.08.27
Блокировать сайты в ISA