На самом деле практический смысл есть. Мне иногда приходилось писать участки кода которые должны были выполнятся за строго определенное число тактов. Но вот засада — if если прямо, то 1 такт, а если направо то два. И выравнять порой сложно. Приходилось избавляться от if и делать «ветвление» хитрой математикой.

wwk Jul 26 2011 at 16:42

А не проще ли nop'ов натыкать нужное количество в более короткую ветвь?

DIHALT Jul 26 2011 at 16:57

Это первое что в голову нам пришло, но не получилось. Уже не помню подробностей ветвления, давно было, но изза цикла выровнять ветви нопами было нельзя. Вывернулись только за счет математики.

adontz Jul 25 2011 at 16:12

Ну вы же не сказали что надо чесать своё ухо своим же локтем :-)

xmdy Jul 25 2011 at 16:29

Усложним задачу — А вы пробовали чесать ухо локтем, когда у вас нет локтя?)

DasDemolisherDuck Jul 25 2011 at 19:35

Когда у вас нет уха.

freopen Jul 25 2011 at 20:41

Странное усложнение. Почесать свое ухо чужим локтем все еще можно…

mihaild Jul 25 2011 at 20:43

Когда у Вас вообще нет локтя. Ни своего, ни чужого.

switlle Jul 25 2011 at 20:52

А что от других тоже ничего не осталось? У Вас что там канибализм? 6-))

xmdy Jul 26 2011 at 01:33

Обычный, здоровый каннибализм, все локти и уши ушли на холодец) Ни чесать ничего, ни чесать нечем… Как раз, как в статье — ничего нет)

0lympian Jul 25 2011 at 18:43

Вы тоже попробовали это после прочтения комментария? ))

+31

olexandr17 Jul 25 2011 at 21:43

блин… я что один такой оказался? :)

dlinyj Jul 25 2011 at 18:56

почесал…

DIHALT Jul 26 2011 at 16:59

Треба видео! Или ты не свое почесал?

dlinyj Jul 27 2011 at 00:12

Локтём, своё. Локоть был не свой ;)

int03e Jul 25 2011 at 18:58

Только что попробовал. Начальство удивленно покосилось, но все ок- получилось.

ob1 Jul 25 2011 at 20:13

Нормальное исследование получилось. И вывод правильный, на мой взгляд.

Ofigenen Jul 26 2011 at 00:07

Сколько человек сейчас попробовали почесать ухо локтем?

SFx Jul 26 2011 at 09:50

одна знакомая еще умеет бить пяткой в грудь. девочки не такое могут))

-1

8bitjoey Jul 25 2011 at 16:04

В Mathematica можно попробовать, примерный код:

fact[0] := 1;

fact[n_?Positive] := n*fact[n - 1];

теперь fact от отрицательных не будет срабатывать, все остальное считается, но это все же читерство, ведь есть ?Positive.

Nakilon Jul 25 2011 at 20:22

То, что:

f[0] :=
f[...] :=
f[...] :=

– это уже условные переходы.

cblp Jul 25 2011 at 21:34

Это вы тут видите условные переходы, а я вижу расширение определения функции на разные множества.

Dragonizer Jul 25 2011 at 22:35

Это функциональный стиль задания, а не условные переходы.
Иными словами, мы задаем функцию на разных подмножествах области определения.
Тогда как в императивных языках if/else — именно условные переходы, так как связаны с порядком выполнения.

Так что логично ограничить условие задачи только императивными языками. Или потребовать отсутствия условных переходов уже в машинном коде.

mihaild Jul 25 2011 at 23:31

На ассемблере можно написать без cmp, используя косвенную адресацию. Но это, думаю, будет жульничеством.

DIHALT Jul 26 2011 at 11:11

Почему жульничество? Нет же сравнения, а то что у нас есть таблица переходов по результату как то и не в счет :))))

andrewsh Jul 25 2011 at 16:17

Не совсем по теме, но немного похожие вещи:
If we had no if
If we had no proc
If we had no variables

mihaild Jul 25 2011 at 16:28

Линейную программу, вычисляющую факториал, с использованием только логических и арифметических операций, написать невозможно. Для простоты положим, что в каждой строке может быть не более одной операции (ибо несколько операций можно легко разбить на несколько строк). Предположим также, что единственная изначально доступная константа — это «1» (любое другое число можно получить за конечное число строк).
Доказательство.
Пусть f(n, k) — самое большое число, вычислимое программой из k строк на входе n.
Лемма. Для любого k существует такое N_k, что f(n, k) <= n^(2^k) при всех n > N_k.
Доказательство (по индукции).
Для k = 1 — очевидно (разбор случаев: n*n, n*1, n+2, etc.).
Пусть доказано для k-1. Для k: после первых (k-1) строки в нашем распоряжении, по предположению индукции, есть число, не большее, чем n^(2^(k-1)) = x. Далее, опять разбор вариантов.

Поскольку n! растет быстрее, чем n^(2^k) для любого k, то, если наша программа состоит из K строк, при всех достаточно большин n она вычисляет число, меньшее n!..

Moonrise Jul 25 2011 at 16:45

Слишком уж сложно вы завернули :) Всё даже куда проще — для вычисления n! нужно O(n) операций, а в линейной программе число операций фиксировано. Заведомо найдётся число, для вычисления факториала которого потребуется больше, чем есть в программе. Вот если сказать, что n не превышает, скажем, 10, то ещё можно попробовать.

mihaild Jul 25 2011 at 16:47

Если n не превышает C, то все просто:)
Например, если n может быть 1,2,3:
answer = (n-2)*(n-3)/(1-2)/(1-3)*1 + (n-1)*(n-3)/(2-1)/(2-3)*2 + (n-1)*(n-2)/(3-1)/(3-2)*6

