Oberon space
General Category => Общий раздел => Тема начата: ilovb от Ноябрь 22, 2013, 03:07:30 pm
-
Тема перекликается с http://oberspace.dyndns.org/index.php/topic,591.0.html
Яркий пример на тему "ниасилил while (и линейный поиск)"
Выдержка из http://kpolyakov.blogspot.ru/2012/10/break-break.html
Пример 5. Разработать функцию, которая определяет, если ли в квадратной матрице элемент, равный заданному значению.
Будем предполагать, что введен тип данных
type Matrix = array[1..N,1..N] of integer;
Тогда функцию можно написать так:
function Find(const A: Matrix; X: integer): boolean;
var i, j: integer;
begin
Result := True;
for i:=1 to N do
for j:=1 to N do
if A[i,j] = X then exit;
Result := False
end;
Здесь оператор exit фактически выполняет роль break для вложенного цикла. С формальной точки зрения у функции два выхода. В общем, «я своим ученикам никогда такое не зачту» — уже слышу я от учителей информатики.
А давайте подумаем, какие альтернативы? Можно вот так:
function Find(const A: Matrix; X: integer): Boolean;
var i, j: integer;
label finish;
begin
Result := True;
for i:=1 to N do
for j:=1 to N do
if A[i,j] = X then goto finish;
Result := False;
finish:
end;
Но тут вообще «криминал» — метка и goto! Хотя по сути ничего не изменилось, тот же выход из вложенного цикла.
Конечно, здесь можно использовать исключение:
function Find(const A: Matrix; X: integer): Boolean;
var i, j: integer;
begin
Result := False;
try
for i:=1 to N do
for j:=1 to N do
if A[i,j] = X then
raise Exception.Create('');
except
Result := True
end
end;
Но ведь это далеко не «исключительная ситуация», поэтому по смыслу исключения здесь всё-таки не особо уместны. Кроме того, нужно учитывать, что при обработке исключений выполняется большое число машинных команд, что снижает эффективность программы.
Любителей «чистого» структурного программирования наверняка устроит такой вариант решения:
function Find(A: Matrix; X: integer): Boolean;
var i, j: integer;
begin
Result := False;
for i:=1 to N do
for j:=1 to N do
if A[i,j] = X then Result := True
end;
Но, к сожалению, по эффективности он не может составить конкуренцию предыдущим, так как в любом случае рассматриваются все N2 элементов массива, даже если элемент A[1,1] равен X.
-
Яркий пример на тему "ниасилил while (и линейный поиск)"
И чего? :) Лично я предпочту пройтись по этой матрице std::find. Но если уж слишком много для этого писать (писатель матрицы не позаботился об итераторах), то тогда в отдельную функцию с двумя return.
Цикл Дейкстры напишу только если настроение поглумиться :)
-
Тут не нужен никакой цикл Дейкстры. Обычный лин.поиск. Просто инкремент нужно делать не в одном измерении, а в двух.
PROCEDURE Inc2d(VAR d1, d2: INTEGER);
BEGIN
INC(d2);
IF d2 = n THEN
d2 := 0;
INC(d1);
END;
END Inc2d;
i := 0; j := 0;
WHILE (i < n) & (m[i, j] # x) DO
Inc2d(i, j);
END;
IF i < n THEN
// нашли
END;
-
Тут не нужен никакой цикл Дейкстры. Обычный лин.поиск. Просто инкремент нужно делать не в одном измерении, а в двух.
Не, VAR-параметры это моветон. Тем более для индексов.
ИМХО, у тебя, собственно, и получился завуалированный ЦД.
-
Не, VAR-параметры это моветон. Тем более для индексов.
С каких это пор? :)
INC() тоже моветон?
-
ИМХО, у тебя, собственно, и получился завуалированный ЦД.
Думаю, что многие циклы "завуалированный ЦД" ;)
90 процентов чего угодно (http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BA%D0%BE%D0%BD_%D0%A1%D1%82%D0%B0%D1%80%D0%B4%D0%B6%D0%BE%D0%BD%D0%B0)
-
Не, VAR-параметры это моветон. Тем более для индексов.
С каких это пор? :)
С тех пор как я ознакомился с хаскелем :) Точно не помню, но примерно в то время пришло осознание, что результат должен возвращаться как результат, а не в виде изменяемых аргументов.
А до этого была просто неудовлетворенность существующим синтаксисом C++ (причем в ББ/обероне точно такая же проблема) - в точке вызова не видно, что аргументы передаются по ссылке и будут изменены.
INC() тоже моветон?
Да. ++ намного лучше ;) В крайнем случае i += 1 :)
P.S. NEW - тоже дурной. Запись p := NEW смотрится намного естественнее.
P.S.S. Не говоря о том, что не сильно оптимизирующий компилятор породит ужасный код для инкремента индексов из твоего примера.
-
в точке вызова не видно, что аргументы передаются по ссылке и будут изменены.
В C# это фикснули, но для меня было уже поздно :) Для меня, теперь испорченного хаскелем, возврат результата как результата все равно лучше.
-
Ну я пока функциональщиной не заболел. :) Так что воспринимаю нормально. Помечать не мешало бы, да.
В любом случае Inc2d написана только для иллюстрации схемы цикла.
-
Многомерные массивы в языке - моветон :-) Не было бы их, и проблемы не было бы.
-
Матрицы - это моветон. Не было бы их, и проблемы не было бы.
-
Чтобы не казалось, что я только других умею дерьмом поливать.
Пожалста: https://code.google.com/p/1c-toolkit/source/browse/lua/cf_tools/cf_inside.lua#108
Прекрасно помню почему так сделал - было лень писать while :(
-
i := 0; j := 0;
WHILE (i < n) & (m[i, j] # x) DO
Inc2d(i, j);
END;
IF i < n THEN
// нашли
END;
Не понимаю я такого паттерна:
i := 0;
while i < len(arr) and not p(arr[i]) do
i := i + 1
end;
if i < len(arr) then
-- нашли!
end;Всегда делаю так:
i := 0; found := false;
while i < len(arr) and not found do
if p(arr[i]) then
found := true
else
i := i + 1
end;
if found then
-- нашли!
end;
или так (учитывая что на паскалях я вапще-то не работаю лет 10):
bool found = false;
for (int i = 0; i < arr.Length && !found; i++)
{
if (p(arr[i])) found = true;
}
if (found)
{
// нашли!
}
-
Из той же оперы: http://ic.asf.ru/~/docs/cpp/cppd_ifstruct.htm
Хотя оператор goto как метод управления программой давно "впал в немилость", он порой оправдывает свое существование. Одним из таких особых случаев является выход из глубоко вложенной процедуры. Рассмотрим, например, следующий фрагмент программы.
int i, j, k;
int stop = 0;
for(i=0; i<100 && istop; i++) {
for(j=0; j<10 && istop; j+ + ) {
for(k=0; k<20; k++) {
// ...
if(something()) {
stop = 1;
break;
}
}
}
}
Переменная stop используется для отмены двух внешних циклов при условии возникновения некоторого программного события. Однако все же лучше достичь того же эффекта с помощью оператора goto.
int i, j, k;
for(i=0; i<100; i++) {
for(j=0; j<10; j + +) {
for(k=0; k<20; k++) {
// . ..
if(something()) {
goto done;
}
}
}
}
done: // ...
Как видите, используя оператор goto, можно обойтись без дополнительных затрат ресурсов, которые связаны с повторением проверки значения переменной stop в предыдущем варианте.
-
Не понимаю я такого паттерна:
вот здесь-то и пригодился бы цикл-паук
-
int i, j, k;
for(i=0; i<100; i++) {
for(j=0; j<10; j + +) {
for(k=0; k<20; k++) {
// . ..
if(something()) {
goto done;
}
}
}
}
done: // ...
Как видите, используя оператор goto, можно обойтись без дополнительных затрат ресурсов, которые связаны с повторением проверки значения переменной stop в предыдущем варианте.
В Аде для этого используется выход из именованного цикла:
outer_loop:
for i in (0..99) loop
for j in (0..9) loop
for k in (0..19) loop
-- ...
exit outer_loop when something();
end loop;
end loop;
end loop outer_loop;
-
Попытался найти вариант где без break никак нельзя.
Нашел это(Java):
int a=...;
int b=...;
int c=...;
m1:
for(int i=0; i<100; i++) {
int d = 0;
for(int j=0; j<100; j++) {
if ((a+i) % (b+j) = c) {
a = 3*a;
b = 4*i;
c = 2+j;
}
if (b*c % a == 0) {
break m1;
}
b++;
d = (a + b) % c;
if (a*b % с == 0) {
break;
}
}
if (d = 0) sout("yyy");
}
Как насчёт поупражняться в рефакторинге такого кода?
Про break и continue в циклах (http://www.rsdn.ru/forum/java/1432379.flat)
OK. Попробуем завернуть в линейный поиск.
Вникать в алгоритм не стал. Но на первый взгляд преобразуется так(Lua):
function calc(i, j, a, b, c)
if (a + i) % (b + j) == c then
a = 3 * a
b = 4 * i
c = 2 + j
end
return a, b, c
end
local i, j = 0, 0
a, b, c = calc(i, j, a, b, c)
while (i < 100) and (b * c % a ~= 0) do
b = b + 1
d = (a + b) % c
j = j + 1
if (j == 100) or (a * b % c == 0) then
j = 0
i = i + 1
if d == 0 then
print 'yyy'
end
d = 0
end
a, b, c = calc(i, j, a, b, c)
end
-
А я для себя вопрос выхода "из середины" закрыл. Если процедура должна быть максимально оптимизирована по быстродействию, и выход "из середины" действиельно даёт выигрыш в производительности, то я его использую без угрызений совести.
-
Если процедура должна быть максимально оптимизирована по быстродействию, и выход "из середины" действиельно даёт выигрыш в производительности
Вот как раз по этой причине я сомневаюсь в целесообразности запрета break :)
Не могу склониться полностью на сторону злаbreak только потому, что профит тут получается не алгоритмический, а машиннозависимый. В идеале этим должен оптимизатор заниматься, имхо.
ps Ручная оптимизация - это наверно единственная печенька стороны злаbreak
-
ps Ручная оптимизация - это наверно единственная печенька стороны злаbreak
Оберонщики всегда делали упор на ручные оптимизации, утверждая, что компилятор должен быть тупым как пробка.
Поэтому мне непонятен этот их дисонанс с брейком. Как говорится, "или крестик сними, или трусы надень"...
-
Ну можно оптимизировать в рамках структурного программирования, а можно грязно (break).
Думаю, что они как раз грязные оптимизации не признают. :)
-
Ну можно оптимизировать в рамках структурного программирования, а можно грязно (break).
Думаю, что они как раз грязные оптимизации не признают. :)
Ну и как структурно соптимизировать выход из тройного цикла? Особенно когда каждый такт на счету?
-
Никак
-
Хотя нужно потестить и посмотреть на сколько структурный вариант проиграет, и проиграет ли вообще.