Oberon space
General Category => Общий раздел => Тема начата: vlad от Сентябрь 19, 2012, 04:12:19 am
-
Продолжаем строить правильные циклы.
Дан образец, в котором звездочка (*) обозначает любое количество любых символов. Определить соответствует ли строка образцу. Пример:
"12345abc" соответствует "123*abc"
"12345abc*d*" не соответствует "123*abc"
Для определенности - строки это обычные строки (можно заглядывать вперед/назад). Все граничные условия учитываем (пустые строки и т.п.)
Рассуждаем про инварианты, формальные методы и т.д. Ждем info21 с циклом Дейкстры.
-
А где же свой вариант под паролем? По сложившейся традиции надо бы :)
-
Я так понял, задача сводится к многократному поиску подстрок.
Если A, B, C, D, E,... - строки, то "*A*B*C*D*E*" - это значит сначала найти подстроку A, потом в оставшемся хвосте найти подстроку B, потом подстроку C и т. д.
Стало быть псевдокод цикла:
Пока не кончилась исходная строка для всех искомых подстрок
{
найти эту подстроку;
}
Потом еще хвост надо проверить...
-
Только вначале проверить и отбросить те края строки и образца, где у образца не *.
Тогда
Потом еще хвост надо проверить...
не нужно
-
А как понимать * в проверяемой строке?
"12345abc*d*" не соответствует "123*abc"
-
А что тут - задачка на составление КА по рег. выражению. И затем программирование КА. Если составите НКА, то будете программировать с откатом :) Если сделаете ДКА - то уложитесь в обычный цикл.
-
А как понимать * в проверяемой строке?
"12345abc*d*" не соответствует "123*abc"
Вопрос снимаю - потому что без разницы как.
-
А что тут - задачка на составление КА по рег. выражению. И затем программирование КА. Если составите НКА, то будете программировать с откатом :) Если сделаете ДКА - то уложитесь в обычный цикл.
Если сделаете НКА, то потом сведете к ДКА и все равно будет обычный цикл :-)
-
А где же свой вариант под паролем? По сложившейся традиции надо бы :)
Чуть позже будет.
-
FUNCTION Match (CONST Str, Pattern: STRING): BOOLEAN;
CONST
WILLCARD = '*';
TYPE
TState =
(
STATE_STRICT_COMPARE, // [L]
STATE_FIRST_LETTER_SEARCH, // *[L]
STATE_MATCH_SUBSTR_TAIL, // *L[...]*
STATE_EXIT
);
VAR
State: TState;
StrLen: INTEGER;
PatternLen: INTEGER;
StrBasePos: INTEGER;
PatternBasePos: INTEGER;
s: INTEGER; // Pos in Pattern
p: INTEGER; // Pos in Str
PROCEDURE SkipWillcards;
BEGIN
WHILE (p <= PatternLen) AND (Pattern[p] = WILLCARD) DO BEGIN
INC(p);
END; // .WHILE
END; // .PROCEDURE SkipWillcards
PROCEDURE SkipMatchingSubstr;
BEGIN
WHILE
(p <= PatternLen) AND
(s <= StrLen) AND
(Pattern[p] <> WILLCARD) AND
(Str[s] = Pattern[p])
DO BEGIN
INC(p);
INC(s);
END; // .WHILE
END; // .PROCEDURE SkipMatchingSubstr
PROCEDURE Fail;
BEGIN
State := STATE_EXIT;
RESULT := FALSE;
END; // .PROCEDURE Fail
PROCEDURE Success;
BEGIN
State := STATE_EXIT;
RESULT := TRUE;
END; // .PROCEDURE Success
BEGIN
StrLen := LENGTH(Str);
PatternLen := LENGTH(Pattern);
StrBasePos := 1;
PatternBasePos := 1;
s := 1;
p := 1;
State := STATE_STRICT_COMPARE;
RESULT := FALSE;
WHILE State <> STATE_EXIT DO BEGIN
CASE State OF
STATE_STRICT_COMPARE:
BEGIN
SkipMatchingSubstr;
IF (s > StrLen) AND (p > PatternLen) THEN BEGIN
Success;
END // .IF
ELSE IF (s > StrLen) OR (p > PatternLen) OR (Pattern[p] <> WILLCARD) THEN BEGIN
Fail;
END // .ELSEIF
ELSE BEGIN
SkipWillcards;
State := STATE_FIRST_LETTER_SEARCH;
END; // .ELSE
END; // .CASE STATE_STRICT_COMPARE
STATE_FIRST_LETTER_SEARCH:
BEGIN
WHILE (s < StrLen) AND (Str[s] <> Pattern[p]) DO BEGIN
INC(s);
END; // .WHILE
IF s > StrLen THEN BEGIN
Fail;
END // .IF
ELSE BEGIN
StrBasePos := s;
PatternBasePos := p;
INC(p);
INC(s);
State := STATE_MATCH_SUBSTR_TAIL;
END; // .ELSE
END; // .CASE STATE_FIRST_LETTER_SEARCH
STATE_MATCH_SUBSTR_TAIL:
BEGIN
SkipMatchingSubstr;
IF (s > StrLen) AND (p > PatternLen) THEN BEGIN
Success;
END // .IF
ELSE IF (s > StrLen) OR (p > PatternLen) THEN BEGIN
Fail;
END // .ELSEIF
ELSE IF Pattern[p] <> WILLCARD THEN BEGIN
p := PatternBasePos + 1;
s := StrBasePos + 1;
State := STATE_FIRST_LETTER_SEARCH;
END // .ELSEIF
ELSE BEGIN
SkipWillcards;
State := STATE_FIRST_LETTER_SEARCH;
END; // .ELSE
END; // .CASE STATE_MATCH_SUBSTR_TAIL
END; // .SWITCH State
END; // .WHILE
(* If "..." matches, "...*" matches too *)
IF NOT RESULT THEN BEGIN
SkipWillcards;
RESULT := (p > PatternLen) AND (s > StrLen);
END; // .IF
END; // .FUNCTION Match
ShowMessage(IntToStr(ORD(Match('', '')))); // 1
ShowMessage(IntToStr(ORD(Match('a', '')))); // 0
ShowMessage(IntToStr(ORD(Match('', 'a')))); // 0
ShowMessage(IntToStr(ORD(Match('', '*')))); // 1
ShowMessage(IntToStr(ORD(Match('aaa', 'bbb')))); // 0
ShowMessage(IntToStr(ORD(Match('12345abc', '123*abc')))); // 1
ShowMessage(IntToStr(ORD(Match('12345abc*d*', '123*abc')))); // 0
ShowMessage(IntToStr(ORD(Match('abceabcdef', 'abcd*f*')))); // 0
ShowMessage(IntToStr(ORD(Match('abceabcdef', '*abcd*f*')))); // 1
ShowMessage(IntToStr(ORD(Match('abceabcdef', '*ab*d*f*')))); // 1
Таблица переходов:
strict_compare:
end(Str) & end(Pattern) => success
end(Str) or end(Pattern) => fail
mismatch => fail
match until willcard => first_letter_search
first_letter_search:
not found => fail
found => match_substr_tail
match_substr_tail:
end(Str) & end(Pattern) => success
end(Str) or end(Pattern) => fail
match until willcard => first_letter_search
mismatch => match_substr_tail
exit:
only willcards left to match => success
Не судите строго.
-
А где же свой вариант под паролем? По сложившейся традиции надо бы :)
Мой вариант. Редуцированный реальный код (на самом деле там сложнее образец):
public class star_expression
{
public static bool match( string s, string pattern )
{
var st = new state{ s = s, pattern = pattern };
return match( ref st );
}
private struct state
{
public string s;
public string pattern;
public int string_pos;
public int pattern_pos;
}
private static bool match( ref state st )
{
while ( st.pattern_pos < st.pattern.Length )
{
var ch = st.pattern[st.pattern_pos];
if ( ch == '*' )
{
var try_state = new state{ s = st.s, pattern = st.pattern, string_pos = st.string_pos, pattern_pos = st.pattern_pos + 1 };
if ( match( ref try_state ) )
return true;
if ( st.string_pos == st.s.Length )
return false;
++st.string_pos;
}
else if ( st.string_pos < st.s.Length && ch == st.s[st.string_pos] )
{
++st.pattern_pos;
++st.string_pos;
}
else
return false;
}
return st.string_pos == st.s.Length;
}
}
Набор тестовых данных:
Assert.That( star_expression.match( "str123", "str123*" ), Is.True );
Assert.That( star_expression.match( "str123", "str*" ), Is.True );
Assert.That( star_expression.match( "str123", "*str123" ), Is.True );
Assert.That( star_expression.match( "str123", "*123" ), Is.True );
Assert.That( star_expression.match( "str123", "*str123*" ), Is.True );
Assert.That( star_expression.match( "str123", "*r1*" ), Is.True );
Assert.That( star_expression.match( "str123", "*s*r1*3" ), Is.True );
Assert.That( star_expression.match( "str123", "*s*r1*34" ), Is.False );
Assert.That( star_expression.match( "str123", "*" ), Is.True );
Assert.That( star_expression.match( "str123", "**" ), Is.True );
Assert.That( star_expression.match( "str123", "***" ), Is.True );
Assert.That( star_expression.match( "", "" ), Is.True );
Assert.That( star_expression.match( "str123", "" ), Is.False );
Assert.That( star_expression.match( "", "*" ), Is.True );
-
А что тут - задачка на составление КА по рег. выражению. И затем программирование КА.
Как бы да. Я всегда начинаю такие задачки с автомата. Но в процессе явные состояния со свитчом почему-то всегда редуцируются до вызова отдельных функций (см. мой пример).
Если составите НКА, то будете программировать с откатом :) Если сделаете ДКА - то уложитесь в обычный цикл.
Боюсь показаться серым, но не могу придумать как тут обойтись без откатов (рекурсии)?
P.S. Да, была идея сначала странслировать все это в обычное регулярное выражение и там стандартное библиотченое решение использовать. Но образец немного сложнее, чем я описал. Поэтому решил врукопашную.
-
Не судите строго.
Не увидел в твоем коде откатов. Будет ли он работать для таких данных:
abcdefgabcefg -> abc*efg
abcdefgabcefg -> abc*efg*efg
-
Зачем в этой задаче откаты?
В общем виде всё сводится к:
1. Сначала проверить совпадение подстрок в фиксированных местах, а это только может быть на концах строки.
2.Затем проверить наличие остальных подстрок образца по первому же совпадения в оставшейся части проверяемой строки.
-
Зачем в этой задаче откаты?
В общем виде всё сводится к:
Не очень понял. Код в студию ;) Вариант Berserker'а не осилил. Но попробую еще раз, если у него работают предложенные варианты.
-
Не очень понял. Код в студию ;)
Код на MUMPSе приводить смысла нет.
Реально у меня в рабочем коде ввиду того, что в языке (MUMPS) есть операторы сравнения с шаблоном, образец трансформируется в шаблон, а затем одной командой проверяется. Но это к слову. Другой код с циклом сравнения написать не проблема. Поясню свой предыдущий пост на примере, кстати С.Губанов в принципе про такое же и писал но кратко, без нюансов.
abcdefgabcefg -> abc*efg*efg
1.Образец начинается не со '*' - надо проверить с фикс. позиции (с начала строки) наличие подстроки "abc"
На конце образца не '*' - надо проверить наличие "efg" на конце строки
Остаётся проверить "defgabc" ->*efg*
2.Ищем первое же вхождение каждой подстроки из образца в проверяемой строке, пока образец или проверяемая строка не закончится.
Если на первом этапе образец закончился а проверяемая строка нет, то общий итог - строка не соответствует образцу.
Примерно так всё.
-
Полный текст на C#. Не причесывал для Assert'ов.
class Program {
static string s, p;
//i - тек. позиция в строке, j - тек. позиция в образце
static bool Test(int i, int j) {
bool res = false;
if (s.Length == i && p.Length == j) {//одновременный конец строк
res = true;
} else if (s.Length != i && p.Length == j) {//строка не пустая, образец кончился
res = false;
} else if (p.Length != j && p[j] == '*') {
j++;
while (i != s.Length+1 && !Test(i, j)) {
i++;
}
res = i != s.Length+1;
} else if (s.Length != i && p.Length != j) {
res = s[i] == p[j] && Test(i + 1, j + 1);
}
return res;
}
static void Main(string[] args) {
s = "str123";
p = "*s*r1*34";
bool res = Test(0, 0);
}
}
-
Зачем в этой задаче откаты?
В общем виде всё сводится к:
1. Сначала проверить совпадение подстрок в фиксированных местах, а это только может быть на концах строки.
2.Затем проверить наличие остальных подстрок образца по первому же совпадения в оставшейся части проверяемой строки.
Refal-style ))
-
Полный текст на C#.
а на таких данных как?
строка "str1212" образец "s*12"
-
true
-
Ещё разок.
строка "str1212" образец "s*1t*2"
-
false
-
Вложил exe-шник. Но потребуется .NET 2.0.
-
Исправил. Пропустил случай "конец шаблона, не конец строки = откат".
FUNCTION Match (CONST Str, Pattern: STRING): BOOLEAN;
CONST
WILLCARD = '*';
TYPE
TState =
(
STATE_STRICT_COMPARE, // [L]
STATE_FIRST_LETTER_SEARCH, // *[L]
STATE_MATCH_SUBSTR_TAIL, // *L[...]*
STATE_EXIT
);
VAR
State: TState;
StrLen: INTEGER;
PatternLen: INTEGER;
StrBasePos: INTEGER;
PatternBasePos: INTEGER;
s: INTEGER; // Pos in Pattern
p: INTEGER; // Pos in Str
PROCEDURE SkipWillcards;
BEGIN
WHILE (p <= PatternLen) AND (Pattern[p] = WILLCARD) DO BEGIN
INC(p);
END; // .WHILE
END; // .PROCEDURE SkipWillcards
PROCEDURE SkipMatchingSubstr;
BEGIN
WHILE
(p <= PatternLen) AND
(s <= StrLen) AND
(Pattern[p] <> WILLCARD) AND
(Str[s] = Pattern[p])
DO BEGIN
INC(p);
INC(s);
END; // .WHILE
END; // .PROCEDURE SkipMatchingSubstr
PROCEDURE Fail;
BEGIN
State := STATE_EXIT;
RESULT := FALSE;
END; // .PROCEDURE Fail
PROCEDURE Success;
BEGIN
State := STATE_EXIT;
RESULT := TRUE;
END; // .PROCEDURE Success
BEGIN
StrLen := LENGTH(Str);
PatternLen := LENGTH(Pattern);
StrBasePos := 1;
PatternBasePos := 1;
s := 1;
p := 1;
State := STATE_STRICT_COMPARE;
RESULT := FALSE;
WHILE State <> STATE_EXIT DO BEGIN
CASE State OF
STATE_STRICT_COMPARE:
BEGIN
SkipMatchingSubstr;
IF (s > StrLen) AND (p > PatternLen) THEN BEGIN
Success;
END // .IF
ELSE IF (s > StrLen) OR (p > PatternLen) OR (Pattern[p] <> WILLCARD) THEN BEGIN
Fail;
END // .ELSEIF
ELSE BEGIN
SkipWillcards;
State := STATE_FIRST_LETTER_SEARCH;
END; // .ELSE
END; // .CASE STATE_STRICT_COMPARE
STATE_FIRST_LETTER_SEARCH:
BEGIN
WHILE (s < StrLen) AND (Str[s] <> Pattern[p]) DO BEGIN
INC(s);
END; // .WHILE
IF s > StrLen THEN BEGIN
Fail;
END // .IF
ELSE BEGIN
StrBasePos := s;
PatternBasePos := p;
INC(p);
INC(s);
State := STATE_MATCH_SUBSTR_TAIL;
END; // .ELSE
END; // .CASE STATE_FIRST_LETTER_SEARCH
STATE_MATCH_SUBSTR_TAIL:
BEGIN
SkipMatchingSubstr;
IF (s > StrLen) AND (p > PatternLen) THEN BEGIN
Success;
END // .IF
ELSE IF s > StrLen THEN BEGIN
Fail;
END // .ELSEIF
ELSE IF (p > PatternLen) OR (Pattern[p] <> WILLCARD) THEN BEGIN
p := PatternBasePos;
s := StrBasePos + 1;
State := STATE_FIRST_LETTER_SEARCH;
END // .ELSEIF
ELSE BEGIN
SkipWillcards;
State := STATE_FIRST_LETTER_SEARCH;
END; // .ELSE
END; // .CASE STATE_MATCH_SUBSTR_TAIL
END; // .SWITCH State
END; // .WHILE
(* If "..." matches, "...*" matches too *)
IF NOT RESULT THEN BEGIN
SkipWillcards;
RESULT := (p > PatternLen) AND (s > StrLen);
END; // .IF
END; // .FUNCTION Match
ShowMessage(IntToStr(ORD(Match('', '')))); // 1
ShowMessage(IntToStr(ORD(Match('a', '')))); // 0
ShowMessage(IntToStr(ORD(Match('', 'a')))); // 0
ShowMessage(IntToStr(ORD(Match('', '*')))); // 1
ShowMessage(IntToStr(ORD(Match('aaa', 'bbb')))); // 0
ShowMessage(IntToStr(ORD(Match('12345abc', '123*abc')))); // 1
ShowMessage(IntToStr(ORD(Match('12345abc*d*', '123*abc')))); // 0
ShowMessage(IntToStr(ORD(Match('abceabcdef', 'abcd*f*')))); // 0
ShowMessage(IntToStr(ORD(Match('abceabcdef', '*abcd*f*')))); // 1
ShowMessage(IntToStr(ORD(Match('abceabcdef', '*ab*d*f*')))); // 1
ShowMessage(IntToStr(ORD(Match('abcdefgabcefg', 'abc*efg')))); // 1
ShowMessage(IntToStr(ORD(Match('abceabcdef', 'abc*efg*efg')))); // 0
strict_compare:
end(Str) & end(Pattern) => success
end(Str) or end(Pattern) => fail
mismatch => fail
match until willcard => first_letter_search
first_letter_search:
not found => fail
found => match_substr_tail
match_substr_tail:
end(Str) & end(Pattern) => success
end(Str) => fail
end(Pattern) or mismatch => first_letter_search [fallback]
else => first_letter_search [continue]
exit:
only willcards left to match => success
Особенности: не использует динамическую память, не использует рекурсию.
Откат происходит в следующем месте:
STATE_MATCH_SUBSTR_TAIL:
BEGIN
SkipMatchingSubstr;
...
// Шаблон закончился или строка не совпала с той, которую искали
ELSE IF (p > PatternLen) OR (Pattern[p] <> WILLCARD) THEN BEGIN
// Откат позиций к запомненным
p := PatternBasePos;
s := StrBasePos + 1;
State := STATE_FIRST_LETTER_SEARCH;
END // .ELSEIF
ELSE BEGIN
SkipWillcards;
State := STATE_FIRST_LETTER_SEARCH;
END; // .ELSE
END; // .CASE STATE_MATCH_SUBSTR_TAIL
-
Врёт.
String: 878765
Pattern: 87*8*7*6
Result: TRUE
-
2.Ищем первое же вхождение каждой подстроки из образца в проверяемой строке, пока образец или проверяемая строка не закончится.
Кажется понял. В моем варианте "поиск подстроки" это и есть "откат". Т.е. ищем подстроку с текущей позиции, откатываемся, инкрементируем позицию, опять ищем.
-
2.Ищем первое же вхождение каждой подстроки из образца в проверяемой строке, пока образец или проверяемая строка не закончится.
Кажется понял. В моем варианте "поиск подстроки" это и есть "откат". Т.е. ищем подстроку с текущей позиции, откатываемся, инкрементируем позицию, опять ищем.
Но пока еще не осознал куда деть рекурсию, максимальная глубина которой равна колчичеству подстрок (звездочек).
-
В моем варианте "поиск подстроки" это и есть "откат".
И я понял о каких "откатах" народ говорит. Тяжело бывает переключится на чужие проблемы с языка, в котором есть и сравнение строк и поиск подстроки и пр. удобства и к которым настолько привык :)
-
В моем варианте "поиск подстроки" это и есть "откат".
И я понял о каких "откатах" народ говорит. Тяжело бывает переключится на чужие проблемы с языка, в котором есть и сравнение строк и поиск подстроки и пр. удобства и к которым настолько привык :)
Это ты про perl (где регэкспы встроенные)? ;-)
-
Блин, строка не с нуля индексируется:
WHILE (s < StrLen) AND (Str[s] <> Pattern[p]) DO BEGIN
=>
WHILE (s <= StrLen) AND (Str[s] <> Pattern[p]) DO BEGIN
Теперь пример Петра Алмазова проходит. Рекурсии всё равно нет.
-
а чем рекурсия не угодила?
-
Но пока еще не осознал куда деть рекурсию, максимальная глубина которой равна колчичеству подстрок (звездочек).
Да, можно без рекурсии, достаточно помнить позицию последней звезды (как у Berserker'а). Потому что очередная найденная звезда "эквивалентна" предыдущей с точки зрения нахождения соответствия.
-
а чем рекурсия не угодила?
В данном случае - все хорошо (ну не будет мильена звездочек в образце). Собственно я у себя и оставил как есть, потому что с рекурсией код проще, а сложность O - одинаковая. Просто хотелось понять как можно без нее. А еще без рекурсии можно полноценный злобнейший цикл Дейкстры наколбасить с трехэтажными условиями в ифах ;)
-
2 vlad:
Если тебе нужна рекурсия, значит, ты построил недетерминированный КА (в котором из некоторого состояния могут быть два и более перехода, помеченные одним символом). Его можно формально преобразовать в детерминированный, в котором очередной символ однозначно определяет переход.
-
Надо бы ещё поддержку "?" добавить в качестве 1-го случайного символа. Кстати, FindFirstFile "по-своему" сопоставляет с шаблоном, так что:
"*.pak" вернёт и "abba.pak.abba".
-
а чем рекурсия не угодила?
Поправьте меня, если я ошибаюсь, но разве у Петра не на каждый символ вызов процедуры? Очень лаконичный и надёжный вариант, но переполнение стопки не дремлет.
На пользовательских данных плохой запрос повесит функцию (сложность N^2 поиска строки в лоб) на неопределённое время, а в случае рекурсии убьёт процесс.
Найти a[99]
Дано a[98]b
В скобках - число повторений.
Проходы: 99, 98, 97...
-
Надо бы ещё поддержку "?" добавить в качестве 1-го случайного символа.
Вообще в оригинале надо сделать вот это: http://msdn.microsoft.com/en-us/library/ms179859.aspx
-
В принципе, удобная конструкция. Нужно будет попробовать в полном объёме сделать.
-
но переполнение стопки не дремлет.
На пользовательских данных плохой запрос повесит функцию (сложность N^2 поиска строки в лоб) на неопределённое время, а в случае рекурсии убьёт процесс.
Найти a[99]
Дано a[98]b
В скобках - число повторений.
Проходы: 99, 98, 97...
В той программе у P.A. при поиске последней непустой подстроки образца в проверяемой строке неявным образом учитывается "наличие" как бы символа "конца строки" и потому окончательное успешное сравнение естественно может произойти только когда правые границы совпадут, но по алгоритму процесс сравнения "тупо" повторяется двигаясь шаг за шагом вправо.
122222222222 и 1*2
Вот двойка и будет ползти по строке начиная с 1 позиции пока не упрётся в правую границу, и только тогда окончательный итог будет TRUE.
Вот почему лучше сначала проверить на соответствие непустые крайние подстроки образца, а серединку оставить на десерт. :)
-
в котором очередной символ однозначно определяет переход.
Дело не в КА. Потому что главный вопрос при очередном шаге не "куда?", а "когда?". И правильный ответ на него "в будущем". Дело в том, что есть не меньше двух подходов к регулярным выражениям. Например, сопоставление 123412341234
1.*1234одним методом вернёт FALSE (и это правильно), а другая вернёт TRUE (и это тоже правильно).
Но только в сообщении 36 Vlad дал необходимый минимум исходных данных, чтобы начать решать задачу, поэтому вариант только на опору КА, без запоминания состояния, не подойдёт.
-
Полный текст на C#. Не причесывал для Assert'ов.
Голосую за твой вариант как наиболее красивый и наглядный :)
-
Поправьте меня, если я ошибаюсь, но разве у Петра не на каждый символ вызов процедуры? Очень лаконичный и надёжный вариант, но переполнение стопки не дремлет.
Там типичная хвостовая рекурсия (которая последняя) - компилятор имеет все шансы соптимизить ее в цикл. Но не факт, конечно. А та, которая в цикле - зависит от количества звездочек, а не всех символов (как и в моем варианте).
-
Если без рекурсии, то как-то так:
MODULE Match;
IMPORT Strings;
PROCEDURE MatchIt( CONST text, pattern : ARRAY OF CHAR;
posT, posP : LONGINT;
lenT, lenP : LONGINT ): BOOLEAN;
VAR chT, chP: CHAR;
PROCEDURE NoMoreCharInPattern(): BOOLEAN;
BEGIN
WHILE ( pattern[ posP ] = '*' ) & ( posP # lenP ) DO
INC( posP );
END;
RETURN posP = lenP;
END NoMoreCharInPattern;
PROCEDURE FindCharInText( ch: CHAR ): BOOLEAN;
BEGIN
WHILE posT # lenT DO
IF text[ posT ] = ch THEN RETURN TRUE END;
INC ( posT );
END;
RETURN FALSE;
END FindCharInText;
BEGIN
LOOP
IF posT = lenT THEN
RETURN NoMoreCharInPattern();
ELSIF posP = lenP THEN
RETURN FALSE;
ELSE
chT := text[ posT ];
chP := pattern[ posP ];
IF chP = '*' THEN
INC( posP );
IF NoMoreCharInPattern() THEN
RETURN TRUE;
ELSIF FindCharInText( pattern[ posP ] ) THEN
INC( posT );
INC( posP );
ELSE
RETURN FALSE;
END;
ELSIF ( chP = chT ) OR ( chP = '?' ) THEN
INC( posT );
INC( posP );
ELSE
RETURN FALSE;
END;
END;
END;
END MatchIt;
PROCEDURE DoMatch*( CONST text, pattern: ARRAY OF CHAR ): BOOLEAN;
BEGIN
RETURN MatchIt( text, pattern, 0, 0, Strings.Length( text ), Strings.Length( pattern ));
END DoMatch;
END Match.
'?' вроде тоже должна работать, при условии, что стоит не перед звездой, но кто ее перед звездой ставит...
-
'?' вроде тоже должна работать, при условии, что стоит не перед звездой, но кто ее перед звездой ставит...
Вернее не рядом со звездой
-
Убеждаюсь лишний раз, что RETURN/BREAK/EXIT - зло.
Если пока оставить вопрос с комбинациями * и ?, у меня серьёзные подозрения, что
abdabc *abc не пройдёт. Нет откатов. По шагам:
* - найди "a" => ok
b = b? да
d = c? нет, конец игры.
Или я ошибаюсь?
-
2Valeriy Solovey:
Если мы берём второй вариант (что допускаем строку 1.12341234), то будет такой КА, как на прилагаемом рисунке.
Если хотим первый вариант, то убираем переход q6->q2.
Вообще, достаточно одной семантики - жадной (как первый КА). Нежадная даётся расстановкой скобок: 1.(*123)4
В теории языков нет понятия "жадная/нежадная интерпретация регулярного выражения". Это уже самоделкинские придумки в реализациях.
Уверен в сказанном выше не на 100%, готов к возражениям :)
-
У меня в примере сначала шла строка, а затем регулярное выражение, которому она должна соответствовать. Точка в моём регулярном выражении - это обозначение любого символа, а звёздочка - произвольное кол-во повторений символа, стоящего перед ней. Когда я писал пример, то думал, что это будет понятно, но глядя теперь на граф, не уверен, что ясно донёс свою мысль.
Лично я предпочитаю такой вариант, где не нужны возвраты. Подавляющее большинство реальных задач такой вариант покрывает. Правда, конечное регулярное выражение временами бывает слишком громоздким. Но зато сложнее написать такое выражение, которое вместо секунд будет выполняться неделями. Или его вообще невозможно написать таким тормознутым.
Что же касается жадности, то самоделкины здесь ни при чём. Этот термин - результат анализа разных подходов к регулярным выражениям. Его смысл - в реакции движка герулярных выражений при ситуации, требующей выбора. Например, у нас есть выражение .*4 Движок выполняет разбор строки и доходит до символа "4". Появляется необходимость выбора: или этот символ покрывается частью выражения, представленного точкой, или частью выражения, представленного непосредственно символом 4. Та часть выражения, которая захватит символ, более жадная. То есть, жадность - это аналог приоритета операций в арифметических выражениях.
-
abdabc *abc не пройдёт.
Да, недопонял задачу
-
Исправленный вариант
MODULE Match;
IMPORT Strings;
PROCEDURE MatchIt( CONST text, pattern : ARRAY OF CHAR;
posT, posP : LONGINT;
lenT, lenP : LONGINT ): BOOLEAN;
VAR
chT, chP: CHAR;
iT, iP : LONGINT;
PROCEDURE NoMoreCharInPattern(): BOOLEAN;
BEGIN
WHILE ( pattern[ posP ] = '*' ) & ( posP < lenP ) DO
INC( posP );
END;
RETURN posP = lenP;
END NoMoreCharInPattern;
PROCEDURE FindCharInText( ch: CHAR; pos: LONGINT ): BOOLEAN;
BEGIN
WHILE pos < lenT DO
IF text[ pos ] = ch THEN posT:= pos; RETURN TRUE END;
INC ( pos );
END;
RETURN FALSE;
END FindCharInText;
BEGIN
iT := lenT;
LOOP
IF posT = lenT THEN
RETURN NoMoreCharInPattern();
ELSIF posP = lenP THEN
RETURN FALSE;
ELSE
chT := text[ posT ];
chP := pattern[ posP ];
IF chP = '*' THEN
INC( posP );
IF NoMoreCharInPattern() THEN
RETURN TRUE;
ELSIF FindCharInText( pattern[ posP ], posT ) THEN
iP := posP;
INC( posP );
INC( posT );
iT := posT;
ELSE
RETURN FALSE;
END;
ELSIF ( chP = chT ) OR ( chP = '?' ) THEN
INC( posP );
INC( posT );
ELSE
IF ( iT < lenT ) & FindCharInText( pattern[ iP ] , iT ) THEN
posP := iP;
INC( posP );
INC( posT );
iT := posT;
ELSE
RETURN FALSE;
END;
END;
END;
END;
END MatchIt;
PROCEDURE DoMatch*( CONST text, pattern: ARRAY OF CHAR ): BOOLEAN;
BEGIN
RETURN MatchIt( text, pattern, 0, 0, Strings.Length( text ), Strings.Length( pattern ));
END DoMatch;
END Match.
-
Всё же более вразумительно нужно задачи формулировать ... хотя да, и мне нужно все читать, а не по диагонали.
MODULE Match;
IMPORT Strings;
PROCEDURE MatchIt( CONST text, pattern : ARRAY OF CHAR;
posT, posP : LONGINT;
lenT, lenP : LONGINT ): BOOLEAN;
VAR
chT, chP: CHAR;
iT, iP : LONGINT;
PROCEDURE NoMoreCharInPattern(): BOOLEAN;
BEGIN
WHILE ( pattern[ posP ] = '*' ) & ( posP < lenP ) DO
INC( posP );
END;
RETURN posP = lenP;
END NoMoreCharInPattern;
PROCEDURE FindCharInText( ch: CHAR; pos: LONGINT ): BOOLEAN;
BEGIN
WHILE pos < lenT DO
IF text[ pos ] = ch THEN posT:= pos; RETURN TRUE END;
INC ( pos );
END;
RETURN FALSE;
END FindCharInText;
PROCEDURE Retry;
BEGIN
posP := iP;
INC( posP );
INC( posT );
iT := posT;
END Retry;
BEGIN
iT := lenT;
iP := lenP;
LOOP
IF posT = lenT THEN
RETURN NoMoreCharInPattern();
ELSIF posP = lenP THEN
IF ( iP < lenP ) & FindCharInText( pattern[iP] , iT ) THEN
Retry
ELSE
RETURN FALSE;
END;
ELSE
chT := text[ posT ];
chP := pattern[ posP ];
IF chP = '*' THEN
INC( posP );
IF NoMoreCharInPattern() THEN
RETURN TRUE;
ELSIF FindCharInText( pattern[ posP ], posT ) THEN
iP := posP;
INC( posP );
INC( posT );
iT := posT;
ELSE
RETURN FALSE;
END;
ELSIF ( chP = chT ) OR ( chP = '?' ) THEN
INC( posP );
INC( posT );
ELSE
IF ( iP < lenP ) & FindCharInText( pattern[iP] , iT ) THEN
Retry;
ELSE
RETURN FALSE;
END;
END;
END;
END;
END MatchIt;
PROCEDURE DoMatch*( CONST text, pattern: ARRAY OF CHAR ): BOOLEAN;
BEGIN
RETURN MatchIt( text, pattern, 0, 0, Strings.Length( text ), Strings.Length( pattern ));
END DoMatch;
END Match.
Вроде как на всех тестовых данных прошло
-
Ну так и де у вас всех доказательства корректности, инварианты и всё такое? )))
-
Лично я предпочитаю такой вариант, где не нужны возвраты. Подавляющее большинство реальных задач такой вариант покрывает. Правда, конечное регулярное выражение временами бывает слишком громоздким. Но зато сложнее написать такое выражение, которое вместо секунд будет выполняться неделями. Или его вообще невозможно написать таким тормознутым.
Что же касается жадности, то самоделкины здесь ни при чём. Этот термин - результат анализа разных подходов к регулярным выражениям. Его смысл - в реакции движка герулярных выражений при ситуации, требующей
Понял про точку, ну так граф от этого не сильно меняется - просто выкидывается одно состояние и переход. Разница между жадностью и нежадностью, опять же, в наличии обратного перехода из последнего состояния. И имея жадную семантику, я всегда представлю нежадную: (.*)4.
А возвраты таки получаются, если сгенерирован недетерминированный автомат (а "обычный" алгоритм генерации КА из РВ такой и будет давать). Ну так кто мешает преобразовать его в детерминированный и избавиться от возвратов?
Пример с (.*)4, кстати, не даст НКА, - при соединении автомата для части в скобках и автомата для окончания выражения всё соединится детерминированно.
-
Илья, интересно было бы Ваше решение.
Я обобщил задачу до заявленной функциональности магических символов (WILDCARDS) в API OS Windows. В частности:
"*" - нуль или более любых символов
"?" - один любой символ
Требуется проверить, соответствует (не содержит!) ли строка шаблону.
После очередного перерождения и нахождения пары ошибок, мой вариант:
FUNCTION Match (CONST Str, Pattern: STRING): BOOLEAN;
CONST
ONE_SYM_WILDCARD = '?';
ANY_SYMS_WILDCARD = '*';
WILDCARDS = [ONE_SYM_WILDCARD, ANY_SYMS_WILDCARD];
TYPE
TState =
(
STATE_STRICT_COMPARE, // [abc]*?*?**cde?x*
STATE_SKIP_WILDCARDS, // abc[*?*?**]cde?x*
STATE_FIRST_LETTER_SEARCH, // abc*?*?**[c]de?x*
STATE_MATCH_SUBSTR_TAIL, // abc*?*?**c[de?x]*
STATE_EXIT
);
(*
Non-greedy algorithm tries to treat ANY_SYMS_WILLCARD as the shortest possible string.
Token is a substring between Base position and ANY_SYMS_WILLCARD or end of string in the template
and corresponding matching substring in the string.
Match "abcecd78e" against "a*cd*e": (Token is wrapped in parenthesis)
(abcecd78e)
(a*cd*e)
=> STRICT_COMPARE until * (success)
(a )(bcecd78e)
(a* )(cd*e)
=> FIRST_LETTER_SEARCH "c" (success)
(ab )(cecd78e)
(a* )(cd*e)
=> MATCH_SUBSTR_TAIL "d" (fail)
(abc)(ecd78e)
(a* )(cd*e)
=> FIND_FIRST_LETTER "c" (success)
(abce)(cd78e)
(a* )(cd*e)
=> MATCH_SUBSTR_TAIL "d" (success)
(abce)(cd )(78e)
(a* )(cd* )(e)
=> FIND_FIRST_LETTER "e" (success)
(abce)(cd78)(e)
(a* )(cd* )(e)
=> EXIT
*)
(*
Contracts for states:
STATE_STRICT_COMPARE:
- Entry state, not-reenterable
- Matches character-to-character, including ONE_SYM_WILLCARD
- Exits on mismatch
- => STATE_SKIP_WILDCARDS
STATE_SKIP_WILDCARDS:
- Skips sequence of WILDCARDS
- Increases position in the string for each ONE_SYM_WILDCARD
- Exits on end of pattern
- Initializes character "c" to current pattern character
- => STATE_FIRST_LETTER_SEARCH
STATE_FIRST_LETTER_SEARCH
- Character [c] must be initialized before entering
- Searches for character [c] in the string
- Exits on end of string
- Sets new token positions for string and token to current positions
- => STATE_MATCH_SUBSTR_TAIL
STATE_MATCH_SUBSTR_TAIL:
- Matches character-to-character, including ONE_SYM_WILLCARD
- Exits on end of string
- Increases current token position in string by 1 and roll-backs to tokens positions in
string and template on end of template or last character mismatch
- => STATE_SKIP_WILDCARDS
*)
VAR
State: TState;
StrLen: INTEGER;
PatternLen: INTEGER;
StrBasePos: INTEGER; // Start position of current token
PatternBasePos: INTEGER; // Start position of current token
s: INTEGER; // Pos in Pattern
p: INTEGER; // Pos in Str
c: CHAR; // First letter to search for
PROCEDURE SkipMatchingSubstr;
BEGIN
WHILE
(p <= PatternLen) AND
(s <= StrLen) AND
(Pattern[p] <> ANY_SYMS_WILDCARD) AND
(
(Str[s] = Pattern[p]) OR
(Pattern[p] = ONE_SYM_WILDCARD)
)
DO BEGIN
INC(p);
INC(s);
END; // .WHILE
END; // .PROCEDURE SkipMatchingSubstr
BEGIN
StrLen := LENGTH(Str);
PatternLen := LENGTH(Pattern);
StrBasePos := 1;
PatternBasePos := 1;
s := 1;
p := 1;
c := #0;
State := STATE_STRICT_COMPARE;
RESULT := FALSE;
WHILE State <> STATE_EXIT DO BEGIN
CASE State OF
STATE_STRICT_COMPARE:
BEGIN
SkipMatchingSubstr;
IF (p > PatternLen) OR (Pattern[p] <> ANY_SYMS_WILDCARD) THEN BEGIN
State := STATE_EXIT;
END // .IF
ELSE BEGIN
STATE := STATE_SKIP_WILDCARDS;
END; // .ELSE
END; // .CASE STATE_STRICT_COMPARE
STATE_SKIP_WILDCARDS:
BEGIN
WHILE (p <= PatternLen) AND (Pattern[p] IN WILDCARDS) DO BEGIN
IF Pattern[p] = ONE_SYM_WILDCARD THEN BEGIN
INC(s);
END; // .IF
INC(p);
END; // .WHILE
IF p <= PatternLen THEN BEGIN
c := Pattern[p];
State := STATE_FIRST_LETTER_SEARCH;
END // .IF
ELSE BEGIN
State := STATE_EXIT;
END; // .ELSE
END; // .CASE STATE_SKIP_WILDCARDS
STATE_FIRST_LETTER_SEARCH:
BEGIN
WHILE (s <= StrLen) AND (Str[s] <> c) DO BEGIN
INC(s);
END; // .WHILE
IF s > StrLen THEN BEGIN
State := STATE_EXIT;
END // .IF
ELSE BEGIN
StrBasePos := s;
PatternBasePos := p;
INC(p);
INC(s);
State := STATE_MATCH_SUBSTR_TAIL;
END; // .ELSE
END; // .CASE STATE_FIRST_LETTER_SEARCH
STATE_MATCH_SUBSTR_TAIL:
BEGIN
SkipMatchingSubstr;
IF s > StrLen THEN BEGIN
State := STATE_EXIT;
END // .IF
ELSE IF (p > PatternLen) OR (Pattern[p] <> ANY_SYMS_WILDCARD) THEN BEGIN
INC(StrBasePos);
p := PatternBasePos;
s := StrBasePos;
State := STATE_FIRST_LETTER_SEARCH;
END // .ELSEIF
ELSE BEGIN
State := STATE_SKIP_WILDCARDS;
END; // .ELSE
END; // .CASE STATE_MATCH_SUBSTR_TAIL
END; // .SWITCH State
END; // .WHILE
RESULT := (s = (StrLen + 1)) AND (p = (PatternLen + 1));
END; // .FUNCTION Match
ASSERT( Match('', ''));
ASSERT(NOT Match('a', ''));
ASSERT(NOT Match('', 'a'));
ASSERT( Match('', '*'));
ASSERT(NOT Match('aaa', 'bbb'));
ASSERT( Match('12345abc', '123*abc'));
ASSERT(NOT Match('12345abc*d*', '123*abc'));
ASSERT(NOT Match('abceabcdef', 'abcd*f*'));
ASSERT( Match('abceabcdef', '*abcd*f*'));
ASSERT( Match('abceabcdef', '*ab*d*f*'));
ASSERT( Match('abcdefgabcefg', 'abc*efg'));
ASSERT(NOT Match('abceabcdef', 'abc*efg*efg'));
То же на pastebin (http://pastebin.com/bv2FDfjm)
Суть алгоритма, в принципе, частями изложена в комментариях. Основная проблема в вопросе, сколько символов должен кушать магический знак "*". В текущей реализации он следует принципу не-жадности. Это значит, что будет "съедена" минимально возможная строка.
Было выделено 5 ключевых состояний:
- Строгое сравнение. Обрабатывает ряд символов в начале строки до первой "*".
[abc]*?*?**cde?x* - Пропуск магических знаков. Пропускает цепочку из "*" и "?". За каждый обнаруженный символ "?" позиция в строке увеличивается на 1. При этом позиция в строке может уйти далеко за пределы её границы, но это не проблема. Успех функции - если позиции ровно в конце строки и в конце шаблона.
abc[*?*?**]cde?x* - Поиск первого символа. За цепочкой магических знаков следует обычный символ, задающий начало новой подстроке. Если символ удаётся найти, то запоминается текущая позиция в шаблоне и строке, как новая стартовая. Она используется в будущем для откатов.
abc*?*?**[c]de?x* - Проверка хвоста или тела подстроки. Посимвольный проход с учётом "?". Если очередной символ не совпадает, то увеличиваем на 1 базовую позицию в строке и откатываемся как в строке, так и в шаблоне до базовых позиций. После чего переходим к поиску первого символа снова. Если же строка совпала до "*", то очередная часть пути пройдена, переходим к пропуску магических знаков.
abc*?*?**c[de?x]* - Выход
-
Как же отвратны все эти бесконечные паскалЁвые BEGIN'ы... >:(
ps Звиняюсь за оффтоп
-
Увы. В Object Pascal старый синтаксис.
-
Ну так и де у вас всех доказательства корректности, инварианты и всё такое? )))
Ну инвариантов и все такое у меня вообще не было, потому что, видимо плохо проснувшись, решил, что нужно сделать поиск по образцу (а это LL), и написал рекурсивную процедуру, с 3-мя или 4-мя вызовами, без цикла, откаты получались автоматически, потом увидел слово рекурсия, стал от нее избавляться, мысль про откаты уже не всплывала (ибо в рекурсии они шли автоматом и в логике это как-то не отложилось как сколь-нибудь значимое), заменил рекурсию на бесконечный цикл и граничные выходы. Потом ещё почитал, и понял, что нужен не поиск по образцу(LL), а сравнение с образцом(LR), но переписывать уже лень, в принципе и так работает, хотя оно и ищет только слева-направо, а не с концов к центру.
Весь текст модуля (тот же что и выше ) + тестовая процедура и результаты (для запуска требуется A2):
MODULE Match;
IMPORT Log := KernelLog, Strings;
PROCEDURE MatchIt( CONST text, pattern : ARRAY OF CHAR;
posT, posP : LONGINT;
lenT, lenP : LONGINT ): BOOLEAN;
VAR
chT, chP: CHAR;
iT, iP : LONGINT;
PROCEDURE NoMoreCharInPattern(): BOOLEAN;
BEGIN
WHILE ( pattern[ posP ] = '*' ) & ( posP < lenP ) DO
INC( posP );
END;
RETURN posP = lenP;
END NoMoreCharInPattern;
PROCEDURE FindCharInText( ch: CHAR; pos: LONGINT ): BOOLEAN;
BEGIN
WHILE pos # lenT DO
IF text[ pos ] = ch THEN posT:= pos; RETURN TRUE END;
INC ( pos );
END;
RETURN FALSE;
END FindCharInText;
PROCEDURE Retry;
BEGIN
posP := iP;
INC( posP );
INC( posT );
iT := posT;
END Retry;
BEGIN
iT := lenT;
iP := lenP;
LOOP
IF posT = lenT THEN
RETURN NoMoreCharInPattern();
ELSIF posP = lenP THEN
IF ( iP # lenP ) & FindCharInText( pattern[iP] , iT ) THEN
Retry
ELSE
RETURN FALSE;
END;
ELSE
chT := text[ posT ];
chP := pattern[ posP ];
IF chP = '*' THEN
INC( posP );
IF NoMoreCharInPattern() THEN
RETURN TRUE;
ELSIF FindCharInText( pattern[ posP ], posT ) THEN
iP := posP;
INC( posP );
INC( posT );
iT := posT;
ELSE
RETURN FALSE;
END;
ELSIF ( chP = chT ) OR ( chP = '?' ) THEN
INC( posP );
INC( posT );
ELSE
IF ( iP # lenP ) & FindCharInText( pattern[iP] , iT ) THEN
Retry;
ELSE
RETURN FALSE;
END;
END;
END;
END;
END MatchIt;
PROCEDURE DoMatch*( CONST text, pattern: ARRAY OF CHAR ): BOOLEAN;
BEGIN
RETURN MatchIt( text, pattern, 0, 0, Strings.Length( text ), Strings.Length( pattern ));
END DoMatch;
PROCEDURE Test;
BEGIN
Log.String( "=========================================" ); Log.Ln;
Log.String( " 1)'' $ '' = " );
Log.Boolean( DoMatch( '' , '' ));
Log.Ln;
Log.String( " 2)'' $ 'a' = " );
Log.Boolean( DoMatch( '' , 'a' ));
Log.Ln;
Log.String( " 3)'' $ '*' = " );
Log.Boolean( DoMatch( '' , '*' ));
Log.Ln;
Log.String( " 4)'a' $ '' = " );
Log.Boolean( DoMatch( 'a' , '' ));
Log.Ln;
Log.String( " 5)'abcxyz' $ '*' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*' ));
Log.Ln;
Log.String( " 6)'abcxyz' $ 'ab*' = " );
Log.Boolean( DoMatch( 'abcxyz' , 'ab*' ));
Log.Ln;
Log.String( " 7)'abcxyz' $ '*ab' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*ab' ));
Log.Ln;
Log.String( " 8)'abcxyz' $ '*yz' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*yz' ));
Log.Ln;
Log.String( " 9)'abcxyz' $ '*yz*' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*yz*' ));
Log.Ln;
Log.String( "10)'abcxyz' $ 'ab*yz' = " );
Log.Boolean( DoMatch( 'abcxyz' , 'ab*yz' ));
Log.Ln;
Log.String( "11)'abcxyz' $ '*cx*' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*cx*' ));
Log.Ln;
Log.String( "12)'abcxyz' $ '*a*c*y*' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*a*c*y*' ));
Log.Ln;
Log.String( "13)'abcxyz' $ 'a*b***c*z' ) = " );
Log.Boolean( DoMatch( 'abcxyz' , 'a*b***c*z' ));
Log.Ln;
Log.String( "14)'abcxyz' $ '**a*b***y*z**' ) = " );
Log.Boolean( DoMatch( 'abcxyz' , '**a*b***y*z**' ));
Log.Ln;
Log.String( "15)'abcxyz' $ 'ab*x*c*yz' ) = " );
Log.Boolean( DoMatch( 'abcxyz' , 'ab*x*c*yz' ));
Log.Ln;
Log.String( "16)'abcxyz' $ '*cx' ) = " );
Log.Boolean( DoMatch( 'abcxyz' , '*cx' ));
Log.Ln;
Log.String( "17)'abcxyxyz' $ '*xyz' ) = " );
Log.Boolean( DoMatch( 'abcxyxyz' , '*xyz' ));
Log.Ln;
Log.String( "18)'abcxyzxy' $ '*xyz' ) = " );
Log.Boolean( DoMatch( 'abcxyzxy' , '*xyz' ));
Log.Ln;
Log.String( "19)'abcxyzxyz' $ '*xyz' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz' ));
Log.Ln;
Log.String( "20)'abcxyzxyz' $ '*xyz*xyz' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz*xyz' ));
Log.Ln;
Log.String( "=========================================" ); Log.Ln;
END Test;
PROCEDURE Do*;
BEGIN
Test;
END Do;
END Match.
SystemTools.Free Match ~
Match.Do~
=========================================
1)'' $ '' = TRUE
2)'' $ 'a' = FALSE
3)'' $ '*' = TRUE
4)'a' $ '' = FALSE
5)'abcxyz' $ '*' = TRUE
6)'abcxyz' $ 'ab*' = TRUE
7)'abcxyz' $ '*ab' = FALSE
8)'abcxyz' $ '*yz' = TRUE
9)'abcxyz' $ '*yz*' = TRUE
10)'abcxyz' $ 'ab*yz' = TRUE
11)'abcxyz' $ '*cx*' = TRUE
12)'abcxyz' $ '*a*c*y*' = TRUE
13)'abcxyz' $ 'a*b***c*z' ) = TRUE
14)'abcxyz' $ '**a*b***y*z**' ) = TRUE
15)'abcxyz' $ 'ab*x*c*yz' ) = FALSE
16)'abcxyz' $ '*cx' ) = FALSE
17)'abcxyxyz' $ '*xyz' ) = TRUE
18)'abcxyzxy' $ '*xyz' ) = FALSE
19)'abcxyzxyz' $ '*xyz' ) = TRUE
20)'abcxyzxyz' $ '*xyz*xyz' ) = TRUE
=========================================
-
Я обобщил задачу до заявленной функциональности магических символов (WILDCARDS) в API OS Windows. В частности:
"*" - нуль или более любых символов
"?" - один любой символ
А квадратные скобки что означают: [abc]?
-
Часть шаблона, к которой относится указанное состояние.
-
Ясности не добавилось. Мне бы попроще, типа такого:
[ ]: Any single character within the specified range ([a-f]) or set ([abcdef]).
-
Илья, интересно было бы Ваше решение.
Решать задачу в духе интерпретации сейчас времени нет. Думаю, что Ваше решение вполне себе.
Компилирующая реализация - мой давний Rocot и Рефал-0 (http://www.oberoncore.ru/library/ermakov_refal-0_rocot, http://www.oberoncore.ru/bbcc/subs/rocot/start).
Там паттерны ограничиваются максимум двумя звёздочками (e-переменными в терминах Рефала), при произвольном количестве ? (s-переменных) - и для такого максимального случая генерируется код концевых сравнений и цикл линейного поиска центральной части (того, что между двумя звёздочками).
Ну а произвольная мощность разбора уже может быть достигнута за счёт того, что язык - Тьюринг-полный и рекурсивный.
-
Косметика + условие для учета '?' + дополнительные тесты на прохождение '?':
MODULE Match;
IMPORT Log := KernelLog, Strings;
PROCEDURE MatchIt( CONST text, pattern : ARRAY OF CHAR;
posT, posP : LONGINT;
lenT, lenP : LONGINT ): BOOLEAN;
VAR
chT, chP: CHAR;
iT, iP : LONGINT;
PROCEDURE NoMoreCharInPattern(): BOOLEAN;
BEGIN
WHILE ( posP # lenP ) & ( pattern[ posP ] = '*' ) DO
INC( posP );
END;
RETURN posP = lenP;
END NoMoreCharInPattern;
PROCEDURE FindCharInText( ch: CHAR; pos: LONGINT ): BOOLEAN;
BEGIN
WHILE pos # lenT DO
IF ( text[ pos ] = ch ) OR ( ch = '?' ) THEN posT := pos; RETURN TRUE END;
INC ( pos );
END;
RETURN FALSE;
END FindCharInText;
PROCEDURE Retry;
BEGIN
posP := iP;
INC( posP );
INC( posT );
iT := posT;
END Retry;
BEGIN
iT := lenT;
iP := lenP;
LOOP
IF posT = lenT THEN
RETURN NoMoreCharInPattern();
ELSIF posP = lenP THEN
IF ( iP # lenP ) & FindCharInText( pattern[iP] , iT ) THEN
Retry
ELSE
RETURN FALSE;
END;
ELSE
chT := text[ posT ];
chP := pattern[ posP ];
IF chP = '*' THEN
INC( posP );
IF NoMoreCharInPattern() THEN RETURN TRUE END;
chP := pattern[ posP ];
IF FindCharInText( chP, posT ) THEN
iP := posP;
INC( posP );
INC( posT );
iT := posT;
ELSE
RETURN FALSE;
END;
ELSIF ( chP = chT ) OR ( chP = '?' ) THEN
INC( posP );
INC( posT );
ELSE
IF ( iP # lenP ) & FindCharInText( pattern[iP] , iT ) THEN
Retry;
ELSE
RETURN FALSE;
END;
END;
END;
END;
END MatchIt;
PROCEDURE DoMatch*( CONST text, pattern: ARRAY OF CHAR ): BOOLEAN;
BEGIN
RETURN MatchIt( text, pattern, 0, 0, Strings.Length( text ), Strings.Length( pattern ));
END DoMatch;
PROCEDURE Test;
BEGIN
Log.String( "=========================================" ); Log.Ln;
Log.String( " 1)'' $ '' = " );
Log.Boolean( DoMatch( '' , '' ));
Log.Ln;
Log.String( " 2)'' $ 'a' = " );
Log.Boolean( DoMatch( '' , 'a' ));
Log.Ln;
Log.String( " 3)'' $ '*' = " );
Log.Boolean( DoMatch( '' , '*' ));
Log.Ln;
Log.String( " 4)'a' $ '' = " );
Log.Boolean( DoMatch( 'a' , '' ));
Log.Ln;
Log.String( " 5)'abcxyz' $ '*' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*' ));
Log.Ln;
Log.String( " 6)'abcxyz' $ 'ab*' = " );
Log.Boolean( DoMatch( 'abcxyz' , 'ab*' ));
Log.Ln;
Log.String( " 7)'abcxyz' $ '*ab' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*ab' ));
Log.Ln;
Log.String( " 8)'abcxyz' $ '*yz' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*yz' ));
Log.Ln;
Log.String( " 9)'abcxyz' $ '*yz*' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*yz*' ));
Log.Ln;
Log.String( "10)'abcxyz' $ 'ab*yz' = " );
Log.Boolean( DoMatch( 'abcxyz' , 'ab*yz' ));
Log.Ln;
Log.String( "11)'abcxyz' $ '*cx*' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*cx*' ));
Log.Ln;
Log.String( "12)'abcxyz' $ '*a*c*y*' = " );
Log.Boolean( DoMatch( 'abcxyz' , '*a*c*y*' ));
Log.Ln;
Log.String( "13)'abcxyz' $ 'a*b***c*z' ) = " );
Log.Boolean( DoMatch( 'abcxyz' , 'a*b***c*z' ));
Log.Ln;
Log.String( "14)'abcxyz' $ '**a*b***y*z**' ) = " );
Log.Boolean( DoMatch( 'abcxyz' , '**a*b***y*z**' ));
Log.Ln;
Log.String( "15)'abcxyz' $ 'ab*x*c*yz' ) = " );
Log.Boolean( DoMatch( 'abcxyz' , 'ab*x*c*yz' ));
Log.Ln;
Log.String( "16)'abcxyz' $ '*cx' ) = " );
Log.Boolean( DoMatch( 'abcxyz' , '*cx' ));
Log.Ln;
Log.String( "17)'abcxyxyz' $ '*xyz' ) = " );
Log.Boolean( DoMatch( 'abcxyxyz' , '*xyz' ));
Log.Ln;
Log.String( "18)'abcxyzxy' $ '*xyz' ) = " );
Log.Boolean( DoMatch( 'abcxyzxy' , '*xyz' ));
Log.Ln;
Log.String( "19)'abcxyzxyz' $ '*xyz' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz' ));
Log.Ln;
Log.String( "20)'abcxyzxyz' $ '*xyz*xyz' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz*xyz' ));
Log.Ln;
Log.String( "21)'' $ '?' ) = " );
Log.Boolean( DoMatch( '' , '?' ));
Log.Ln;
Log.String( "22)'a' $ '?' ) = " );
Log.Boolean( DoMatch( 'a' , '?' ));
Log.Ln;
Log.String( "23)'az' $ '?' ) = " );
Log.Boolean( DoMatch( 'az' , '?' ));
Log.Ln;
Log.String( "24)'az' $ '??' ) = " );
Log.Boolean( DoMatch( 'az' , '??' ));
Log.Ln;
Log.String( "25)'az' $ '?*?' ) = " );
Log.Boolean( DoMatch( 'az' , '?*?' ));
Log.Ln;
Log.String( "26)'abyz' $ '?*?' ) = " );
Log.Boolean( DoMatch( 'abyz' , '?*?' ));
Log.Ln;
Log.String( "27)'abyz' $ '?*?*' ) = " );
Log.Boolean( DoMatch( 'abyz' , '?*?*' ));
Log.Ln;
Log.String( "28)'abcxyzxyz' $ '*?*' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*?*' ));
Log.Ln;
Log.String( "29)'abcxyzxyz' $ '*xyz*?yz' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz*?yz' ));
Log.Ln;
Log.String( "30)'abcxyzxyz' $ '*?xyz*?yz' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*?xyz*?yz' ));
Log.Ln;
Log.String( "31)'abcxyzxyz' $ '?*xyz*y?' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '?*xyz*y?' ));
Log.Ln;
Log.String( "32)'abcxyzxyz' $ '*x?z' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*x?z' ));
Log.Ln;
Log.String( "33)'abcxyzxyz' $ '*xyz*x?z' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz*x?z' ));
Log.Ln;
Log.String( "34)'abcxyzxyz' $ '*x?z*x?z' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*x?z*x?z' ));
Log.Ln;
Log.String( "35)'abcxyzxyz' $ '*??x?z*x?z' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*??x?z*x?z' ));
Log.Ln;
Log.String( "36)'abcxyzxyz' $ '*??x?0z*x?z' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*??x?0z*x?z' ));
Log.Ln;
Log.String( "37)'abcxyzxyz' $ '*??x?z?*x?z' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*??x?z?*x?z' ));
Log.Ln;
Log.String( "38)'abcxyzxyz' $ '*??x?z?*?z' ) = " );
Log.Boolean( DoMatch( 'abcxyzxyz' , '*??x?z?*?z' ));
Log.Ln;
Log.String( "39)'abcxyz0xyz' $ '*??x?z?*x?z' ) = " );
Log.Boolean( DoMatch( 'abcxyz0xyz' , '*??x?z?*x?z' ));
Log.Ln;
Log.String( "=========================================" ); Log.Ln;
END Test;
PROCEDURE Do*;
BEGIN
Test;
END Do;
END Match.
SystemTools.Free Match ~
Match.Do~
Результаты тестов:
1)'' $ '' = TRUE
2)'' $ 'a' = FALSE
3)'' $ '*' = TRUE
4)'a' $ '' = FALSE
5)'abcxyz' $ '*' = TRUE
6)'abcxyz' $ 'ab*' = TRUE
7)'abcxyz' $ '*ab' = FALSE
8)'abcxyz' $ '*yz' = TRUE
9)'abcxyz' $ '*yz*' = TRUE
10)'abcxyz' $ 'ab*yz' = TRUE
11)'abcxyz' $ '*cx*' = TRUE
12)'abcxyz' $ '*a*c*y*' = TRUE
13)'abcxyz' $ 'a*b***c*z' ) = TRUE
14)'abcxyz' $ '**a*b***y*z**' ) = TRUE
15)'abcxyz' $ 'ab*x*c*yz' ) = FALSE
16)'abcxyz' $ '*cx' ) = FALSE
17)'abcxyxyz' $ '*xyz' ) = TRUE
18)'abcxyzxy' $ '*xyz' ) = FALSE
19)'abcxyzxyz' $ '*xyz' ) = TRUE
20)'abcxyzxyz' $ '*xyz*xyz' ) = TRUE
21)'' $ '?' ) = FALSE
22)'a' $ '?' ) = TRUE
23)'az' $ '?' ) = FALSE
24)'az' $ '??' ) = TRUE
25)'az' $ '?*?' ) = TRUE
26)'abyz' $ '?*?' ) = TRUE
27)'abyz' $ '?*?*' ) = TRUE
28)'abcxyzxyz' $ '*?*' ) = TRUE
29)'abcxyzxyz' $ '*xyz*?yz' ) = TRUE
30)'abcxyzxyz' $ '*?xyz*?yz' ) = TRUE
31)'abcxyzxyz' $ '?*xyz*y?' ) = TRUE
32)'abcxyzxyz' $ '*x?z' ) = TRUE
33)'abcxyzxyz' $ '*xyz*x?z' ) = TRUE
34)'abcxyzxyz' $ '*x?z*x?z' ) = TRUE
35)'abcxyzxyz' $ '*??x?z*x?z' ) = TRUE
36)'abcxyzxyz' $ '*??x?0z*x?z' ) = FALSE
37)'abcxyzxyz' $ '*??x?z?*x?z' ) = FALSE
38)'abcxyzxyz' $ '*??x?z?*?z' ) = TRUE
39)'abcxyz0xyz' $ '*??x?z?*x?z' ) = TRUE
-
Жаль, нельзя проверить. Раз там Оберон, может быть Оберон-07М от Рефата подошёл бы для несложного примера? Правда от возвратов с середины пришлось бы отказаться.
-
Жаль, нельзя проверить. Раз там Оберон, может быть Оберон-07М от Рефата подошёл бы для несложного примера? Правда от возвратов с середины пришлось бы отказаться.
Не знаю, что за 07M такой, но вроде в самом поиске-сравнении ничего сверх Оберона нет, Strings.Length можно в нужный модуль перенести или, если сравниваемые строки указаны прямо в тексте программы (как у меня в тесте), можно и просто LEN( string ), а вместо KernelLog может какой-нибудь Out пойдет. В принципе можно перевести и на Паскаль для сравнения, если будет время - займусь.
Проблему с возвратами с середины не понял.
К тому-же изначально я всё-таки делал поиск а не сравнение, а потом, преобразовал в сравнение, добавив еще один откат(если его убрать, то поиск и останется). Поэтому правильно написанному сравнению алгоритм проиграет в эффективности.
-
Обнаружил в модуле Strings от A2 процедуру Match
(** Simple pattern matching with support for "*" and "?" wildcards - returns TRUE if name matches mask. Patent pending ;-) *)
PROCEDURE Match*(CONST mask, name: ARRAY OF CHAR): BOOLEAN;
VAR m,n, om, on: LONGINT; f: BOOLEAN;
BEGIN
m := 0; n := 0; om := -1;
f := TRUE;
LOOP
IF (mask[m] = "*") THEN
om := m; INC(m);
WHILE (name[n] # 0X) & (name[n] # mask[m]) DO INC(n) END;
on := n
ELSIF (mask[m] = "?") THEN
IF (name[n] = 0X) THEN f := FALSE; EXIT END;
INC(m); INC(n)
ELSE
IF (mask[m] # name[n]) THEN
IF (om = -1) THEN f := FALSE; EXIT
ELSIF (name[n] # 0X) THEN (* try the next position *)
m := om; n := on + 1;
IF (name[n] = 0X) THEN f := FALSE; EXIT END
ELSE
f := FALSE; EXIT
END
ELSE INC(m); INC(n)
END
END;
IF (mask[m] = 0X) & ((name[n] = 0X) OR (om=-1)) THEN EXIT END
END;
RETURN f & (name[n] = 0X)
END Match;
Результаты тестов (расхождения помечены "-" в последнем столбце).
строка шаблон мойвар A2 *
======================================================
1)'' $ '' = TRUE ASSERT
2)'' $ 'a' = FALSE FALSE
3)'' $ '*' = TRUE TRUE
4)'a' $ '' = FALSE FALSE
5)'abcxyz' $ '*' = TRUE TRUE
6)'abcxyz' $ 'ab*' = TRUE TRUE
7)'abcxyz' $ '*ab' = FALSE FALSE
8)'abcxyz' $ '*yz' = TRUE TRUE
9)'abcxyz' $ '*yz*' = TRUE TRUE
10)'abcxyz' $ 'ab*yz' = TRUE TRUE
11)'abcxyz' $ '*cx*' = TRUE TRUE
12)'abcxyz' $ '*a*c*y*' = TRUE TRUE
13)'abcxyz' $ 'a*b***c*z' = TRUE FALSE -
14)'abcxyz' $ '**a*b***y*z**' = TRUE FALSE -
15)'abcxyz' $ 'ab*x*c*yz' = FALSE FALSE
16)'abcxyz' $ '*cx' = FALSE FALSE
17)'abcxyxyz' $ '*xyz' = TRUE TRUE
18)'abcxyzxy' $ '*xyz' = FALSE FALSE
19)'abcxyzxyz' $ '*xyz' = TRUE TRUE
20)'abcxyzxyz' $ '*xyz*xyz' = TRUE TRUE
21)'' $ '?' = FALSE FALSE
22)'a' $ '?' = TRUE TRUE
23)'az' $ '?' = FALSE FALSE
24)'az' $ '??' = TRUE TRUE
25)'az' $ '?*?' = TRUE FALSE -
26)'abyz' $ '?*?' = TRUE FALSE -
27)'abyz' $ '?*?*' = TRUE FALSE -
28)'abcxyzxyz' $ '*?*' = TRUE FALSE -
29)'abcxyzxyz' $ '*xyz*?yz' = TRUE FALSE -
30)'abcxyzxyz' $ '*?xyz*?yz' = TRUE FALSE -
31)'abcxyzxyz' $ '?*xyz*y?' = TRUE TRUE
32)'abcxyzxyz' $ '*x?z' = TRUE TRUE
33)'abcxyzxyz' $ '*xyz*x?z' = TRUE TRUE
34)'abcxyzxyz' $ '*x?z*x?z' = TRUE TRUE
35)'abcxyzxyz' $ '*??x?z*x?z' = TRUE FALSE -
36)'abcxyzxyz' $ '*??x?0z*x?z' = FALSE FALSE
37)'abcxyzxyz' $ '*??x?z?*x?z' = FALSE FALSE
38)'abcxyzxyz' $ '*??x?z?*?z' = TRUE FALSE -
39)'abcxyz0xyz' $ '*??x?z?*x?z' = TRUE FALSE -
-
Не совсем тривиальная задача, выходит.
-
Щас набежит info21 и назовет разработчиков A2 мейнстримщиками, а Active Oberon неправильным обероном.
Ведь у правильных оберонщиков все работает правильно "сразу и без отладки" ;D
-
А вот он возьмёт и не набежит. Не будет ли стыдно предсказателю за очередное несбывшееся предсказание?
-
Не понял вашего негодования. ???
Нет, стыдно не будет. Это была шутка.
ps На каком основании вы мне клеймо "предсказателя" вешаете?
Да еще и "очередное несбывшееся"... Чем я вам насолил?
-
Да в общем-то, никаких бурных эмоций я не испытывал при прочтении сообщения. Поэтому, нет никакого негодование, я спокоен.
Однако, если это шутка, то она не вызывает положительных эмоций.
И клейма я не ставил. Предсказание - это рассказ о том, что в будущем. Если Вам не нравится это слово, то его можно заменить на "прогноз".
-
Ладно. Проехали.
-
До полнолуния ещё далеко, запаситесь терпением так что... ))
-
Щас набежит info21 и назовет разработчиков A2 мейнстримщиками, а Active Oberon неправильным обероном.
Ведь у правильных оберонщиков все работает правильно "сразу и без отладки" ;D
Уже горел народ на том, что брал из А2 "глючащие" алгоритмы. Что-то было то ли сетевое, то ли PNG, то ли сжатие... Глючило как раз из такого многоэтажного ужаса с выходами из середины. Когда перепроектировали цикл как положено, всё стало нормально.
-
Мне вот любопытно. А существует ли система, которая написана грамотно? Где посмотреть на это чудо?
Ну т.е. циклы "построенные под доказательство" и все такое...
Я вот давно уже сам для себя пытаюсь понять к чему ближе программирование... к формальным методам или к производству.
То, что я каждый день наблюдаю пока много ближе именно к производству.
А как сказал один мой товарищ (бизнесмен): "Всегда будь готов к 20% брака в любом производстве".
-
Мне вот любопытно. А существует ли система, которая написана грамотно? Где посмотреть на это чудо?
Ну т.е. циклы "построенные под доказательство" и все такое...
Это такой тонкий троллинг? :) Конечно есть!!! Оберон ОС же ш!!! И ББ же ш!!!
-
В чЁрной коробке говнокода хватает.
А Оберон.... ну может быть.... но есть много оговорок:
1. Система слишком маленькая, чтобы там явно выделился человеческий фактор
2. Разработчик и постановщик задачи одно лицо. Когда тебе ставит задачу другой человек (обычно не знающий программирования), то сложность возрастает на порядки.
3. Практически отсутствует сопротивление среды (требования не меняются каждый день; нет нужды реагировать на вопли пользователей)
4. и т.д.
т.е. Оберон не считается, т.к. это тепличное растение.
-
Уже горел народ на том, что брал из А2 "глючащие" алгоритмы. Что-то было то ли сетевое, то ли PNG, то ли сжатие... Глючило как раз из такого многоэтажного ужаса с выходами из середины. Когда перепроектировали цикл как положено, всё стало нормально.
Во-первых, все мы люди, ми склонны к ошибкам, во-вторых, далеко не все в А2 написано мэтрами, много чего и студентами, в третьих, если мы пишем для диссертации, для книги, ведем исследовтельскую работу, то стиль будет один, а если все это реализуем в реальной работе, то совсем другой, и здесь от RETURN'ов из середины глупо отказываться, если это увеличит эффективность алгоритма, в четвертых, относительно данной конкретной процедуры, то там же написано - "простая", и предназначена она для конкретного применения, которое полностью покрывает, естественно, она не обязана учитывать монструозные конструкции типа "***?*?***?*?***", потому что это, на самом деле, неправильно составленный образец, зачем там 3 звезды подряд?
С другой стороны, встречаются действительно глупые ошибки, и если бы А2, как и вообще Обероны, были бы чуточку популярнее, в том смысле, что их бы кто-нибудь в реальной работе использовал, то пользователи непременно бы обнаружили ошибки и заставили разработчиков поработать над их устранением. Сейчас же это не более чем концепт, а учитывая, что она в обучении используется (или использовалась), то может и ошибки там сознательно висят, а студиозусы на спецкурсах их находят и исправляют. У этой процедуры есть неоспоримое преимущество - она очень маленькая, простая и понятная. Для студентов самое то, а сколько возможностей для творчества...
-
Щас набежит info21 и назовет разработчиков A2 мейнстримщиками, а Active Oberon неправильным обероном.
Ведь у правильных оберонщиков все работает правильно "сразу и без отладки" ;D
Уже горел народ на том, что брал из А2 "глючащие" алгоритмы. Что-то было то ли сетевое, то ли PNG, то ли сжатие... Глючило как раз из такого многоэтажного ужаса с выходами из середины. Когда перепроектировали цикл как положено, всё стало нормально.
То есть программирование на Обероне отнюдь не гарантирует качества софта.
Что и требовалось доказать... :P
-
2. Разработчик и постановщик задачи одно лицо. Когда тебе ставит задачу другой человек (обычно не знающий программирования), то сложность возрастает на порядки.
3. Практически отсутствует сопротивление среды (требования не меняются каждый день; нет нужды реагировать на вопли пользователей)
т.е. Оберон не считается, т.к. это тепличное растение.
Это не имеет отношения к Оберону, это особенности прикладной автоматизации... Хорошо известные.
Если автоматизатор - крупная компания, то она часто выделяет подразделение, которое занимается программированием "общего знаменателя" для своих проектов (библиотек, инструментов). И у этого подразделения будут тоже "тепличные условия".
А про циклы - какие там нах супер-формальные методы, коллега? Написать цикл аккуратно без выхода из середины - это супер-сложно? Легче наклепать и иметь 20% брака?
-
У этой процедуры есть неоспоримое преимущество - она очень маленькая, простая и понятная. Для студентов самое то, а сколько возможностей для творчества...
Процедуру с 4 EXIT-ами из середины Вы называете понятной? Да я её даже читать не буду, сразу выкину. :) Я не собираюсь изображать из себя процессор и гонять в уме построчно все варианты. Если я не могу проверить логически, не-императивно, то фтопку..
Заходил к нам когда-то на форум компиляторщик из XDS - и в грудь ся ударял, что у них там такие циклы, которые без выхода из середины ну никак.
И вот шо из этого вышло:
http://oberoncore.ru/wiki/%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BF%D1%80%D0%BE%D0%BC%D1%8B%D1%88%D0%BB%D0%B5%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0
-
Мне вот любопытно. А существует ли система, которая написана грамотно? Где посмотреть на это чудо?
Ну т.е. циклы "построенные под доказательство" и все такое...
Не знаю, насколько грамотно, но таки с доказательствами -- это микроядро seL4 (7500 строк кода с доказательством в 200,000 строк), верифицированный компилятор подмножества Си Compcert (http://en.wikipedia.org/wiki/Compcert).
Наверняка ещё что-то есть...
-
То есть программирование на Обероне отнюдь не гарантирует качества софта.
Что и требовалось доказать... :P
УУУУ провокатор, однако :)
-
Процедуру с 4 EXIT-ами из середины Вы называете понятной? Да я её даже читать не буду, сразу выкину. :) Я не собираюсь изображать из себя процессор и гонять в уме построчно все варианты. Если я не могу проверить логически, не-императивно, то фтопку..
Самое забавное, что если посмотреть исходники А2, ЧЯ, я даже подозреваю, что и Виртовский Оберон, то там такого кода вагон и огромадная телега, вдвойне забано, что написано это Тру-Оберонщики, самими "отцами-создатели".
Заходил к нам когда-то на форум компиляторщик из XDS - и в грудь ся ударял, что у них там такие циклы, которые без выхода из середины ну никак.
И вот шо из этого вышло:
http://oberoncore.ru/wiki/%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BF%D1%80%D0%BE%D0%BC%D1%8B%D1%88%D0%BB%D0%B5%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0
Да кто спорит, что нельзя, конечно можно, но вот нужно ли всегда? Потому что в итоге может получиться не менее монструозная конструкция. Видимо учитывая это и Тру-Оберонщики из альма-матер идут другим путем.
-
Можно. Достаточно структурировать мозги, то бишь дать установку. Через неделю старый код и фобии покажутся страшным сном. Я никаких проблем не испытываю на любых ЯП, с которыми приходится работать. А вот верифицировать, даже приблизительно, конструкции с прыжками - это насилие над разумом.
Касаемо ** - это корректный шаблон. Спецификация: "*" стоит вместо нуля или более символов.
-
Можно. Достаточно структурировать мозги, то бишь дать установку. Через неделю старый код и фобии покажутся страшным сном. Я никаких проблем не испытываю на любых ЯП, с которыми приходится работать. А вот верифицировать, даже приблизительно, конструкции с прыжками - это насилие над разумом.
Если это ко мне, то это несколтко не ко мне ))) Я писал и на этом форуме, что не люблю GOTO, BREAK'и, EXIT'ы, RETURN'ы, и предпочитаю более структурированные подходы, но без монструозных десятиэтажных условий. Но их (return'ов, exit'ов...) наличие меня в ступор не вводит. Что касается процедуры А2, да и моей тоже, в которой еще больше ретурнов получилось, то там таки не прыжки, а выходы из процедуры по достижению условий с возвратом результата. Хотя для кого-то это одн и тоже, маразм и прочая и прочая. Спорить даже не буду, как только человек начинает писать что-то под микроконтроллеры или системы с ограниченными ресурсами, то наступает понимание, что не всё так просто и однозначно. Если, к примеру, посмотреть код Вирта, то становится очевидным, что его стиль программирования сформировался в условиях недостатка вычислительных ресурсов. Можено сказать, что такой код ужасен, малочитабелен и совершенно непонимаем без "словаря"-таблиц соответствий, но он учитывает определенные реалии, которые, естественно, далеки от "мейнстрима".
Касаемо ** - это корректный шаблон. Спецификация: "*" стоит вместо нуля или более символов.
Не знаю, но как по мне, так ** абсолютно бессмысленный шаблон
-
Да кто спорит, что нельзя, конечно можно, но вот нужно ли всегда? Потому что в итоге может получиться не менее монструозная конструкция.
Из моих 12 лет в программировании 5 я писал, не заморачиваясь и не зная про "правильные циклы". (И про Оберон тоже).
for и break для поиска - да как делать нечего.
Потом попробовал стиль "правильных циклов". Это другой уровень алгоритмического "ощущения", вплоть до того, как ты "чувствуешь" алгоритм в голове. Так шо все эти рассуждения "нужно ли всегда", прикрывающие лень заставить себя изменить метод и попробовать... просто отговорки.
-
Я писал и на этом форуме, что не люблю GOTO, BREAK'и, EXIT'ы, RETURN'ы, и предпочитаю более структурированные подходы, но без монструозных десятиэтажных условий.
Я не могу знать про Вас, но в большинстве случаев, когда человек утверждает "я тоже не люблю и предпочитаю структурное...", он пишет что-нибудь с булевскими признаками в условии, заменяя ими и присваиванием внутри цикла явный break...
"Правильные циклы" - это не когда избавились от break. А когда само принятие решения "продолжать или нет" полностью сконцентрировано в условии цикла (или условиях многоветочного цикла).
Может быть, это не о Вас, но об очень многих.
-
Так шо все эти рассуждения "нужно ли всегда", прикрывающие лень заставить себя изменить метод и попробовать... просто отговорки.
Ясно, видимо в ETHZ низкая культура программирования
-
"Правильные циклы" - это не когда избавились от break. А когда само принятие решения "продолжать или нет" полностью сконцентрировано в условии цикла (или условиях многоветочного цикла).
Так там выходы из процедуры по достижению результатов, а цикл там постольку-поскольку, как я понимаю, это то же что и у меня - избавление от рекурсии малой кровью, т.е. циклы к этим конкретным процедурам/алгоритмам имеет отношение постольку-поскольку. Если сразу писать с использованием цикла, то ясное дело, получился бы совершенно другой код. Хотя может и нет, учитывая что так написано очень многое в А2 и ЧЯ, сейчас сложно сказать что получилось бы и у меня, как говорится вышло то, что вышло... кто смжет, пусть сделает лучше
-
"Правильные циклы" - это не когда избавились от break. А когда само принятие решения "продолжать или нет" полностью сконцентрировано в условии цикла (или условиях многоветочного цикла).
Я повторюсь, это называется "культ карго" (http://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%BB%D1%8C%D1%82_%D0%BA%D0%B0%D1%80%D0%B3%D0%BE):
В наиболее известных культах карго из кокосовых пальм и соломы строятся «точные копии» правильных циклов взлётно-посадочных полос, аэропортов и радиовышек. Члены культа строят их, веря в то, что эти постройки привлекут транспортные самолёты (которые считаются посланниками духов), заполненные грузом (карго). Верующие регулярно проводят строевые учения («муштру») и некое подобие военных маршей, используя ветки вместо винтовок и рисуя на теле ордена и надписи Дейкстра «USA».
-
Потом попробовал стиль "правильных циклов". Это другой уровень алгоритмического "ощущения", вплоть до того, как ты "чувствуешь" алгоритм в голове. Так шо все эти рассуждения "нужно ли всегда", прикрывающие лень заставить себя изменить метод и попробовать... просто отговорки.
У меня было несколько подходов к "правильным" циклам и прочим ретурнам из середины. Растянулось по времени примерно на год. Каждый раз, когда я возвращался к такому "правильному" коду для чтения - он мне не нравился. Нет, я не пишу break для поиска и не использую continue (да и никогда не злоупотреблял, кроме как на заре в студенческие времена). Но "return по достижению" из середины (как в моем примере в этой теме), в том числе и из цикла - абсолютно нормально и читаемо. Так что у меня больше нет иллюзий. Я вполне допускаю, что в языке ОБЕРОН требование "абсолютной структурности" более жизнеспособно из-за отсутсвия семантики завершения (using/with/finally/деструкторы в других языках). Но только в языке ОБЕРОН. В том же Си эта семантика обеспечивается правильным использованием goto (вместо return из середины).
И еще небольшое замечание про эффективность и реальную жизнь. Я перевел код Peter Almazov (в котором он как раз борется за единственность return) на С++ на предмет посмотреть соптимизится ли хвостовая рекурсия. Оптимизится. Но только при отказе от искусственной переменной возврата и использовании "return из середины". Это конечно ничего не доказывает, но... оно так.
-
Да кто спорит, что нельзя, конечно можно, но вот нужно ли всегда? Потому что в итоге может получиться не менее монструозная конструкция.
Из моих 12 лет в программировании 5 я писал, не заморачиваясь и не зная про "правильные циклы". (И про Оберон тоже).
for и break для поиска - да как делать нечего.
До сих пор использую for для поиска, но всё же стараюсь без break... Что-то типа:
bool found = false;
for (int i = 0; i < list->Count() && !found; i++)
{
if (list->Items[i] == xxx)
{
elem = list->Items[i];
found = true;
}
}
if (found)
{
......
}(В VCL есть список TList, который элементы списка хранит в массиве, там доступ к элементам массива по индексу быстрый...)
Быстро-быстро нагавнякал -- работает и ладно )))
-
Быстро-быстро нагавнякал -- работает и ладно )))
Не, это не труЪ цикл. Илья как раз упоминал это - убрать break мало, надо чтоб все было в условии цикла, без всяких костыльных переменных. Ну и последующая проверка по второму разу.
-
Вот так что ли:
for (int i = 0; (i < list->Count()) && (list->Items[i] != xxx); i++) {}
if (list->Items[i] == xxx)
{
......
} ?
Вроде компактнее выходит...
А если проверка тяжёлая? Как по вычислениям, так и по дополнительным действиям?
-
Типичный while. А тяжёлая проверка уходит в подпрограмму.
i = 0;
while ((i < list->Count()) && (list->Items[i] != xxx))
{
i++;
}
if (i < list.Count())
{
printf('yep');
}
-
Вроде компактнее выходит...
А если проверка тяжёлая? Как по вычислениям, так и по дополнительным действиям?
Она тяжелая для моих глазок :) Хотя в сгенерированном коде там тоже все грустно будет.
-
2. Разработчик и постановщик задачи одно лицо. Когда тебе ставит задачу другой человек (обычно не знающий программирования), то сложность возрастает на порядки.
3. Практически отсутствует сопротивление среды (требования не меняются каждый день; нет нужды реагировать на вопли пользователей)
т.е. Оберон не считается, т.к. это тепличное растение.
Это не имеет отношения к Оберону, это особенности прикладной автоматизации... Хорошо известные.
Если автоматизатор - крупная компания, то она часто выделяет подразделение, которое занимается программированием "общего знаменателя" для своих проектов (библиотек, инструментов). И у этого подразделения будут тоже "тепличные условия".
А Оберон что вещь в себе? От кодеров для кодеров?
Хотя... наверно так и есть... (вот кстати почему она однопользовательская?)
Не будет там тепличных условий. Постановщик и разработчик один фиг будет о двух лицах практически в любой прикладной задаче. Чтобы закодить "общий знаменатель" нужен специалист по данной прикладной области, который и будет постановщиком задачи. (ну или нужно идти по пути alexus'a и вкуривать прикладуху самому..., а на это нужно дохера времени, коего в реальных задачах всегда мало)
Постановщик очень часто не может сформулировать на понятном кодеру языке чего он хочет. И кодер очень часто не имеет врожденного таланта расшифровки чужих мыслей. Очень часто постановщик проявляет моральную слабость и отвечает на вопрос, который он абсолютно не понял, функцией random(да, нет). По прошествии некоторого времени, когда он накопит достаточно маны и смелости, вы услышите ехидную речь о том, что вы дебил и все сделали не так. Начнутся перепостановки, изменение требований, ночной хардкодинг того, что нужно было сдать неделю назад.(а не редко по факту оно уже сдано официально) Нервы, недосып, конфликты....
А про циклы - какие там нах супер-формальные методы, коллега? Написать цикл аккуратно без выхода из середины - это супер-сложно? Легче наклепать и иметь 20% брака?
А чтобы написать цикл аккуратно нужно расписывать инварианты и доказывать правильность?
Вот info21 элементарные циклы пишет с доказательством, а я интуитивно в свое башке... И че? Результат то один. (хотя мне мои интуитивные больше нравятся :P)
На сложном цикле с большим количеством переменных меня интуиция подведет, а info21 допустит ошибку на бумаге. И что дальше? Или скажете бумага ошибок не пропускает?!
На действительно сложных циклах и я бумагу мараю, но только потому, что оно в мою оперативу не помещается. :)
И вообще я не понимаю откуда эта информация о проблемах с циклами у программистов. Вот не помню я у себя проблем с циклами. И у коллег не помню. (у студентов стажеров бывает, но это отсутствие опыта и только...) Ну чтобы вот сидеть, пялиться в цикл и не понимать почему он неправильно работает. Или чтобы там ошибки были частые в циклах. Нету такого. Вообще очень редко мозг включаю на циклах. Попадаются иногда нетривиальные, типа парсера над говноданными. Но это редко... Раз в пол года можно и помедитировать час-другой. Да и вообще стараюсь циклы сводить к простейшим вплоть до форычей. Пусть будет менее эффективно, зато любой идиот поймет. Иногда вместо красивой нетривиальной и смекалистой рекурсии сознательно пишу говнокод(в хорошем смысле), т.к. понимаю что над моим шедевром будет весь офис материться потом (а потом еще и стебаться :D)
-
Вот пример из жизни (захардкодил в пятницу на месте у клиента)
5 минут на изучение формата. 15 минут на кодинг.
Загрузили уже кучу данных. Ошибок пока не обнаружено.
Процедура ЗагрузитьCSV_1(Путь)
ТекстовыйФайл = Новый ТекстовыйДокумент;
ТекстовыйФайл.Прочитать(Путь);
Текст = ТекстовыйФайл.ПолучитьТекст();
Буфер = "";
МассивСтрок = Новый Массив;
МассивПоказаний = Неопределено;
Для Индекс = 1 По СтрДлина(Текст) Цикл
ТекСимвол = Сред(Текст, Индекс, 1);
Если ТекСимвол = "," Тогда
МассивПоказаний = Неопределено;
МассивСтрок.Добавить(Буфер);
Буфер = "";
ИначеЕсли ТекСимвол = ";" Тогда
Если МассивПоказаний = Неопределено Тогда
МассивПоказаний = Новый Массив;
МассивСтрок.Добавить(МассивПоказаний);
КонецЕсли;
МассивПоказаний.Добавить(Буфер);
Буфер = "";
ИначеЕсли ТекСимвол <> Символы.ПС Тогда
Буфер = Буфер + ТекСимвол;
КонецЕсли;
КонецЦикла;
Состояние = "Ищем баркод";
ЛицевойСчет = Справочники.ЛицевыеСчета.ПустаяСсылка();
Сумма = 0;
НомерСтроки = 0;
Сумма1 = 0; // в баркоде неправильная сумма
Для Каждого Элемент Из МассивСтрок Цикл
Если Состояние = "Ищем баркод" Тогда
Если Найти(Элемент, "W") > 0 Тогда
НомерСтроки = НомерСтроки + 1;
// опред л/с
Если ПолучитьДанныеБарКода(СокрЛП(Элемент), ЛицевойСчет, Сумма1, НомерСтроки) Тогда
Состояние = "Ищем сумму";
Иначе
Состояние = "Ищем баркод"
КонецЕсли;
КонецЕсли;
ИначеЕсли Состояние = "Ищем сумму" Тогда
Попытка
Сумма = Число(?(Элемент = "", "0", Элемент));
// добавляем строку
НоваяСтрока = Состав.Добавить();
НоваяСтрока.ЛицевойСчет = ЛицевойСчет;
НоваяСтрока.Сумма = Сумма / 100;
Состояние = "Ищем показания"
Исключение
Сообщить("Не удалось определить сумму");
Состояние = "Ищем баркод"
КонецПопытки;
ИначеЕсли Состояние = "Ищем показания" Тогда
Если ТипЗнч(Элемент) = Тип("Массив") Тогда
// собираем показания
СтрокаСообщения = ЛицевойСчет.Код + " - ";
Для Каждого Показание Из Элемент Цикл
СтрокаСообщения = СтрокаСообщения + Показание + "; ";
КонецЦикла;
Сообщить(СтрокаСообщения);
Состояние = "Ищем баркод"
КонецЕсли;
Иначе
ВызватьИсключение "Ошибка";
КонецЕсли;
КонецЦикла;
КонецПроцедуры
Формат тут не сложный, но дебильный (количество колонок плавает)
типа такого:
106798,5982144,3922588,034W0242071200352322108,36000,00188;00203;;;;
107139,5983300,153,3923490,034W0164061200940803042,50000,01085;01097;00070;00078;;;
106776,5987505,3926754,034W1199491000274242763,28000,00103;00117;00162;00181;;;
106783,5993445,3931435,034W0338781200376323156,40000,00150;00160;00083;00088;;;
107146,5995777,3933173,034W0129041200043922028,5000,00129;00132;;;;
-
Типичный while. А тяжёлая проверка уходит в подпрограмму.
i = 0;
while ((i < list->Count()) && (list->Items[i] != xxx))
{
i++;
}
if (i < list.Count())
{
printf('yep');
}
Такой код мне вапще не нравится -- снаружи цикла появляется совершенно ненужная там переменная i, все эти инварианты цикла в данном случае меня совершенно не интересуют -- цикл простейший, условие завершения очевидное -- список либо кончится, и тогда искомый элемент не найден, или же элемент будет найден, и что там со списком меня не интересует уже.
Найден-не найден -- вот что важно. Если этот факт завуалировать через всякие дополнительные "if (i < list.Count())" -- это, имхо, затруднит понимание сути кода.
-
Я повторюсь, это называется "культ карго" (http://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%BB%D1%8C%D1%82_%D0%BA%D0%B0%D1%80%D0%B3%D0%BE):
А я не раз повторял, что у Петра культ конкретного формального метода, без желания обсуждать семантику.
Я, кстати, могу предложить ему пойти и попробовать где-нибудь на 1 курсе рядолежащего ВУЗа обучить делать циклы именно на том, безусловно, высоком матем. уровне, на котором он это сам делает. А лучше в школе. А не на 2-3 курсе мат. факультетов. У меня не получилось - а поскольку я стараюсь оставлять в арсенале только такие методы, которым я представляю, как быстро научить. Отсюда то, что Вы называете "культом карго". Это способ привить базовую дисциплину, само альтернативное понимание программы (не как последовательности инструкций). Шаг в нужную сторону. И, кстати, этого шага для многих случаев оказывается более, чем достаточно, чтобы иметь надёжный результат.
-
все эти инварианты цикла в данном случае меня совершенно не интересуют -- цикл простейший, условие завершения очевидное -- список либо кончится, и тогда искомый элемент не найден, или же элемент будет найден, и что там со списком меня не интересует уже.
Простейший- не простейший, если вы откажетесь "гонять код в уме построчно", то для вас вариант с выходом из середины не просто будет лучше-хуже, а перестанет существовать. Поскольку проверить его правильность без мысленной прогонки нельзя, а от прогонки вы отказываетесь.
-
Простейший- не простейший, если вы откажетесь "гонять код в уме построчно", то для вас вариант с выходом из середины не просто будет лучше-хуже, а перестанет существовать. Поскольку проверить его правильность без мысленной прогонки нельзя, а от прогонки вы отказываетесь.
А зачем это нужно -- отказываться от прогонки в уме?
-
1)... делать циклы именно на том, безусловно, высоком матем. уровне, на котором он это сам делает.
2)... У меня не получилось...
1). НЕТ ТАМ МАТЕМАТИКИ.
См. http://oberspace.dyndns.org/index.php/topic,331.msg8778.html#msg8778
2). Не получилось потому, что надо сначала обучить себя :)
-
Простейший- не простейший, если вы откажетесь "гонять код в уме построчно", то для вас вариант с выходом из середины не просто будет лучше-хуже, а перестанет существовать. Поскольку проверить его правильность без мысленной прогонки нельзя, а от прогонки вы отказываетесь.
А зачем это нужно -- отказываться от прогонки в уме?
Согласен на все 100!
-
Это способ привить базовую дисциплину, само альтернативное понимание программы (не как последовательности инструкций). Шаг в нужную сторону.
Сори что вмешиваюсь, просто примечание:
По моему скромному опыту обучения кого-либо программированию могу сказать, что сложнее всего прививается именно понимание программы как последовательности действий. По умолчанию народ воспринимает текст программы целиком и сразу (свободно читает его как сверху-вниз, так и снизу вверх). Отсюда возникают проблемы с понимаением "почему оно выдает не то что ожидалось". Пока в отладчике (да-да, в пошаговом отладчике) не покажешь как РЕАЛЬНО оно работает (по шагам с тыканием пальцем в то как изменяются переменные и так далее), народ не воспринимает. Если этого не сделать, то народ через какое-то время научается просто имитировать понимание и отвечать так, как ты ожидаешь услышать ответ.
Не факт что это у всех так, но у многих мозг (особенно после школьной математики) закручен не имеперативно а сурово декларативно-функционально.
-
2). Не получилось потому, что надо сначала обучить себя :)
Пётр, покажите методику. Пойдите и попробуйте. На студентах СПО после 9 класса.
Я не делаю разницу между собой и студентами, в том смысле, что обычно не задействую в повседневном арсенале программирования те методы, которым невозможно обучить в течение полутора лет. Info21 с "паттернами" столкнулся с тем же самым. Мы можем сколько угодно читать Дейкстру и Гриса, но в первую очередь для того, чтобы спроецировать их в такие методы, которые можно объяснить доходчиво и доступно для использования всеми, желательно в первые полгода (потому что лично у меня во вторые полгода начинается ООП и элементы архитектуры).
Вы правы, если судить с позиции отдельно взятого интеллектуала. У нас срабатывают другие факторы, при которых просто нет иного пути, чем то, что Вы называете "культ карго". Врубитесь в ситуацию, в конце концов.
-
А зачем это нужно -- отказываться от прогонки в уме?
Чтобы получить уже в императивном программировании то, что Вы ищете в функциональном. Другой взгляд на составление алгоритма, на соединение его частей. Более высокоуровневый.
А то потом чего удивляться, что функциональщики г-ном поливают обычные языки. Они их, оказыватеся, "в уме по шагам исполняют". Голова перегревается у них от смены состояний :)
-
Сори что вмешиваюсь, просто примечание:
По моему скромному опыту обучения кого-либо программированию могу сказать, что сложнее всего прививается именно понимание программы как последовательности действий. По умолчанию народ воспринимает текст программы целиком и сразу (свободно читает его как сверху-вниз, так и снизу вверх). Отсюда возникают проблемы с понимаением "почему оно выдает не то что ожидалось".
с этим особых проблем нет - если делать грамотно и обучаемый обладает достаточным уровнем развития для понимания решаемой задачи
.Данный навык формируется на ранних этапах обучения - если его (это обучения) разбить на 3 этапа, то оно состоит из
1. Понимание задания, получение формального решения (лично я считаю что если по некоторому корректному набору начальных данных обучаемый не способен получить правильный конечный результат - переходить к основным этапам смысла нет)
2. Составление по нему алгоритма
3. Отображения его на целевой ЯП
- около 90 % УСТОЙЧИВЫХ ошибок приходится на 1 этап, на остальные где -то по 5% - причем на последнем УСТОЙЧИВО валятся самые слабые (для которых большие проблемы составляет 1 и 2 этапы)
-
Пётр, покажите методику.
... и т.п. ...
Неправильная позиция. Не просто пассивная, а агрессивно-оборонительная. Типа я должен убеждать, давать методики, врубаться в ситуацию.
Для вдохновления полистайте хотя бы книгу "Плэтт В. Информационная работа стратегической разведки. Основные принципы". Большего, правда, она не заслуживает.
-
А зачем это нужно -- отказываться от прогонки в уме?
Чтобы получить уже в императивном программировании то, что Вы ищете в функциональном. Другой взгляд на составление алгоритма, на соединение его частей. Более высокоуровневый.
А то потом чего удивляться, что функциональщики г-ном поливают обычные языки. Они их, оказыватеся, "в уме по шагам исполняют". Голова перегревается у них от смены состояний :)
Имхо, не стоит пытаться видеть в императивном коде декларативный стиль.
Кроме того, функциональные программы точно так же по шагам и в уме и исполняются, разницы особой нет -- просто изменяемое состояние не в каких-то глобальных переменных, а в параметрах функций...
Фишка ФП -- то что функции можно удобно принимать/передавать/создавать, а изменяемое или неизменяемое состояние тут не так важно...
-
Пётр, покажите методику.
... и т.п. ...
Неправильная позиция. Не просто пассивная, а агрессивно-оборонительная. Типа я должен убеждать, давать методики, врубаться в ситуацию.
Для вдохновления полистайте хотя бы книгу "Плэтт В. Информационная работа стратегической разведки. Основные принципы". Большего, правда, она не заслуживает.
Позиция ПРАВИЛЬНАЯ - если вы, Петр , утверждаете что методикой владеете и успешно приминяете, а оппонент ТОЖЕ считает что ею владеет (но не получает по ней ожидаемых результатов) - то естественно сравнить
1. Сами методики (вдруг с ними непонятки)
2. Обьекты обучения и задачи решаемые с помощью нее.
-
что касается вашего виденья, Петр - по ссылке которую вы не постеснялись здесь дать - я привел там вам еще пару инвариантов (по определению) и попросил прокомментировать их
- у вас КИШКА ТОНКА ОКАЗАЛАСЬ - ответ сводился "рассуждения долгие и нудные , у меня нет времени на это", кроме того, Албобин нашел у вас ошибку (это свидетельство что эта метода даже вам(ее адепту) не помогла ее избежать- если это так то НАХ. данная методика? и не е.-те другим мозги...
-
Албобин нашел ... ошибку
Справедливости ради. На настоящую добротную ошибку не тянет, просто интерпретации использованных "словов" могут быть разные, оттого и ощущение неточности возникает:)