А что для вычисления факториала необходимо O(n) операций — совсем неочевидно.

AlMag Jul 25 2011 at 16:49

практически в любой задаче есть ограничения. Скажем, вычыслить n!.. 0<=n<=1000
поэтому в теории получается фиксированное количество операций. А если ограничений в задаче нету — тогда действительно невозможно

dime Jul 26 2011 at 15:08

Да легко. До этой вашей тысячи — по табличке, выше — по формуле Стирлинга, например. На больших аргументах она точна.

mihaild Jul 26 2011 at 16:55

Относительная погрешность формули Стирлинга стремится к нулю. Абсолютная — к бесконечности.

AlMag Jul 26 2011 at 17:27

Ну, во-первых, как уже здесь писали, абсолютная погрешность чисел Стирлинга стемится к бесконечности.
Во-вторых, я как раз к этому и веду, что при ограничениях можно как-то выкрутиться. Даже для тысячи, пускай не Вашим методом. А при их отсутствии всякие константы на размерность чего-либо теряют смысл.

mihaild Jul 26 2011 at 17:42

Ну почему? Если считать длинную арифметику «данной свыше» (например, мы работаем с RAM (Random-Access Machine)), то многие функции можно вычислить «линейной» программой даже без ограничений на вход.

mihaild Jul 25 2011 at 17:21

Упс… Я забыл про <<. С его помощью можно вычислить, например, 2^(n^2), что растет быстрее факториала.
Так что соображения по скорости роста не проходят.
Думаю, как доказать невыразимость факториала через арифметику, битовые операции и степень. Пока что не получается.

Moonrise Jul 25 2011 at 17:27

В любом случае за конечное число шагов можно получить только конечное число. Для конкретной программы максимальное такое число можно оценить, а поскольку факториал — растущая функция, дело в шляпе. На самом деле без условий даже длинную арифметику реализовать не получится, куда уж тут факториалу.

-2

mihaild Jul 25 2011 at 17:30

Ну тогда и программу умножения двух чисел реализовать нельзя.
Предположим, что у нас не совсем компьютер фон Неймана, а нечто, больше похожее на RAM. То есть длинная арифметика дана «свыше».
Растущую функцию можно вычислить легко. Например, f(x) = x — растущая функция:)
Можно даже вычислить функцию, растущую быстрее факториала (см. выше).

Moonrise Jul 26 2011 at 20:56

> Растущую функцию можно вычислить легко.
В оригинальном комменте предлагалось плясать от единицы. Я имел ввиду, что из неё сколь угодно большое число не построишь за конечное число операций.

mihaild Jul 27 2011 at 00:45

Оригинальный — это habrahabr.ru/blogs/crazydev/124878/#comment_4106402? В нем предлагалось плясать от единицы и входа.

lesha_penguin Jul 27 2011 at 02:27

Любую функцию. Потому что:
1) Внутри машины все является набором ноликов и единичек
2) Любое ~~число~~ набор бит можно отобразить в ~~другое число~~ другой набор бит с помощью арифметических и логический операций
3) Рекурсию-то никто не запрещал.

Вот вам ниже в доказательство пример сортировки массива без единной операции сравнения и без единного условного перехода:

habrahabr.ru/blogs/crazydev/124878/#comment_4111117

Могу, если сомневаетесь, «до кучи» еще запилить бинарный поиск без единного cmp/jcc.

P.S.: При всей кажущейся «бредовости» — автор статьи — просто молодец (сто плюсов ему в карму и тысячу счастливых лет жизни), побуждает пошевелить программистов давно неиспользованными извилинами в голове, не давая им заржаветь!

mihaild Jul 27 2011 at 02:29

Если разрешена рекурсия с ленивыми вычислениями — то можно реализовать МТ и дальше вычислять что угодно. Как уже много раз говорилось в этом топике.
Мое рассуждение было для программ, выполняющихся последовательно — строки выполняются в том же порядке, в котором написаны, каждая — один и только один раз. Т.е. по сути вычисление по формуле.

Moonrise Jul 27 2011 at 11:00

> Любой набор бит можно отобразить в другой набор бит с помощью арифметических и логический операций
Если вы имеете ввиду конечный набор бит, то да. Иначе, возникают вопросы вычислимости. Собственно, если ограничиться 32 битами, то функцию факториала (32 младших бита) можно вообще выписать аналитически без каких бы то ни было рекурсий.

Про реализацию ветвления через таблицу переходов и косвенную адресацию я понял. Собственно, это сродни тому, что я делал вначале (через хеш-таблицы), только выглядит уже не извращением, а практическим подходом.

Moonrise Jul 27 2011 at 10:52

Тогда, да, я неправильно рассуждал.

AlMag Jul 25 2011 at 17:31

нет, я думаю для факториала решение
есть
поэтому некоторые класс таких задач уже можно решать подобным образом

mihaild Jul 25 2011 at 17:35

Подобным образом можно решить вообще разрешимую задачу, т.к. можно реализовать машину Тьюринга.

amosk Jul 25 2011 at 22:09

Это вы сейчас себя сами ограничили когда сказали «с использованием только логических и арифметических операций».
В этом топике рассматривалось существенно менее строгое ограничение: «без ветвлений».
А вот оно легко реализуется — условия заменяем на косвенную адресацию, циклы — на рекурсию.

int fact(int n);

int fact1(int n)
{
    return 1;
}

int factN(int n)
{
    return fact(n - 1) * n;
}

typedef int (*fact_fn_t)(int);

fact_fn_t fact_fn[] = {fact1, factN};

int fact(int n)
{
    int i = (bool)(n - 1);
    return fact_fn[i](n);
}


int main(int argc, char* argv[]) 
{
    cout << fact(5) << endl;
}

