Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4]      все
 Re: максимум без if  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34387
andreymx
напомните, есть ли алгоритм вычисления максимума из двух чисел без if


вычислить разность двух чисел и поверить знак результата.
23 ноя 14, 09:51    [16891559]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6303
Вася Уткин,

Походу нашелся победитель с правильным решением :)
23 ноя 14, 12:54    [16891799]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Вася Уткин
Guest
Anatoly Moskovsky
Вася Уткин,

Походу нашелся победитель с правильным решением :)

Я только не на 100% уверен, всегда ли по стандарту в C/C++ выражение a<b обязано быть равно 0 или 1, или может принимать и другие значения?
23 ноя 14, 13:32    [16891834]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 54847
Блог
White Owl
Может вас смущает то что "ассемблером" называют и программу которая переводит из мнемоники в машинные кода? Но эта программа по существу и есть компилятор.

Нет, эта программа по существу не есть компилятор. Она есть по существу транслятор. Надеюсь, разницу объяснять не надо.
23 ноя 14, 13:39    [16891838]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6303
Вася Уткин
Я только не на 100% уверен, всегда ли по стандарту в C/C++ выражение a<b обязано быть равно 0 или 1, или может принимать и другие значения?

Да, обязано.

"a<b" имеет тип bool в С++ и _Bool в С
bool в С++ это нечисловой тип, который при приведении к числовому (в данном случае для индексации массива) принимает значения 0 или 1.
_Bool в С - это числовой тип который принимает значения 0 или 1.
23 ноя 14, 13:53    [16891866]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Вася Уткин
Guest
Anatoly Moskovsky
Вася Уткин
Я только не на 100% уверен, всегда ли по стандарту в C/C++ выражение a<b обязано быть равно 0 или 1, или может принимать и другие значения?

Да, обязано.

"a<b" имеет тип bool в С++ и _Bool в С
bool в С++ это нечисловой тип, который при приведении к числовому (в данном случае для индексации массива) принимает значения 0 или 1.
_Bool в С - это числовой тип который принимает значения 0 или 1.

Значит я угадал :)
Но обращение к кэшу L1 все равно будет дольше, чем переходы jg/jl, так что с практической точки зрения это мало имеет смысла. В обоих случаях в конвейере не получится внеочередное выполнение команд завязанных на результат такого сравнения - только в случае с массивом потеряем ещё несколько тактов на обмен с L1.

А других вариантов решения не знаете случайно?
23 ноя 14, 14:15    [16891923]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Вася Уткин,

ну, например, из той же серии: a + (b-a) and (ord(a>b) - 1)
23 ноя 14, 14:49    [16892004]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Вася Уткин
Guest
Aleksandr Sharahov
Вася Уткин,

ну, например, из той же серии: a + (b-a) and (ord(a>b) - 1)

А что такое ord? :)


Получается что-то типа:
http://ideone.com/1zCiYa
#include <iostream>
#include <cstdlib>
using namespace std;

inline constexpr int func(int a, int b) {
	return a + ((b-a) & ((unsigned)(a>b) - 1));
}
 

int main() {
	
	cout << func(5, 4);
	
	cout << endl << func(rand()%10, rand()%10);
	
	// your code goes here
	return 0;
}


Причем, 1-й раз в compile-time отработает, даже в C++11(не 14), а второй раз в run-time без jump-ов.
23 ноя 14, 17:59    [16892548]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6303
Вася Уткин,

Сорри, приз переходит к Aleksandr Sharahov :)
24 ноя 14, 00:38    [16893980]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
Anatoly Moskovsky
Вася Уткин,

Походу нашелся победитель с правильным решением :)


нет, там есть сравнение, причём явное.

Anatoly Moskovsky

Сорри, приз переходит к Aleksandr Sharahov :)

а знак больше это не if разве ?


Правильно решение было у Дмитрия (Dima_T) и у меня. Только в этих двух решения не содержался явный if (и знаки больше меньше etc)
24 ноя 14, 01:48    [16894078]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6303
SashaMercury
а знак больше это не if разве ?

Нет конечно. Там же нет ветвления.
24 ноя 14, 06:49    [16894226]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6303
SashaMercury
нет, там есть сравнение, причём явное.

Правильно решение было у Дмитрия (Dima_T) и у меня. Только в этих двух решения не содержался явный if (и знаки больше меньше etc)

