Самый эффективный способ найти наибольшее из трех целых

Question

Ниже мой псевдокод.

function highest(i, j, k)
{
  if(i > j && i > k)
  {
    return i;
  }
  else if (j > k)
  {
    return j;
  }
  else
  {
    return k;
  }
}

Я думаю, что это работает, но разве это самый эффективный способ в C ++?

Answer 1

Чтобы найти самое большое, нужно взглянуть ровно на 3 дюйма, не больше, не меньше. Вы смотрите на 6 с 3 сравнениями. Вы должны быть в состоянии сделать это за 3 и 2 сравнения.

int ret = max(i,j);
ret = max(ret, k);
return ret;

Answer 2

псевдокод:

result = i
if j > result:
  result = j
if k > result:
  result = k
return result

Answer 3

Как насчет

return i > j? (i > k? i: k): (j > k? j: k);

два сравнения, без использования временных переменных стека ...

Answer 4

Ваш текущий метод: http://ideone.com/JZEqZTlj (0,40 с)

Решение Криса:

int ret = max(i,j);
ret = max(ret, k);
return ret;

http://ideone.com/hlnl7QZX (0,39 с)

Решение Игнасио Васкеса-Абрамса:

result = i;
if (j > result)
  result = j;
if (k > result)
  result = k;
return result;

http://ideone.com/JKbtkgXi (0,40 с)

А у Чарльза Бретаны:

return i > j? (i > k? i: k): (j > k? j: k);

http://ideone.com/kyl0SpUZ (0,40 с)

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

РЕДАКТИРОВАТЬ: Обновил тесты, оказалось, что он до сих пор оптимизировал его части. Надеюсь, это больше не так.

Answer 5

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

Я предпочитаю решение Игнасио:

result = i;
if (j > result)
  result = j;
if (k > result)
  result = k;
return result;

потому что на обычном современном оборудовании Intel компилятору будет чрезвычайно легко генерировать всего два сравнения и две cmov инструкции, которые создают меньшую нагрузку на I-кэш и меньшую нагрузку на предиктор ветвлений, чем условные переходы , (Кроме того, код понятен и легко читается.) Если вы используете x86-64, компилятор будет даже хранить все в регистрах.

Обратите внимание, что вам будет трудно внедрить этот код в программу , где ваш выбор имеет значение ...

Answer 6

Мне нравится исключать условные скачки как интеллектуальное упражнение.Имеет ли это какое-либо ощутимое влияние на производительность, я понятия не имею, хотя:)

#include <iostream>
#include <limits>

inline int max(int a, int b)
{
    int difference = a - b;
    int b_greater = difference >> std::numeric_limits<int>::digits;
    return a - (difference & b_greater);
}

int max(int a, int b, int c)
{
    return max(max(a, b), c);
}

int main()
{
    std::cout << max(1, 2, 3) << std::endl;
    std::cout << max(1, 3, 2) << std::endl;
    std::cout << max(2, 1, 3) << std::endl;
    std::cout << max(2, 3, 1) << std::endl;
    std::cout << max(3, 1, 2) << std::endl;
    std::cout << max(3, 2, 1) << std::endl;
}

Этот бит бит просто для удовольствия, решение cmov, вероятно, намного быстрее.

Answer 7

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

int maximum = max( max(i, j), k);

Answer 8

Есть предложение включить это в библиотеку C ++ под N2485. Предложение простое, поэтому я включил осмысленный код ниже. Очевидно, это предполагает вариадические шаблоны

template < typename T >
const T & max ( const T & a )
{ return a ; }

template < typename T , typename ... Args >
const T & max( const T & a , const T & b , const Args &... args )
{ return  max ( b > a ? b : a , args ...); }

Answer 9

#include<stdio.h>
int main()
{
    int a,b,c,d,e;
    scanf("%d %d %d",&a,&b,&c);
    d=(a+b+abs(a-b))/2;
    e=(d+c+abs(c-d))/2;
    printf("%d is Max\n",e);
    return 0;
}

Answer 10

Величайший из 3-х номеров

int greater = a>b ? (a>c? a:c) :(b>c ? b:c); 
System.out.println(greater);