mihaild Jul 25 2011 at 22:11

Таким образом можно реализовать МТ (выше писали, как именно), поэтому такая постановка задачи не слишком интересна.

Amper Jul 26 2011 at 03:27

def fac(n): 
    return not n or n * fac(n - 1)

mihaild Jul 26 2011 at 06:08

Эта программа нелинейна в том смысле, что выполнение идет непоследовательно (одна и та же строка может быть выполнена много раз).

Amper Jul 26 2011 at 06:14

Да, действительно, не обратил внимание на основное слово: «Линейно».
Зато это красиво )

mihaild Jul 26 2011 at 06:16

А еще это, если не ошибаюсь, не работает. Потому что это не С, и (not 0) — это True, а не 1. Так что 0! == True, при вычислении от больших аргументов — попытается умножить число на True, что вызовет исключение.
Если ошибаюсь — поправьте. Интерпретатора под рукой нет.

Amper Jul 26 2011 at 06:22

Да вроде всё ок:

mihaild Jul 26 2011 at 11:16

Да, в питоне bool таки приводится к int при арифметических операциях. Жаль, я был о нем лучшего мнения…

Amper Jul 26 2011 at 11:26

А что в этом плохого? Мне кажется вполне логичным поведением и им часто пользуются для проверки переменной на равенство нулю и для проверки пустоты строки или списка и т.д.

mihaild Jul 26 2011 at 11:35

А зачем для проверки пустоты приведение к int? «if l» вместо «if len(l) != 0» — действительно, писать удобно (хотя по мнению некоторых и непитонично). Но когда переменная будет то ли bool, то ли int — это ИМХО нехорошо.

Amper Jul 26 2011 at 11:45

А зачем для проверки пустоты приведение к int? «if l» вместо «if len(l) != 0» — действительно, писать удобно (хотя по мнению некоторых и непитонично).

Оно и не приводится к int, оно приводится к логическому типу. К тому же, кроме «питоничности» и лучшей читаемости, вариант "if l:" скорее всего ещё и быстрее.

Но когда переменная будет то ли bool, то ли int — это ИМХО нехорошо.

Добро пожаловать в язык с утиной типизацией ) Хотя вроде в любой момент понятно, какой тип имеет переменная и в чему он будет приведён: 0, "", [] — False, остальное — True

mihaild Jul 26 2011 at 12:03

>Да, в питоне bool таки приводится к int при арифметических операциях
>А что в этом плохого? Мне кажется вполне логичным поведением

Да, быстрее. На треть примерно. Неприятно, честно говоря.

Конечно, переменная может в разное время иметь разный тип. Но мне кажется не слишком хорошим стилем то, что тип переменной в одном и том же месте зависит от того, что было раньше.
И приведение int к bool в условии — это одно. А конструкция вида True * 3 — это совсем другое.

AlMag Jul 25 2011 at 16:31

поскольку в реализации циклов условные операторы должны использоваться — то любую задачу, где количество итераций не константно, невозможно решить без условных операторов? (например тот же факториал)

Moonrise Jul 25 2011 at 16:46

Да, вы правы. Если не дать себе поблажку и не ограничить это число итераций сверху. Например, для всех чисел, больших 10 выводить «очень много».

StanEgo Jul 25 2011 at 17:13

Неа. Любой цикл можно превратить в рекурсию. Это особенно хорошо знают, например, xslt-кодеры, у которых циклов нет вообще. Так что от количества итераций не зависит никак. Остается только одна проблема — определить момент выхода, т.е. надо вернуть константу X, если текущий индекс = минимальному и Y в противном случае. Остатком от деления и простейшими арифметическими операциями это сделать не сложно.

Moonrise Jul 25 2011 at 17:18

Хм, а как вы собираетесь решать, входить или НЕ входить в рекурсию? Если программа линейна, то варианта только два: входить всегда или не входить никогда.

StanEgo Jul 25 2011 at 17:23

Ниже пример, когда рекурсивный вызов заменяется на одну из лямбд, либо продолжающую рекурсию, либо завершающую ее. Определение нужной лямбды осуществляется через арифметические операции и чтение из памяти по смещению (в данном случае массив).

AlMag Jul 25 2011 at 17:26

int Rec(int n)

{

 int a = -isPos(n);

 return a&(n*Rec(n-1))+1-isPos(n);

}

isPos можно без ифов реализовать.

а так условных операторов вообще нету

Dyzzet Jul 25 2011 at 19:36

Рекурсия уйдет в бесконечный цикл!

mihaild Jul 25 2011 at 19:45

Если в языке реализованы ленивые вычисления, то не уйдет.

AlMag Jul 25 2011 at 17:20

да, действительно. можно использовать тот факт, что если
return (a&b);
и a равно нулю, то b не вычисляется. рекурсия спасает

Moonrise Jul 25 2011 at 17:31

Ну, строго говоря, ленивые операторы — тоже условные конструкции.

AlMag Jul 25 2011 at 17:39

тогда позовите сюда Вашого знакомого, интересно будет его аргументы послушать)

StanEgo Jul 25 2011 at 17:07

Запросто решается. Например, наспех сконструячил факториал на c# без условий.

AlMag Jul 25 2011 at 17:13

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

StanEgo Jul 25 2011 at 17:19

Это обыкновенный массив, к которому обращение идет по числовому индексу. Никакой связи с хеш-таблицами нет. Кстати, и хеш-таблицы можно реализовать без условий. Исходя из того, что в основе своей хэш-таблицы — выборка из массива по индексу, полученном при помощи хэш-функции. Потом, правда, при наличии коллизий могут начать перебирать с условием, но всегда можно сделать второй хэш и т.п. А для строк можно вообще сделать ассоциативный словарь деревом и тоже будет без условий.

