Функция PosEx из Share.pas

Вверх ↑

Форумы ПрочееФункция PosEx из Share.pas ← Ctrl123 4 5 6...8 9 10 11 12Ctrl →

Этот топик читают: Гость

Разработчик

Ответов: 26200

Рейтинг: 2137

#16: 2010-04-20 17:08:16 ЛС | профиль | цитата

Tad, проверь на строках длиной по 1 - 2 Mb, минимум. Вот тогда и посмотрим результат, а так это -- пустые слова

карма: 22

Ответов: 16884

Рейтинг: 1239

#17: 2010-04-20 17:13:51 ЛС | профиль | цитата

nesco, строку длинной в 1-2 мб еще придумать надо.

Подскажи - где такую найти ?
------------ Дoбавленo в 17.13:

Леонид писал(а):

эту схему я не буду даже скачивать

Да старость не радость.

карма: 25

Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!

Разработчик

Ответов: 26200

Рейтинг: 2137

#18: 2010-04-20 17:14:42 ЛС | профиль | цитата

Tad писал(а):

строку длинной в 1-2 мб

Возьми обычный текст такой длины, вот тебе и строка

карма: 22

Ответов: 16884

Рейтинг: 1239

#19: 2010-04-20 17:17:34 ЛС | профиль | цитата

nesco писал(а):

Возьми обычный текст такой длины

Так я обычный текст проверю построчно (по 80 знаков в строке) , а не одной строкой.
И так сделает любой нормальный человек.

карма: 25

Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!

Разработчик

Ответов: 26200

Рейтинг: 2137

#20: 2010-04-20 17:22:28 ЛС | профиль | цитата

Tad писал(а):

И так сделает любой нормальный человек

Есть и не нормальные, которые могут искать во всем тексте. Особенно, если это текстовый стрим.

Tad, завязывай разводить демагогию на пустом месте, тебе что, делать нечего

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

карма: 22

Администрация

Ответов: 15295

Рейтинг: 1519

#21: 2010-04-20 17:51:10 ЛС | профиль | цитата

nesco писал(а):

откуда ясно, что никто ничего менять не будет

этого от туда не ясно. Существующая реализация posex тоже не оптимальна.

карма: 27

https://hiasm.com

Разработчик

Ответов: 26200

Рейтинг: 2137

#22: 2010-04-20 19:07:21 ЛС | профиль | цитата

Dilma писал(а):

Существующая реализация posex тоже не оптимальна

А у тебя уже есть более оптимальный вариант, поделись решением

карма: 22

Ответов: 16884

Рейтинг: 1239

#23: 2010-04-20 19:28:24 ЛС | профиль | цитата

nesco писал(а):

Для себя -- пожалуйста, сколько угодно

так я для себя.
Вместо кроссворда.

А вообще-то "завязывать разводить демагогию" не стоит.
Assasin почему обратил внимание на PosEx ?
Ну какая-то она не такая:
если ищем с начала, то применяем стандартную Pos() паскаля,
а если с какойто позиции, то начинаем перебирать по одной букве (между прочим та же стандартная Pos(), но написанная своими руками - индусский код называется ) и искать - совпало - начинаем сравнивать вторую. И т.д.
И мысль Assasin-а - отбросить лишнее и применить стандартную Pos мне больше нравится.
Попробуй найти : Сколько раз в каком-то тексте встречается какое-то слово.
И придешь именно к алгоритму Assasin, как самому оптимальному.
ИМХО.

карма: 25

Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!

Разработчик

Ответов: 26200

Рейтинг: 2137

#24: 2010-04-20 19:56:11 ЛС | профиль | цитата

Tad писал(а):

И придешь именно к алгоритму Assasin, как самому оптимальному

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

карма: 22

Ответов: 16884

Рейтинг: 1239

#25: 2010-04-20 21:12:08 ЛС | профиль | цитата

nesco писал(а):

Буду пробовать, там посмотрим

nesco писал(а):

тебе что, делать нечего ?

А задачка то интересная

Вот тебе и демагогия.

P.S. Assasin говорил, что язык показывать - некультурно.

карма: 25

Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!

Разработчик

Ответов: 26200

Рейтинг: 2137

#26: 2010-04-21 00:44:30 ЛС | профиль | цитата

Вот что получилось