Поясню. Сравнение - это просто вычитание, а вовсе не if где требуется проверка на 0 и условный переход.
Таким образом в коде который предложил Aleksandr Sharahov есть операции "-", "+", "&".
А в вашем коде есть в разных его вариантах были операция * и даже % которые медленнее на порядки.

Если сравнивать алгоритмы по скорости выполнения (а других причин для такого идиотского условия задачи нет) то самый быстрый будет код от Aleksandr Sharahov.
24 ноя 14, 07:07    [16894230]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
SS
miksoft
Придумать-то можно, но зачем?

Псевдокод:
int max(int a, int b)
(
  t[0]=a;
  t[1]=b;
  return a[sign(sign(b-a)+1)];
}
sign можно реализовать без if, например, сдвигами и бинарными операциями.


тогда уже
 a*sign[a-b]+b*(1-sign[a-b]);

так читабельней.


Чем тогда плох этот пример(приводил его намного раньше) ? Выше псевдокод и использованием нотации Айверсона, присутствующей в Си/С++ по умолчанию, вот код на С++.
int max=a*(a>b)+b*(1-(a>b));
24 ноя 14, 07:16    [16894234]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
Anatoly Moskovsky,

не знал что операция сравнения это разность.
Но тем не менее, позже был показан вариант включающий только & >> и +, без умножения и %
24 ноя 14, 07:24    [16894237]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6303
SashaMercury
Чем тогда плох этот пример

Я не говорю что он плох. Я говорю что есть лучше :)
24 ноя 14, 07:47    [16894255]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
Anatoly Moskovsky,
кстати, в этом примере, умножение смело можно заменить на побитовое умножение &

int t=a>b;
nt max=a&t+b&(1-t);


мне эти ord непонятны, поверю вам, лучше так лучше :)
24 ноя 14, 07:58    [16894264]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6303
SashaMercury
мне эти ord непонятны, поверю вам, лучше так лучше :)

Не надо мне верить.
Я же не проверял экспериментом :)

А ord это просто приведение типа к числу.
24 ноя 14, 08:41    [16894335]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Barlone
Member

Откуда:
Сообщений: 1016
Развели тут длинное обсуждение, а при этом современный компилятор сгенерирует код для такого "if(a) b=c" без условных переходов, используя conditional move
24 ноя 14, 09:12    [16894416]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
SashaMercury
Anatoly Moskovsky,
кстати, в этом примере, умножение смело можно заменить на побитовое умножение &

int t=a>b;
nt max=a&t+b&(1-t);


мне эти ord непонятны, поверю вам, лучше так лучше :)

Это из Паскалей. ИМХО.

Автор некисло вбросил навоза на реактивную турбину. Он в сабже не указал язык
программирования. Перечислил какой-то сомнительный список операций (или функций)
или макросов типа and or xor.

Вот мы и крутимся то в ассемблер то в С++ то в математику.

О базисах и минимизации я уже писал. Так что добавить нечего.
24 ноя 14, 12:25    [16895654]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Гость_11111
Guest
Не думаю, что автору было нужно узнать максимум любых двух чисел. Наверное, было достаточно и для положительных. Потому

def f(a, b):
c = - ((a % b - a) // a)
return c * a + (1 - c) * b

Для произвольных чисел алгоритм не подойдет, но думаю двигаться нужно в этом направлении, так как такие задачки часто задают школьникам на "подумать" прежде, чем рассказать о if и т.п.

К примеру

http://informatics.mccme.ru/mod/statements/view3.php?id=2296&chapterid=2958
14 авг 15, 22:16    [18020493]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
Anatoly Moskovsky
Вася Уткин,

Сорри, приз переходит к Aleksandr Sharahov :)


Всё-таки нет. Правильных решений на этих 4х страницах практически нет(в том числе и мое первое рассуждение содержит ошибку)
8 авг 16, 14:22    [19515825]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: максимум без if  [new]
jksfj23jk
Member

Откуда:
Сообщений: 1
на Python 3.4.2
a = int(input())
b = int(input())
r= a * (a // b)
rr = b * (b // a)
rrr = int((r + rr) / (a//b + b//a))
print(rrr)
18 окт 18, 01:58    [21707297]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Лысый дядька
Member

Откуда:
Сообщений: 181
jksfj23jk
на Python 3.4.2


max = lambda x, y: (x,0,y)[(y-x)//abs(y-x)+1]
20 окт 18, 13:35    [21709741]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4]      все
Все форумы / Программирование Ответить