mihaild Jul 25 2011 at 17:24

Насколько я понимаю, условный оператор скрыт в функции handlers. Где-то же должно решаться, брать из массива значение, или использовать x * Factorial(x — 1)?

AlMag Jul 25 2011 at 17:27

да, я говорил об этом

StanEgo Jul 25 2011 at 18:07

Это — условный оператор?

<assembler>

call [esi + смещение_в_массиве]

или

mov eax, [esi + смещение_в_массиве]

call eax

</assembler>

StanEgo Jul 25 2011 at 17:30

Нет там никаких скрытых условных операторов. _handlers — это просто линейный массив функций. Скажем на ассемблере это могло бы выглядеть как «call [esi + смещение_в_массиве]». Здесь же не усматривается, что атомарная процессорная инструкция x86 «call» содержит завуалированную инструкцию «cmp» :)

mihaild Jul 25 2011 at 17:34

А, прошу прощения, не разобрался с синтаксисом.
Безусловно, довольно остроумно. Но, мне кажется, в статье имелось в виду немного другое. «Нет инструкций, изменяющих направление программы» — это скорее значит, что команды выполняются в том же порядке, что и написаны. А у Вас все равно содержатся скачки.

StanEgo Jul 25 2011 at 17:45

У меня осуществляется обыкновенный вызов функции. Но адрес функции определяется в зависимости от текущего состояния. В ассемблере я даже мог бы сделать совсем линейной, просто меняя смещения для JMP, которые скакали бы только вперед. Скажем так, убираем синтаксический сахар и возвращаемся к машине Тьюринга. Надеюсь ТС не хотел сказать, что мы отказываемся от возможностей машины Тьюринга ))

mihaild Jul 25 2011 at 17:54

Программа для МТ целиком состоит из условных операторов:)
Поэтому, если мы хотим говорить о разрешимости задачи, ее надо уточнить. Если разрешить такого рода конструкции — то любую частично рекурсивную функцию можно вычислить таким образом — а значит, и любую вычислимую.

StanEgo Jul 25 2011 at 18:04

Переходы между состояниями в МТ можно делать с условиями, а можно и без :)
Опять же, если говорить процессорным языком, то МТ можно реализовать на ассемблере практически при помощи одних только MOV+JMP. Без CMP/JZ/JNZ и прочих условных переходов.

А вообще, все в итоге сводится к тому, что либо мы рассматриваем транзистор в CPU как условный оператор «если подан ток на базу, то...» :) Либо считаем, что любая задача может быть решена без применения условного оператора

mihaild Jul 25 2011 at 18:12

По определению, МТ задается множеством состояний, алфавитом и программой. Инструкции вида (состояние, символ) -> (состояние, символ, сдвиг) и есть условные операторы.
Но да, мы утыкаемся в вопрос, «что есть условные оператор».

StanEgo Jul 25 2011 at 18:43

Определенно. И опять же, правила МТ можно рассматривать как условия «если состояние такое, а текущий символ эдакий, то...», а можно рассматривать как примитивную индексную операцию:

смещение_правила_в_таблице_правил = текущее_состояние*длина_алфавита + текущий_символ;

новое_состояние = правила[смещение_правила_в_таблице_правил][0];

новый_символ = правила[смещение_правила_в_таблице_правил][1];

движение = правила[смещение_правила_в_таблице_правил][2];

У меня не поворачивается язык сказать, что здесь использованы условные операторы :)

mihaild Jul 25 2011 at 19:02

А у меня вполне поворачивается.
Я наконец придумал четкую формулировку.
То, что предлагает автор лучше называть не «вычислением без условных операторов», а «формулой».
Программа задает выход как некую функцию от входа. И автор приводит пример, когда эту функцию можно задать (бескванторной) формулой в арифметике. Факториал таким образом задать, по всей видимости, нельзя.

Flux Jul 26 2011 at 08:35

А можно еще и так.

Volshebnyi Jul 25 2011 at 16:34

Хм, даже самого заинтересовало. Вот не совсем честный, но красивый онлайнер на питоне:

{"cake":"Yummy!!!"}.get(raw_input(), "The cake is a lie :(")

Вообще, в питоне dict часто используется таким образом как альтернатива switch.

Volshebnyi Jul 25 2011 at 16:49

Да. самое главное забыл. Еще один онлайнер для Python 2.x:
print (lambda x:reduce(lambda x, y:x*y, [i for i in range(1, x)]))(raw_input()+1)

При нуле результат неправильный, но тогда код получается намного хуже =)

Volshebnyi Jul 25 2011 at 16:53

Вот я дурак, а! =) FIXED:

print (lambda x:reduce(lambda x, y:x*y, [i for i in range(1, max(x, 2))]))(int(raw_input())+1)

Ноль теперь работает как ожидалось.

AlMag Jul 25 2011 at 16:55

автор старается избежать использования условных операторов вообще, а не только в явном виде.
а у Вас их многовато)

Volshebnyi Jul 25 2011 at 17:07

Многовато? max(), еще что-то есть?

AlMag Jul 25 2011 at 17:15

например range еще

Volshebnyi Jul 25 2011 at 17:20

А где тут условие? Создаем list и вызывает для него __iter__() пока не возникнет исключение.

tFirma Jul 25 2011 at 17:21

Видимо условие где-то около «пока не возникнет исключение».

tFirma Jul 25 2011 at 16:48

<?php isCake(input) and print('Yummy, thanks!') or print('You are still lying to me!'); ?>
так нельзя?

AlMag Jul 25 2011 at 16:56

Нет. Это то же самое, что использовать конструкцию
printf("%s", isCake(s)?«Yummy»:«Lie!!»);
В основе все равно if

safright Jul 25 2011 at 17:00

return «epic fail» в классе-родителе
return «win» в классе-потомке
чего тут может быть непонятного в такой реализации?..

Moonrise Jul 25 2011 at 17:07

Идея то безусловно прозрачна и ясна. А конкретную реализацию не предложите?

AlexanderYastrebov Jul 25 2011 at 19:11

package ru.nullpointer.cake;

/**
 *
 * @author Alexander Yastrebov
 */
public class App {

    public static void main(String[] args) throws Exception {
        taste("pie");
        taste("cake");
        taste("cookie");
    }

    private static void taste(String s) {

        Confectionery c = new Confectionery();

        try {
            s = Character.toUpperCase(s.charAt(0)) + s.substring(1);
            Class clazz = Class.forName(App.class.getName() + "$" + s);
            c = (Confectionery) clazz.newInstance();
        } catch (Exception ex) {
        }

        c.taste();
    }

    static class Confectionery {

        protected void taste() {
            System.out.println("Not so tasty as I wish :(");
        }
    }

    static class Cake extends Confectionery {

        protected void taste() {
            System.out.println("Mmm, very tasty!");
        }
    }
}

Moonrise Jul 26 2011 at 20:45

Имеет право на существование, хотя мне кажется, что это не совсем то на самом деле, так как в основном эта программа полагается скорее на механизм исключений. Если позволите, можно отбросить в вашем коде всё лишнее и написать просто

public class App {

    public static void main(String[] args) {
        taste("pie");
        taste("cake");
        taste("cookie");
    }

    private static void taste(String s) {

        try {
            s = Character.toUpperCase(s.charAt(0)) + s.substring(1);
            Class.forName(App.class.getName() + "$" + s);
            System.out.println("Mmm, very tasty!");
        } catch (Exception ex) {
            System.out.println("Not so tasty as I wish :(");
        }
    }

    static class Cake { }
}

Идея с исключениями приходила мне в голову, но я её забраковал, как неуниверсальную. Да и это тоже в своём роде ветвление.

AlMag Jul 25 2011 at 17:08

есть желающие отсортировать массив дробных чисел без условных операторов?

zibada Jul 26 2011 at 00:25

сортирующая сеть.
компаратор можно сделать как a[i], a[j] = min(a[i], a[j]), max(a[i], a[j]), min и max без if-ов вполне реализуются, например так:

double min(double a, double b)
{
	double c = b - a;
	int less = -(*(long long *)(&c) >> 63);
	return (1 - less) * a + less * b;
}

AlMag Jul 26 2011 at 00:31

Да, я что-то думал, что сравнивать дробные числа сложнее, чем целые) а принцип остается тот же.

Dr_Logic Jul 25 2011 at 18:08

Один хрен все сводится к je или jne — а это уже условный переход, как не крути, без условий не написать программу на современной архитектуре.

Bodigrim Jul 25 2011 at 19:07

Да нет, можно выжить и на jmp. Если нам надо передать управление адресу a, если x=0, и адресу b, если x=1, то можно засунуть a и b в массив c и делать jmp на адрес c[x]. Помнится, Кнут где-то даже рекомендует такую технику для оптимизации условных переходов.

Dr_Logic Jul 25 2011 at 19:12

Интересно, спасибо. Но все равно, если честно, не могу отделаться от ощущения что топик о том как заменить шило на мыло. Даже в приведенном вами примере мы эмулируем логику интегральной схемы (процессора) программно.

Bodigrim Jul 25 2011 at 19:25

У автора топика это даже не шило на мыло. Заменить в высокоуровневом языке программирования условные переходы на еще более высокоуровневые конструкции из хеш-таблиц — редкостное извращение.

Dr_Logic Jul 25 2011 at 19:29

Да, согласен, чем более высок уровень абстракции языка тем еще более бесполезной кажется эта забава :) По сути речь идет о переформулировании исходников, так чтобы убрать из них ключевое слово if :)

ilynxy Jul 25 2011 at 21:06

Осталось только заметить, что косвенный переход по адресу в таблице по сути условный переход (и вообще адресация памяти это выбор с условием):
если x равно 0, вернуть содержимое ячейки с номером 0
если x равно 1, вернуть содержимое ячейки с номером 1
и т.п.

lesha_penguin Jul 27 2011 at 00:31

Вот Пример, как можно сделать сортировку массива без применения cmp/jcc (вчера вечером развлекался после работы):

/* Вызов: extern void sort_array(uint32_t *arr,uint32_t N); */
    .text
    .globl sort_array
sort_array:
    pushl %ebp
    movl %esp, %ebp
    pushl %edi
    pushl %esi
    pushl %ebx
    pushl $31
    pushl 12(%ebp)
    pushl 8(%ebp)
    call sort_array_asm_recursive
    addl $12,%esp
    popl %ebx
    popl %esi
    popl %edi
    popl %ebp
    ret
sort_array_asm_recursive:
    movl 12(%esp),%ecx
    movl 8(%esp),%eax
    decl %eax
    neg %eax
    shrl $31,%eax
    jmp *jump_tab3(,%eax,4)
go_sort_process:
    movl 4(%esp),%ebx
    xorl %eax,%eax
    movl 8(%esp),%edx
    decl %edx
go_sort_again:
    movl %eax,%esi
    subl %edx,%esi
    shrl $31,%esi
    jmp *jump_tab0(,%esi,4)
process_one:
    movl (%ebx,%eax,4),%esi
    shrl %cl,%esi
    andl $1,%esi
    shll $1,%esi
    movl (%ebx,%edx,4),%edi
    shrl %cl,%edi
    andl $1,%edi
    orl %edi,%esi
    jmp *jump_tab1(,%esi,4)
sw_j0:
    incl %eax
    jmp go_sort_again