Add(MainForm,8227255,203,308)
{
 Width=163
 Height=157
 Position=1
}
Add(InlineCode,11935733,385,245)
{
 @Hint=#8:Standart|
 WorkPoints=#5:doPos|
 EventPoints=#5:onPos|
 Code=#15:unit HiAsmUnit;|0:|9:interface|0:|21:uses kol,Share,Debug;|0:|4:type|28: THiAsmClass = class(TDebug)|10:   private|0:|9:   public|21:     onPos:THI_Event;|5:     |50:     procedure doPos(var _Data:TData; Index:word);|5: end;|0:|14:implementation|0:|28:procedure THiAsmClass.doPos;|5:begin|63: _hi_onEvent(onPos,PosEx('123s12','aasftassklddhs123s123s',3));|4:end;|0:|4:end.|
 link(onPos,14267925:doText,[])
 AddHint(34,-36,55,13,@Hint)
}
Add(For,10753889,336,245)
{
 End=100000
 @IsLib=True
 link(onEvent,11935733:doPos,[])
 link(onStop,3504164:doStop,[(380,258)(380,246)(275,246)(275,258)])
}
Add(For,4107591,336,308)
{
 elink(10753889)
 link(onEvent,5889051:doPos,[])
 link(onStop,13453645:doStop,[(380,321)(380,309)(275,309)(275,321)])
}
Add(Button,14588975,203,245)
{
 Left=5
 Top=10
 Caption="test"
 link(onClick,14186092:doEvent1,[])
}
Add(Hub,14186092,252,245)
{
 link(onEvent1,3504164:doStart,[])
 link(onEvent2,13453645:doStart,[(276,258)(276,314)])
}
Add(TimeCounter,3504164,287,245)
{
 link(onStart,10753889:doFor,[])
 link(onStop,3014420:doText,[(326,258)(326,265)])
}
Add(TimeCounter,13453645,287,308)
{
 link(onStart,4107591:doFor,[])
 link(onStop,5385417:doText,[(327,321)(327,307)])
}
Add(Message,11704833,539,280)
{
}
Add(Edit,14267925,434,245)
{
 Left=70
 Top=10
}
Add(Edit,6078964,434,308)
{
 Left=70
 Top=35
}
Add(Edit,3014420,483,259)
{
 Left=70
 Top=70
 Text="time1"
 link(onChange,6782821:doWork1,[(527,265)])
}
Add(Edit,5385417,483,301)
{
 Left=70
 Top=95
 Text="time2"
 link(onChange,6782821:doWork3,[(527,307)])
}
Add(HubEx,6782821,523,280)
{
}
Add(InlineCode,5889051,385,308)
{
 @Hint=#11:Boyer-Moore|
 WorkPoints=#5:doPos|
 EventPoints=#5:onPos|
 Code=#15:unit HiAsmUnit;|0:|9:interface|0:|21:uses kol,Share,Debug;|0:|4:type|28: THiAsmClass = class(TDebug)|10:   private|0:|9:   public|21:     onPos:THI_Event;|5:     |50:     procedure doPos(var _Data:TData; Index:word);|5: end;|0:|14:implementation|0:|73:function PosEx2(const  SubStr, S: string; Offset: Cardinal = 1): Integer;|4:type|36:  TBMHTable = array[0..255] of byte;|3:var|22:  Ps, lp, i : Integer;|17:  BMT: TBMHTable;|5:begin|23:  lp := Length(SubStr);|3:   |33:  FillChar(BMT, SizeOf(BMT), lp);|25:  for i := lp downto 1 do|34:    BMT[ord(SubStr[i])] := lp - i;|0:|24:  Ps := Offset + lp - 1;|0:|14:  Result := 0;|2:  |26:  while Ps <= Length(S) do|31:    if SubStr[lp] <> S[Ps] then|32:      Ps := Ps + BMT[ord(S[Ps])]|8:    else|29:      for i := lp downto 1 do|43:        if SubStr[i] <> S[Ps - lp + i] then|13:        begin|23:          Ps := Ps + 1;|16:          Break;|11:        end|26:        else if i = 1 then|13:        begin|32:          Result := Ps - lp + 1;|15:          Exit;|12:        end;|4:end;|0:|28:procedure THiAsmClass.doPos;|5:begin|64: _hi_onEvent(onPos,PosEx2('123s12','aasftassklddhs123s123s',3));|4:end;|0:|4:end.|
 link(onPos,6078964:doText,[])
 AddHint(51,46,75,13,@Hint)
}

