Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 2010.08.27;
Скачать: [xml.tar.bz2];

Вниз

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

 
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;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.59 MB
Время: 0.074 c
15-1264338698
Андрей Миронов
2010-01-24 16:11
2010.08.27
Поясните работу с множествами


15-1267337984
Kerk
2010-02-28 09:19
2010.08.27
Некачественное выполнение госконтракта


2-1265842864
defen
2010-02-11 02:01
2010.08.27
Autorun


2-1266950781
Женя
2010-02-23 21:46
2010.08.27
Перенос строки при экспорте из acces в dbgrid


15-1271696488
sniknik
2010-04-19 21:01
2010.08.27
Кодировки в RSS.





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский