Самый быстрый минимум максимум среди трех поплавков в C - PullRequest
Новая
       8

Самый быстрый минимум максимум среди трех поплавков в C

8 голосов
/ 15 ноября 2011

Я думаю, что вопрос довольно ясен: у меня три числа, у меня две функции, минимальная и максимальная.

Какие самые быстрые реализации?

Ответы [ 4 ]

18 голосов
/ 15 ноября 2011

Стандарт C (C99) обеспечивает функции fmaxf и fminf в стандартном заголовке C math.h .Я бы просто использовал его, чтобы найти наибольшее из трех чисел, а затем проверил, достаточно ли он быстр для ваших нужд: 

float max = fmaxf(a, fmaxf(b, c));
float min = fminf(a, fminf(b, c));
5 голосов
/ 15 ноября 2011

Наивное решение - использовать два сравнения для нахождения минимума и два сравнения для нахождения максимума.Это неоптимально, поскольку достаточно трех сравнений (псевдокод, возвращающий (min, max) кортеж, следует): 

function minmax(float a, float b, float c): (float, float)
begin
  boolean altb = (a < b);
  boolean bltc = (b < c);
  if altb and bltc then return (a, c);
  if not altb and not bltc then return (c, a);
  if altb then // Also: c <= b, so b is known to be max
  begin
    if a < c then return (a, b);
    return (c, b);
  end
  if bltc then // Also: b <= a, so b is known to be min
  begin
    if a < c then return (b, c);
    return (b, a);
  end
  // Unreachable.
end

(это написано, чтобы быть наиболее читабельным, а не минимизировать количество ветвей)

Это выполняет от 2 до 3 сравнений.Невозможно использовать только 2 сравнения, так как их 3!= 6 переупорядочений 3 поплавков и 2 сравнения могут различать только 4 различных.Это легко увидеть в дереве решений проблемы.

На практике следует полагаться на оптимизации, подобные этой, на компиляторе.

2 голосов
/ 15 ноября 2011

Мне очень понравился подход Адама Зальцмана, я переписал его на C, на этот раз тоже уменьшив количество ветвей (так что самое большее 3 сравнения и 3 ветви). 

struct Pair
{
    float min_value;
    float max_value;
};

struct Pair minmax(float a, float b, float c)
{
    /* truth table:
     * a<b b<c a<c
     *  T   T   *  => (a, c)
     *  T   F   T  => (a, b)
     *  T   F   F  => (c, b)
     *  F   T   T  => (b, c)
     *  F   T   F  => (b, a)      
     *  F   F   *  => (c, a)
     */
    if (a < b) {
        if (b < c) 
            return (struct Pair) {a, c};
        else {
            if (a < c)
                return (struct Pair) {a, b};
            else
                return (struct Pair) {c, b};
        }
    } else {
        if (b < c) {
            if (a < c)
                return (struct Pair) {b, c};
            else
                return (struct Pair) {b, a};
        } else
            return (struct Pair) {c, a};
    }
}

void foo()
{
    struct Pair result = minmax(1.0, 2.0, 3.0);
}

(сейчас это может перерасти в кодовый гольф ...)

2 голосов
/ 15 ноября 2011

Код, чтобы найти наибольшее из трех чисел. 

#includ<stdio.h>

void main()

{
    float a,b,c;
    printf("enter a,b,c:");
    scanf("%f%f%f",&a,&b,&c); 
    printf("Greatest no: %f"(a>b)?((a>c)?a:c):((c>b)?c:b)); 
}

Обратно логику, чтобы найти наименьшее:)

...