На данный момент это считается наиболее быстрый универсальный алгоритм. Преимущество его начинает замечаться на длинах подстроки > 6 символов

карма: 22

Ответов: 16884

Рейтинг: 1239

#27: 2010-04-21 11:36:27 ЛС | профиль | цитата

Не проходит тест на волшебном слове проверки .

code_17871.txt
------------ Дoбавленo в 10.32:
nesco, посьба - выкладывать коды в свернутом виде (или ХХХХ.txt или ХХХХ.sha)

А ведь обещал !
------------ Дoбавленo в 11.36:
Пока по компактности кода я на первом месте (от скромности я не умру

)


function PosEx(const  SubStr, S: string; Offset: Cardinal =  1): Integer;
var str:string;
begin
   If Offset=0 then Offset := 1; // защита от ......
   Result := Pos(SubStr,CopyEnd(S,Offset));
   If Result>0 then Result := Result + Offset - 1;
end;

Время такое же как и у штатной функции PosEx, длинна результирующих кодов, как я уже писал, АЖ ! на 36 байт

меньше. (тоже критерий

)

карма: 25

Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!

файлы: 1 code_17871.txt [3.3KB] [204]

Разработчик

Ответов: 26200

Рейтинг: 2137

#28: 2010-04-21 12:22:53 ЛС | профиль | цитата

Tad писал(а):

Не проходит тест на волшебном слове проверки

А вообще-то, там небольшая неточность в коде

, которую я потом убрал



Add(MainForm,8227255,273,315)
{
 Width=201
 Height=105
 Position=1
}
Add(InlineCode,11935733,455,252)
{
 @Hint=#8:Standart|
 WorkPoints=#5:doPos|
 EventPoints=#5:onPos|
 Code=#15:unit HiAsmUnit;|0:|9:interface|0:|21:uses kol,Share,Debug;|0:|4:type|28: THiAsmClass = class(TDebug)|10:   private|0:|9:   public|21:     onPos:THI_Event;|5:     |50:     procedure doPos(var _Data:TData; Index:word);|5: end;|0:|14:implementation|0:|28:procedure THiAsmClass.doPos;|5:begin|105: _hi_onEvent(onPos,PosEx('колокол','колоколоколоколоколоколоколоколоколоколоколоколоколоколоколокол',3));|4:end;|0:|4:end.|
 link(onPos,14267925:doText,[])
 AddHint(34,-36,55,13,@Hint)
}
Add(For,10753889,406,252)
{
 @IsLib=True
 link(onEvent,11935733:doPos,[])
 link(onStop,3504164:doStop,[(450,265)(450,253)(345,253)(345,265)])
 link(End,10609727:Var2,[])
}
Add(For,4107591,406,315)
{
 elink(10753889)
 link(onEvent,5889051:doPos,[])
 link(onStop,13453645:doStop,[(450,328)(450,316)(345,316)(345,328)])
 link(End,10609727:Var1,[(419,275)(410,275)(410,236)])
}
Add(Button,14588975,273,252)
{
 Left=5
 Top=35
 Caption="test"
 link(onClick,14186092:doEvent1,[])
}
Add(Hub,14186092,322,252)
{
 link(onEvent1,3504164:doStart,[])
 link(onEvent2,13453645:doStart,[(346,265)(346,321)])
}
Add(TimeCounter,3504164,357,252)
{
 link(onStart,10753889:doFor,[])
 link(onStop,3014420:doText,[(396,265)(396,272)])
}
Add(TimeCounter,13453645,357,315)
{
 link(onStart,4107591:doFor,[])
 link(onStop,5385417:doText,[(397,328)(397,314)])
}
Add(Edit,14267925,504,252)
{
 Left=70
 Top=10
}
Add(Edit,6078964,504,315)
{
 Left=70
 Top=35
}
Add(Edit,3014420,553,266)
{
 Left=130
 Top=10
 Text="time1"
}
Add(Edit,5385417,553,308)
{
 Left=130
 Top=35
 Text="time2"
}
Add(InlineCode,5889051,455,315)
{
 @Hint=#11:Boyer-Moore|
 WorkPoints=#5:doPos|
 EventPoints=#5:onPos|
 Code=#15:unit HiAsmUnit;|0:|9:interface|0:|21:uses kol,Share,Debug;|0:|4:type|28: THiAsmClass = class(TDebug)|10:   private|0:|9:   public|21:     onPos:THI_Event;|5:     |50:     procedure doPos(var _Data:TData; Index:word);|5: end;|0:|14:implementation|0:|72:function PosEx2(const SubStr, S: string; Offset: Cardinal = 1): Integer;|3:var|22:  Ps, lp, i : Integer;|32:  BMT: array[0..255] of integer;|5:begin|23:  lp := Length(SubStr);|3:   |22:  for i := 0 to 255 do|21:    BMT[i] := lp;    |25:  for i := lp downto 1 do|36:    if BMT[ord(SubStr[i])] = lp then|36:      BMT[ord(SubStr[i])] := lp - i;|0:|24:  Ps := Offset + lp - 1;|0:|14:  Result := 0;|2:  |26:  while Ps <= Length(S) do|31:    if SubStr[lp] <> S[Ps] then|32:      Ps := Ps + BMT[ord(S[Ps])]|8:    else|29:      for i := lp downto 1 do|43:        if SubStr[i] <> S[Ps - lp + i] then|13:        begin|23:          Ps := Ps + 1;|16:          Break;|11:        end|26:        else if i = 1 then|13:        begin|32:          Result := Ps - lp + 1;|15:          Exit;|12:        end;|4:end;|0:|28:procedure THiAsmClass.doPos;|5:begin|106: _hi_onEvent(onPos,PosEx2('колокол','колоколоколоколоколоколоколоколоколоколоколоколоколоколоколокол',3));|4:end;|0:|4:end.|
 link(onPos,6078964:doText,[])
 AddHint(51,46,75,13,@Hint)
}
Add(Edit,15250553,413,182)
{
 Left=10
 Top=10
 Text="100000"
}
Add(GetDataEx,10609727,413,231)
{
 link(Data,15250553:Text,[])
}

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

