Форум: "Прочее";
Текущий архив: 2010.08.27;
Скачать: [xml.tar.bz2];
ВнизЗадачка Найти похожие ветки
← →
Kerk © (2010-03-27 15:22) [0]Все знают игру, в которой дается длинное слово и нужно из его букв составлять другие слова. Как оптимально проверить, действительно ли слово А составлено из букв слова Б? Программно, конечно же.
← →
Юрий Зотов © (2010-03-27 15:28) [1]Если одна и та же буква может быть использована несколько раз, то проверить принадлежность одного множества символов (А) другому (Б).
Если строго однократное использование, то в цикле по слову А проверяем, есть ли такой символ в слове Б и удаляем его из слова Б.
← →
Kerk © (2010-03-27 15:31) [2]
> Юрий Зотов © (27.03.10 15:28) [1]
>
> Если одна и та же буква может быть использована несколько раз
Да, нужно уточнить. Не может.
← →
Игорь Шевченко © (2010-03-27 15:32) [3]Не надо переносить в начинающие
← →
Множества в Делфи (2010-03-27 15:36) [4]www.interface.ru/home.asp?artId=22631
или посмотреть еще в
articles.org.ru
← →
Kerk © (2010-03-27 15:43) [5]А если чуть подумать и решать не в лоб? :)
← →
xayam © (2010-03-27 15:48) [6]Удалено модератором
Примечание: Offtopic
← →
xayam © (2010-03-27 15:50) [7]Удалено модератором
Примечание: Offtopic
← →
И. Павел © (2010-03-27 15:56) [8]Если задача состоит в том, чтобы искать в текущем слове много других слов, то можно представить текущее слово в виде массива, где 1-ый элемент - количество букв "А" в слове, 2-ой - "Б" и т.д. Тогда не нужно будет искать буквы, и это, наверное, ускорит алгоритм. Повторюсь - только если сравниваемых слов много.
← →
KilkennyCat © (2010-03-27 16:07) [9]
> xayam © (27.03.10 15:48) [6]
самый лучший алгоритм архивации изобрел я, и уже давно, ибо в 1-ом байте умещается три буквы, и при этом никакой архивации ;)
← →
Kerk © (2010-03-27 16:09) [10]
> И. Павел © (27.03.10 15:56) [8]
В данный момент я так и делаю. Интересно, есть ли более быстрый способ?
← →
имя (2010-03-27 16:25) [11]Удалено модератором
← →
[true]TRIx © (2010-03-27 16:31) [12]
> действительно ли слово А составлено из букв слова Б? Программно,
> конечно же.
Просто. Например проверить по циклу все буквы слова в другом.
← →
имя (2010-03-27 16:32) [13]Удалено модератором
← →
имя (2010-03-27 16:36) [14]Удалено модератором
← →
EvChul © (2010-03-28 11:55) [15]Упорядочить в словах буквы по алфавиту и сравнить результаты.
← →
MBo © (2010-03-28 11:56) [16]Отсортировать буквы в словах.
слон-> лнос
Далее поиск подпоследовательности
← →
@!!ex © (2010-03-28 11:58) [17]> [10] Kerk © (27.03.10 16:09)
> В данный момент я так и делаю. Интересно, есть ли более
> быстрый способ?
А куда быстрее-то?
← →
PZ (2010-03-28 12:11) [18]> [9] KilkennyCat © (27.03.10 16:07)
Такой алгоритм я использовал еще в 80-х годах на БК-0010. Но это не моё изобретение.
← →
[true]TRIx © (2010-03-28 14:05) [19]Нафиг лишний раз сортировать. Имхо это дольше будет выполняться чем
function test(slovo1,slovo2:string):boolean;
var
i:integer;
begin
result:=true;
for i:=1 to length(slovo2) do
if pos(slovo2[i],slovo1)=0 then
begin
result:=false;
break;
end;
end;
вхождения всех символов полученного слова из слова 1
← →
@!!ex © (2010-03-28 14:42) [20]> [19] [true]TRIx © (28.03.10 14:05)
pos - ВЕСЬМА не быстрая операция.
← →
Kerk © (2010-03-28 15:03) [21]
> [true]TRIx © (28.03.10 14:05) [19]
Более того, твой код попросту не решает поставленную задачу.
← →
@!!ex © (2010-03-28 15:15) [22]> [17] @!!ex © (28.03.10 11:58)
> > [10] Kerk © (27.03.10 16:09)
> > В данный момент я так и делаю. Интересно, есть ли более
>
> > быстрый способ?
>
> А куда быстрее-то?
Кстати. Быстрее будет, если сделать массив не для алфавита, а для всей кодовой страницы.
Тогда не будет преобразований кодов и плгоритм ускорится.
← →
turbouser © (2010-03-28 16:16) [23]
> KilkennyCat © (27.03.10 16:07) [9]
>
>
> > xayam © (27.03.10 15:48) [6]
>
> самый лучший алгоритм архивации изобрел я
Не надо врать.. его я изобрел.. У меня все в один бит жмется %)
← →
KilkennyCat © (2010-03-28 16:46) [24]
> turbouser © (28.03.10 16:16) [23]
не работал ли ты в компании "ТВК" в конце 90-х? Знавал я там одного... у него была гениальная идея, как все сжать до одного бита. С расжатием проблемы только были.
← →
Chirockie (2010-03-28 20:10) [25]
function IsSuperword(ASuperword: AnsiString; const AWord: string): boolean;
var
P: PAnsiChar;
P1: PAnsiChar;
begin
P := PAnsiChar(AWord);
while P^ <> #0 do
begin
P1 := PAnsiChar(ASuperword);
while true do
if P1^ = #0 then
begin
Result := false;
Exit
end
else if P1^ = P^ then
begin
P1^ := #1;
Break
end
else
P1 := P1 + 1;
P := P + 1
end;
Result := true;
end;
← →
Chirockie (2010-03-28 20:21) [26]
function IsSuperword(ASuperword: AnsiString; const AWord: AnsiString): boolean;
← →
Chirockie (2010-03-28 20:24) [27]
+ UniqueString()
:-(
← →
@!!ex © (2010-03-28 21:05) [28]> [25] Chirockie (28.03.10 20:10)
Если я правильно понял логику работы функции, то:
1) IsSuperword("ABBBB","AAAAB") == true
2) Переборов не счесть. В то время, как массив достаточнор один раз заполнить и один раз проверить.
НЕ увидел профита от этого метода.
← →
Chirockie (2010-03-28 21:38) [29]Если я правильно понял логику работы функции, то:
1) IsSuperword("ABBBB","AAAAB") == true
false
2) Переборов не счесть
?
2) ...один раз проверить.
Алгоритм проверки?
← →
антифа-- (2010-03-29 01:35) [30]исходим из предположения, что исходное слово одно, а производных много :)
исходим из того, что слова в аскии. в случае чего, преобразовываем. пользуемся тем, что русские буквы в аски упорядочены по православному алфавиту
заводим массив
SrcLetterEstVSlove array[0..32] of boolean := [false, false,false, .... false,]
where
trueѢ - буква есть в начальном слове
falseѢ - никак не встречается
массив 32 байта утечкой памяти не считаем даже в мобильнике.
заполняем
дальше честно лень набивать. :)
← →
Думкин © (2010-03-29 06:51) [31]> Kerk © (27.03.10 15:22)
Есть еще игра Эрудит. Там писать игру за комп интересно. Можно вводить разные правила, придумывать реализацию уровней сложностей. Писал такую 7 лет назад.
← →
[true]TRIx © (2010-03-29 07:31) [32]KilkennyCat сколько людей я на шум поднял. у меня тоже идея такая была, на бумаге логично поначалу было, а потом не все продумал. Теперь что, весь блокнот исписыл, потихоньку подыскиваю методы.
Kerk
почему же нет, итоговое слово проверяется на соответствие из символов первого слова ли оно состоит.
← →
@!!ex © (2010-03-29 07:33) [33]> [29] Chirockie (28.03.10 21:38)
> 1) IsSuperword("ABBBB","AAAAB") == true
>
> false
А. Точно. Оно же единицей затирается. Ступил.
> [29] Chirockie (28.03.10 21:38)
> 2) Переборов не счесть
>
> ?
На каждую букву слова мы проверяем супрслово.
> [29] Chirockie (28.03.10 21:38)
> Алгоритм проверки?
Заоплняем массив, потом проверяем буквы массива.
← →
Chirockie (2010-03-29 10:03) [34]>@!!ex © (29.03.10 07:33) [33]
>Заоплняем массив, потом проверяем буквы массива.
Интересует конкретно алгоритм проверки, со всеми инициализациями и финализациями, если таковые имеются.
← →
Sha © (2010-03-29 11:35) [35]> Chirockie (29.03.10 10:03) [34]
> Интересует конкретно алгоритм проверки, со всеми инициализациями и финализациями, если таковые имеются.
Это демонстрация идеи.
При желании алгоритм можно значительно оптимизировать.procedure ShaFilterDictionaryByString(var slFiltered: TStringList;
const slDictionary: TStringList;
const s: string);
type
TCharCounters= record
TestNo: integer;
CharCount: byte;
CharFound: byte;
Rest1: byte;
Rest2: byte;
end;
var
Filter: array[char] of TCharCounters;
i, j: integer;
ch: char;
t: string;
label
NextString;
begin;
slFiltered.Clear;
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);
for j:=0 to slDictionary.Count-1 do begin;
t:=slDictionary[j];
for i:=1 to Length(t) do with Filter[t[i]] do begin;
if TestNo<>j then begin;
TestNo:=j;
CharFound:=1;
end
else if CharFound<CharCount then inc(CharCount)
else goto NextString;
end;
slFiltered.Add(t);
NextString:
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
s: string;
slFiltered, slDictionary: TStringList;
begin
slFiltered:=TStringList.Create;
slDictionary:=TStringList.Create;
slDictionary.Text:=Memo1.Text;
s:=Edit1.Text;
ShaFilterDictionaryByString(slFiltered, slDictionary, s);
Memo2.Text:=slFiltered.Text;
end;
← →
Sha © (2010-03-29 11:37) [36]> Sha © (29.03.10 11:35) [35]
Забыл освободить slFiltered и slDictionary
← →
Sha © (2010-03-29 11:43) [37]> Sha © (29.03.10 11:35) [35]
Еще ошибка надо было написать:else if CharFound<CharCount then inc(CharFound)
← →
Chirockie (2010-03-29 12:59) [38]2 Sha
Я спрашивал про алгоритм. Не надо было код писать. Тем более такой...
← →
oldman © (2010-03-29 13:01) [39]
> Как оптимально проверить, действительно ли слово А составлено
> из букв слова Б?
Проверять на этапе формирования слова Б.
Слово А есть суть массив.
Если введенная буква найдена в массиве, удаляем символ из массива, даем вводить следующую букву.
← →
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.64 MB
Время: 0.058 c