sw_j1:
    incl %eax
    decl %edx
    jmp go_sort_again
sw_j2:
    movl  (%ebx,%eax,4),%esi
    xchgl (%ebx,%edx,4),%esi
    movl  %esi,(%ebx,%eax,4)
    incl %eax
    decl %edx
    jmp go_sort_again
sw_j3:
    decl %edx
    jmp go_sort_again
get_out_of_loop:
    movl  (%ebx,%eax,4),%esi
    shrl %cl,%esi
    andl $1,%esi
    xorl $1,%esi
    addl %esi,%eax
    decl %ecx
    movl %ecx,%esi
    shrl $31,%esi
    jmp *jump_tab2(,%esi,4)
recurs_go:
    movl 8(%esp),%esi
    subl %eax,%esi
    leal (%ebx,%eax,4),%edi
    pushl %ecx
    pushl %esi
    pushl %edi
    pushl %ecx
    pushl %eax
    pushl %ebx
    call sort_array_asm_recursive
    addl $12,%esp
    call sort_array_asm_recursive
    addl $12,%esp
recurs_end:
    ret
    jmp recurs_end
    .data
jump_tab0:
    .long get_out_of_loop
    .long process_one
jump_tab1:
    .long sw_j0
    .long sw_j1
    .long sw_j2
    .long sw_j3
jump_tab2:
    .long recurs_go
    .long recurs_end
jump_tab3:
    .long recurs_end
    .long go_sort_process

Как видно, все достаточно просто реализуется.

Другое дело, косвенные переходы «там где не надо» дают именно в данном конкретном случае неоправданный оверхед. (по скорости данная функция в своем таком виде я замерял примерно ~1.5 раза уступает квиксорту, в частности за счет этого неоправданного оверхеда а еще за счет неоптимизированной рекурсии (рекурсивно проще было сделать)).

Но во многих других случаях может получиться нехилый прирост к перфомансу за счет убраного бранчинга.

steck Jul 25 2011 at 18:09

Ну, смотря что считать условными операторами. Например в массиве индексацию можно не считать условным оператором, поскольку при простой реализации она решается путем простых операций (в отличии от словарей)
И тогда можно использовать логику на массивах функций:

например тот-же факториал:
f[1] = \x, n -> f[n+1 / n] (x*n, n-1)
f[2] = \x, n -> print x

var k = read
f[1] (1,k)

Bas1l Jul 25 2011 at 18:30

Вообще, мне кажется, что функциональные языки могут обходиться без условных конструкций. А поскольку императивные и функциональные языки эквивалентны (в том смысле, что любую императивную программу можно заменить функциональной, и наоборот), то сразу можно сказать, что любую программу можно переписать без условных конструкций. И без while/for. И без изменяемых переменных.

menchauser Jul 25 2011 at 19:10

И как они могут обходится без условных конструкций? Паттерн-матчинг не всесилен, а guards — это почти уже switch/case.

-1

Bas1l Jul 25 2011 at 20:05

На самом деле в F# условные конструкции реализуются через паттерн-матчинг (см Expert F#, стр 38). Кроме того, if/then/else в F#--это выражение, в отличие от императивных языков (http://msdn.microsoft.com/en-us/library/dd233231.aspx).

EvilBlueBeaver Jul 25 2011 at 22:35

паттерн-матчинг гораздо мощнее if-ов и всяких там switchcase-ов, что бы вы ни думали.

EvilBlueBeaver Jul 25 2011 at 22:34

Все-таки паттерн-матчинг это тоже некая условная конструкция. А с возможностью написания без циклов и условных переменных я соглашусь.

smileonl Jul 25 2011 at 18:51

Не претендую на оригинальность но

<?php
$word = 'cake';
$cake = 0;
$$word++;
$buff = array('The cake is a lie :(', 'Yummy!!!');
echo $buff[$cake];

mobilz Jul 25 2011 at 19:24

$$ рулит )

int03e Jul 25 2011 at 18:55

В алгоритм не вьезжал (конец рабочего дня), но разве на уровне асма там не будет всяких сmp и jmp'ов? Как бы мы не писали высокоуровневый код, это самообман скорее всего :-)

seriyPS Jul 25 2011 at 19:23

А в языках с паттерн-матчингом паттерн-матчинг считается за условную конструкцию?

Shark Jul 25 2011 at 20:08

Насколько я помню, паттерн-матчинг — это всего лишь syntactic sugar для условных конструкций, так что считаются.

diamant Jul 25 2011 at 19:39

>>которая будет радоваться, если на вход ей подать, например, слово «печенька», и огорчаться в противном случае;
set_error_handler(function(){echo 'bad';die;});
$f = array(
'cake' => function(){echo 'good';}
);
//$input=trim(fread(fopen(«php://input», «r»), 10));
$input=$_GET['input'];
$f[$input]();

-1

Hast Jul 25 2011 at 19:39

У меня только один вопрос — а зачем? В любом случае все библиотечные функции и классы реализованы с использованием условий, поэтому от них никак не уйти.

saterenko Jul 26 2011 at 11:00

Тема интересная. Например, при выборе баннера в крутилке, используется несколько десятков сравнений (в худшем случае) для каждого баннера. В таком нагромождении условных операторов предсказатель ветвлений будет давать сбои, что приведёт к промахам при работе с кешом, что скажется на производительности… В общем, в этом смысл есть, но всё хорошо в меру…

plushechnik Jul 25 2011 at 19:49

для шейдеров в GLS именно, что надо без условных переходов и именно такие конструкции

HomoErectus Jul 25 2011 at 20:02

факториал без условий, можно описать по формуле Стирлинга:

хотя наверняка при реализации корня или деления, или возведения в степень в библиотечных функциях будут использоваться условия. Но тем не менее можно и их заменить :))