Tad писал(а):

длинна результирующих кодов, как я уже писал, АЖ ! на 36 байт

В сравнении с чем

Tad писал(а):

тоже критерий

Чей критерий

И нафиг твоя компактность кому впала, ты что, проги для микропроцессоров пишишь с ограниченной паматью

И напоследок --

Tad писал(а):

CopyEnd(s,offset)

не хорошее решение, сможешь написать без него

------------ Дoбавленo в 12.22:

Tad писал(а):

посьба - выкладывать коды в свернутом виде (или ХХХХ.txt или ХХХХ.sha)

Не слищком уж и большая портянка, зато, править можно, если ошбки найдутся. А файлы ХХХХ.txt или ХХХХ.sha у меня, в Опере, не читаются нормально

карма: 22

Ответов: 16884

Рейтинг: 1239

#29: 2010-04-21 12:51:46 ЛС | профиль | цитата

nesco писал(а):

не хорошее решение, сможешь написать без него ?

Без него написано - называется PosEx

nesco писал(а):

В сравнении с чем

В сравнении со штатным PosEx

nesco писал(а):

Нет таких слов и не было никогда, об этом везде написано, что это выдуманная проверка на "нечистые" слова.

Ну если "колокол" нечистое слово, то начинаем рассуждать по другому: я ищу не слово, а буквосочетание "колокол" в наборе букв 'колоколоколоколоколоколоколоколоколоколоколоколоколоколоколокол'. Имею я на это право ? Или это происки нечистого ?

nesco писал(а):

И нафиг твоя компактность

Аксиома писал(а):

Краткость сестра таланта

здесь я не о себе и не я это придумал.

nesco писал(а):

ты что, проги для микропроцессоров пишишь с ограниченной паматью ?

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

------------ Дoбавленo в 12.51:

nesco писал(а):

Жаль. Задолбало колесо крутить.

карма: 25

Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!

Разработчик

Ответов: 26200

Рейтинг: 2137

#30: 2010-04-21 12:55:03 ЛС | профиль | цитата

Tad, ты последний выложенный код проверил, или как

Насколько он меньше или больше штатного, да и в сравнении с твоим, тоже.
Как его быстродействие

На твоем супер-пупер слове, результат у меня не в пользу штатного и позиция первого вхождения определяется совершенно правильно.
То, что я предложил ни на какие внешние функции не ссылается, ни на Pos, ни на CopyEnd, он чисто -- сам в себе

карма: 22

Форумы ПрочееФункция PosEx из Share.pas ← Ctrl123 4 5 6...8 9 10 11 12Ctrl →


Сообщение ...
Прикрепленные файлы (файлы не залиты)