mihaild Jul 25 2011 at 20:30

Только у формулы Стирлинга абсолютная погрешность стремится к бесконечности при больших n.

HomoErectus Jul 25 2011 at 20:55

Вы правы (как и автор топика чуть ниже), не совсем то

HomoErectus Jul 25 2011 at 20:55

поста

Bodigrim Jul 25 2011 at 20:32

Формула Стирлинга не позволяет вычислить значение факториала в точности, так что это не совсем то, что нужно.

bleykher Jul 25 2011 at 20:13

Можно попытаться «съесть» пирог из строки:
foreach (var trash in inString.Split(new[] {«cake»}, StringSplitOptions.RemoveEmptyEntries))
{
return «I can't eat that :(»;
}
return «Yummy!!!»;

хотя тут foreach — по сути if

Monca Jul 25 2011 at 20:24

Доказано (Э. Дейкстра), что любая структура управления, а следовательно, и реализуемые алгоритмы, могут быть функционально эквивалентно представлены суперпозицией трех простых структур управления, имеющих один вход и один выход: последовательного выполнения, ветвления по условию и цикла с предусловием.
Так что, слишком долго обсуждаете.

an24 Jul 25 2011 at 21:31

Наконец то. Хоть кто-то сослался на классиков. Я бы еще Вирта упомянул. Народ, все уже давно доказано.

mephisto Jul 25 2011 at 20:50

Забавно, много было решений на php, но так и не написали самое простое.

$word = "cake";
$results = array("The cake is a lie!", "Yummy!");
echo $results[$word];

mephisto Jul 25 2011 at 20:51

Простите идиота.

Решение выше было верным) тоже с ассоциативным массивом и с обработкой ошибки) у меня хрень вышла, еще и накосячил)

mephisto Jul 25 2011 at 20:52

Имеется ввиду вот это решение.

SLY_G Jul 25 2011 at 20:51

Способ № 482 на perl:

@yesno=('no', 'yes');
print $yesno[$ARGV[0]=~/cake/];

kellas Jul 25 2011 at 21:32

<?php 

$emotions = array( $_GET['eat'] => ' :( '); // на что угодно переданное - плохая реакция

$emotions['cookie'] = 'thank you'; // а за печеньку спасибо



print $emotions[$_GET['eat']];

?>

Часто храню настройки скриптов в php массивах, в которых и узаю такие вот условия. На практике конечно юзаю if для проверки на существование элементов, в основном во избежании notice'ов.

-1

skvot Jul 25 2011 at 23:01

vkontakte.ru/id21409443 суровая такая девочка

www.sexyz.ru/index.php?ukey=order_status&orderID=2792&code=YWxlbmtheWEtODZAbWFpbC5ydQ==&hash=8499c95c70129fea3f9696a40ebd38ae

-2

skvot Jul 25 2011 at 23:04

Блин, не в ту вкладку… Сорри…

OlegTar Jul 25 2011 at 23:22

тут было решение задачи сложения унарных чисел через цепи Маркова.
Видимо, и факториал можно.

vics001 Jul 25 2011 at 23:23

Вообще строго говоря в функциональном и логическом программировании нету if/else.
Для примера Пролог определение метапредиката if_then_else/3 без использования if (просто его нет в принципе нету :) ):
if_then_else(Condition, Then, Else) :- Condition, !, Then.

vics001 Jul 25 2011 at 23:49

if_then_else(Condition, Then, Else) :- Else.

А в чисто функциональном программировании можно определить boolean типы как функции (лямбда-выражения):
TRUE = .x.y x
FALSE = .x.y y
NOT = .x x FALSE TRUE

AND = .x.y x y FALSE
OR = .x.y x TRUE y

IF_THEN_ELSE = .cond.x.y cond x y

apangin Jul 26 2011 at 00:19

Превратить ненулевое число в 1 можно очень просто: (n | -n) >>> 31

alman Jul 26 2011 at 13:08

Спасибо! Как говорится: век живи — век учись. Благодаря предоставленной Вами формуле, мне удалось немного реабилитироваться. Странно, что хабраобщество обошло вниманием столь полезный комментарий.

Кстати, у Вас небольшая опечатка — лишняя угловая скобка, но это сущие пустяки по сравнению с идеей.

apangin Jul 26 2011 at 14:44

Она не лишняя :) В Java это беззнаковый сдвиг в отличие от знакового >>.
При >> мы получим 0 или -1, а при >>> 0 или 1.

AlMag Jul 26 2011 at 17:09

Превратить ненулевое 32-битное знаковое число в 1 можно предоставленым Вами способом

Moonrise Jul 26 2011 at 20:51

О, спасибо, запомню! Мне не удалось до такого додуматься.

GMM Jul 26 2011 at 01:06

А я прочитав заголовок думал что будет что-то о самомодификации кода, не угадал

alman Jul 26 2011 at 02:25

Один знакомый заявил мне, что любая программа может быть написана без использования if/else.

Условие задачи не запрещает использовать операторы while и for. Поэтому извращаемся:

int res;



for( res = strcmp(input, "cake"); res == 0; )

{

 puts("Yummy!!!");

// Здесь бы не помешал goto для избежания избыточной проверки, 

// но раз уж объявили goto вредным - кушаем так.

 break;

}



while( res != 0 )

{

 puts("The cake is a lie :(");

 break;

}

За такой код надо наказывать, но он без if/else.

На x86 ассемблере точно так же можно заменить cmp и jz/jnz на инструкцию loop. Пожалуй, это ещё больший изврат, чем вышеприведённый пример.

Более того:

System.out.println((char)(x*'s'));

^^ В библиотечных функциях никто так извращаться не будет. Посему без if/else программе не обойтись. Тут лишь можно поспорить на тему, является ли System.out частью программы или нет.

И наконец, даже на x86 ассемблере можно обойтись без cmp, jz/jnz. Я основательно забыл ассемблер, поэтому вместо кода предлагаю алгоритм.

0. Обнуляем регистр ebx
1. Устанавливаем esi на введённую строку
2. Устанавливаем edi на сравниваемый шаблон.
3. Загоняем в al код символа (для эстетов и любителей юникода ax или eax)
4. Вычитаем из al значение по адресу edi — соответственно изменяется флаг равенства и другие флаги.
5. Заносим регистр флагов в стек командой pushf
6. Берём значение из стека в регистр eax
7. Сдвигаем eax вправо, чтобы бит z попал в младший бит (я не помню, может быть он уже младший?)
8. Делаем «логическое И» регистра ax c единицей, чтобы сбросить все биты кроме младшего (после сдвига в него попал флаг z).
9. Инвертируем младший бит (нам нужно знать о несовпадении символов)
10. Делаем «логическое ИЛИ» с регистром ebx — в случае несовпадения в нём будет 1, иначе ноль.
11. Повторяем с шага 1 для каждого сравниваемого символа, но без цикла, чтобы не нарушить условие задачи. Иными словами — копипаста с шага 1.
12. В результате получаем в регистре ebx значение 0 при совпадении, или значение 1 при несовпадении.
13. Считаем разницу между переходом при совпадении строки и переходом при несовпадении.
14. Умножаем регистр ebx на разницу переходов, рассчитанную на предыдущем шаге.
15. Прибавляем к регистру ebx адрес перехода на ближайшую метку — в результате имеем адрес, соответствующий выполнению условия или адрес перехода при нарушении условия.
16. Я не помню, есть ли команда jmp [ebx], поэтому воспользуемся следующей последовательностью: push ebx; ret — кладём ebx на стек и «возвращаемся» на рассчитанный адрес.

Брр. ДА ВЕДЬ ЭТО ЖЕ ГНУСНОЕ ИЗВРАЩЕНИЕ! но без cmp и jz/jnz

-1

alman Jul 26 2011 at 02:37

упс. Простите, в пункте 11 копипаста с шага 3.

И ещё не помешает инкремент регистров esi и edi. Хотя, если склероз мне не изменяет, то можно писать и так:
mov al, [esi+1];
sub al, [edi+1]
и на каждой итерации ручками прописывать смещение относительно esi и edi. Ну это уже кто как привык.

alman Jul 26 2011 at 06:33

Хмм. Видать, люди не заценили «ассемблерный алгоритм». Что ж, признаю, что игра «pushf; pop ax» — не самый оптимальный вариант. apangin предложил гораздо более красивое решение.

#include "stdio.h" static char * cake_message = "cake"; const char * match_message = "Yummy!!!"; const char * error_message = "The cake is a lie :("; int test( char * str ) { int result; unsigned long * cake_ptr32, * arg_ptr32; unsigned long diff; char ch = str[4]; const char * result_message = match_message; // Длина входящей строки не более 4-байт result = (int) ((unsigned char) (str[4] | -str[4]) >> 7); // Сравниваем слова как 32-х битные значения cake_ptr32 = (unsigned long *) cake_message; arg_ptr32 = (unsigned long *) str; diff = *cake_ptr32 - *arg_ptr32; result |= (int) (( diff | -diff ) >> 31); result_message += result * (error_message - match_message); puts(result_message); return result; } int main(int argc, char * argv[]) { test("on"); test("cake"); test("cakecake"); return 0; } * This source code was highlighted with Source Code Highlighter.

Проверил этот пример в MSVC 2005 и gcc 4.1.2 — результат правильный.

Но что вы будете делать, если по условию надо ветвить код, а не подбирать строку?
Хотя… старые и добрые setjmp/longjmp никто не отменял. :)

Mirror Jul 26 2011 at 05:54

Понаворатили решений одно красочней другого.
А между тем, задачка легко решается простейшей регуляркой :)

mihaild Jul 26 2011 at 06:09

Регулярка принципиально содержит неявное условие.

Mirror Jul 26 2011 at 06:20

Вообще-то условие принципиально содержит постановка задачи: если, то, а если этак.

-2

mihaild Jul 26 2011 at 11:17

Поэтому наиболее адекватным уточнением мне кажется «задать формулой».

isden Jul 26 2011 at 09:29

Мне кажется, для Java тут в самый раз подошло бы использование Reflection API.
Т.е., например, имеем классы Cake и Pie. Затем, получаем на вход слово и делаем как-то вот так:

try {
Class c = Class.forName(word);
…
} catch (Exception e) {
…
}

При использовании слов на русском языке, можно брать хэш (и нужным классам давать соотв. имена). Если допускаются пробелы и прочие спецсимволы — заменять их на подчеркивание. Ну или вообще использовать хэши в любом случае.

Moonrise Jul 26 2011 at 20:53

Такое решение было предложено выше, см. habrahabr.ru/blogs/crazydev/124878/#comment_4106908

isden Jul 26 2011 at 10:31

Да, пока завтракал, пришла в голову еще идея использовать enum'ы вот таким образом:

public enum Opts {

Cake {
@Override public String getResult() {
return «It's a cake!»;
}
},

Pie {
@Override public String getResult() {
return «It's a pie!»;
}
};

public abstract String getResult();
}
…
try {
String result = Opts.valueof(word).getResult();
}…

tumikosha Mar 24 2016 at 19:08

Наверно банально, я на Python так делаю ;))
x=3
y=4
result= x == y and x or 0
print result
возвращает 0 если x не равно Y и положительное число если равны
или как вариант
result= x == y and True or False

Only those users with full accounts are able to leave comments. Log in, please.