Код для вычисления «медианы пяти» в C #

Question

Примечание: Пожалуйста, не интерпретируйте это как "домашнее задание". Это просто вещь, которую мне интересно знать:)

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

Каков наилучший способ реализации этой "медианы пяти с использованием 6 сравнений" в C #? Кажется, что все мои попытки приводят к неуклюжему коду :( Мне нужен хороший и читаемый код, хотя я все еще использую только 6 сравнений.

public double medianOfFive(double a, double b, double c, double d, double e){
    //
    // return median
    //
    return c;
}

Примечание: Я думаю, что я должен предоставить здесь и "алгоритм":

Я не смог четко объяснить алгоритм, как Azereal в своем посте на форуме. Поэтому я буду ссылаться на его пост здесь. От http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

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

1. Запустите сортировку слиянием с первыми 4 элементами и закажите каждую пару (2 сравнения)

2. Сравните два нижних из каждой пары и исключите самый нижний из возможности (3 сравнения)

3. Добавьте 5-е число, отведенное к номеру без пары, и сравните два (4 сравнения)

4. Сравните две младшие из двух новых пар и исключите младшую (5 сравнений)

5. Сравните единицу отдельно, младшую из последней пары и нижнюю число является медианой

   Возможная медиана находится в пределах parentesis

* * Тысяча сорок-девять (54321)

5: 4 3: 2 2 сравнения

(4 <5 2 <3 1) </p>

4: 2 3 сравнения

2 (4 <5 3 1) </p>

1: 3 4 сравнения

2 (4 <5 1 <3) </p>

4: 1 5 сравнений

1,2 (4 <5 3) </p>

4: 3 6 сравнений

1,2 (3) 4,5

Три медиана

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

double StageGenerator::MedianOfFive(double n1, double n2, double n3, double n4, double n5){
    double *a = &n1, *b = &n2, *c = &n3, *d = &n4, *e = &n5;
    double *tmp;

    // makes a < b and b < d
    if(*b < *a){
        tmp = a; a = b; b = tmp;
    }

    if(*d < *c){
        tmp = c; c = d; d = tmp;
    }

    // eleminate the lowest
    if(*c < *a){
        tmp = b; b = d; d = tmp; 
        c = a;
    }

    // gets e in
    a = e;

    // makes a < b and b < d
    if(*b < *a){
        tmp = a; a = b; b = tmp;
    }

    // eliminate another lowest
    // remaing: a,b,d
    if(*a < *c){
        tmp = b; b = d; d = tmp; 
        a = c;
    }

    if(*d < *a)
        return *d;
    else
        return *a;

} 

Это должно быть более компактно, не так ли?

EDIT:

Как указал @pablito в своем ответе. Встроенный List.Sort () не может выполнить это требование, поскольку он использует до 13 сравнений:]

Answer 1

Я нашел этот пост интересным, и в качестве упражнения я создал это, ТОЛЬКО 6 сравнений и НИЧЕГО:

static double MedianOfFive(double a, double b, double c, double d, double e)
{
    return b < a ? d < c ? b < d ? a < e ? a < d ? e < d ? e : d
                                                 : c < a ? c : a
                                         : e < d ? a < d ? a : d
                                                 : c < e ? c : e
                                 : c < e ? b < c ? a < c ? a : c
                                                 : e < b ? e : b
                                         : b < e ? a < e ? a : e
                                                 : c < b ? c : b
                         : b < c ? a < e ? a < c ? e < c ? e : c
                                                 : d < a ? d : a
                                         : e < c ? a < c ? a : c
                                                 : d < e ? d : e
                                 : d < e ? b < d ? a < d ? a : d
                                                 : e < b ? e : b
                                         : b < e ? a < e ? a : e
                                                 : d < b ? d : b
                 : d < c ? a < d ? b < e ? b < d ? e < d ? e : d
                                                 : c < b ? c : b
                                         : e < d ? b < d ? b : d
                                                 : c < e ? c : e
                                 : c < e ? a < c ? b < c ? b : c
                                                 : e < a ? e : a
                                         : a < e ? b < e ? b : e
                                                 : c < a ? c : a
                         : a < c ? b < e ? b < c ? e < c ? e : c
                                                 : d < b ? d : b
                                         : e < c ? b < c ? b : c
                                                 : d < e ? d : e
                                 : d < e ? a < d ? b < d ? b : d
                                                 : e < a ? e : a
                                         : a < e ? b < e ? b : e
                                                 : d < a ? d : a;
}

Answer 2

Это, в основном, просто выделение кода подкачки и сортировки из вашего примера C ++:

private static void Swap(ref double a, ref double b) {
    double t = a;
    a = b;
    b = t;
}

private static void Sort(ref double a, ref double b) {
    if (a > b) {
        double t = a;
        a = b;
        b = t;
    }
}

private static double MedianOfFive(double a, double b, double c, double d, double e){
    // makes a < b and c < d
    Sort(ref a, ref b);
    Sort(ref c, ref d);

    // eleminate the lowest
    if (c < a) {
        Swap(ref b, ref d);
        c = a;
    }

    // gets e in
    a = e;

    // makes a < b
    Sort(ref a, ref b);

    // eliminate another lowest
    // remaing: a,b,d
    if (a < c) {
        Swap(ref b, ref d);
        a = c;
    }

    return Math.Min(d, a);
}

Answer 3

Спасибо. Я знаю, что ваши сообщения довольно старые, но они были полезны для моей проблемы.

Мне нужен был способ для вычисления медианы 5 регистров SSE / AVX (4 поплавка / 8 поплавков одновременно или 2 удвоения / 4 удвоения одновременно):

• без условных переходов

• только с инструкциями min / max

Если функции min / max запрограммированы для скалярных регистров с условными переходами, мой код не является оптимальным с точки зрения сравнений. Но если функции min / max закодированы с помощью соответствующих инструкций ЦП, мой код очень эффективен, поскольку ЦПУ не выполняет условный переход при выполнении.

    template<class V> 
    inline V median(const V &a, const V &b, const V &c)
    {
      return max(min(a,b),min(c,max(a,b))); 
    } 

    template<class V> 
    inline V median(const V &a, const V &b, const V &c, const V &d, const V &e)
    {
      V f=max(min(a,b),min(c,d)); // discards lowest from first 4
      V g=min(max(a,b),max(c,d)); // discards biggest from first 4
      return median(e,f,g);
    } 

Answer 4

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

public double medianOfFive(double a, double b, double c, double d, double e){
    double median;
    // sort a and b
    if(a > b) // comparison # 1
    {
        double temp = a;
        a = b;
        b = temp;
    }

    // sort c and d
    if(c > d)  // comparison # 2
    {
        double temp = c;
        c = d;
        d = temp;
    }

    // replace the lower of a and c with e
    // because the lowest of the first four cannot be the median
    if(a < c) // comparison # 3
    {
        a = e;
        // re-sort a and b
        if(a > b) // comparison # 4
        {
            double temp = a;
            a = b;
            b = temp;
        }
    }
    else
    {
        c = e;
        // re-sort c and d
        if(c > d)  // comparison # 4
        {
            double temp = c;
            c = d;
            d = temp;
        }
    }

    // eliminate a or c, because the lowest
    // of the remaining four can't be the median either
    if(a < c) // comparison #5
    {
         if(b < c) // comparison #6
         {
              median = c;
         }
         else
         {
              median = b;
         }
    }
    else
    {
         if(d < a) // comparison #6
         {
              median = a;
         }
         else
         {
              median = d;
         }
    }
    return median;
}

Answer 5

Интересная тема здесь:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

Цитата из темы:

1. Поместите числа в массив.

2. Используйте три сравнения и перемешайте числа, чтобы a [1]

3. Если a [3]> a [2], то проблема довольно проста. Если a [2]

4. Итак, [3] a [4], то решение является меньшим из a [3] и a [5]. В противном случае решение является меньшим из a [2] и a [4].

Answer 6

Просто чтобы проверить, сколько сравнений:

    class MyComparable : IComparable
{

    public static int NumberOfComparisons = 0;

    public int NumPart { get; set; }

    #region IComparable Members

    public int CompareTo(object obj)
    {
        NumberOfComparisons++; //I know, not thread safe but just for the sample
        MyComparable mc = obj as MyComparable;
        if (mc == null)
            return -1;
        else
            return NumPart.CompareTo(mc.NumPart);
    }

    #endregion
}

class Program
{
    static void Main(string[] args)
    {
        List<MyComparable> list = new List<MyComparable>();
        list.Add(new MyComparable() { NumPart = 5 });
        list.Add(new MyComparable() { NumPart = 4 });
        list.Add(new MyComparable() { NumPart = 3 });
        list.Add(new MyComparable() { NumPart = 2 });
        list.Add(new MyComparable() { NumPart = 1 });
        list.Sort();


        Console.WriteLine(MyComparable.NumberOfComparisons);
    }
}

результат - 13.

Answer 7

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

Answer 8

Это должно сделать это

private Double medianofFive(double[] input)
{
    Double temp;
if (input[0] > input[1])//#1 - sort First and Second
{
    temp = input[0];
    input[0] = input[1];
    input[1] = temp;
}
if (input[2] > input[3])//#2 sort Third and Fourth
{
    temp = input[2];
    input[2] = input[3];
    input[3] = temp;
}

// replace the smaller of first and third with 5th, then sort
int smallerIndex = input[0] < input[2] ? 0 : 2;//#3
input[smallerIndex] = input[4];

//sort the new pair
if(input[smallerIndex]>input[smallerIndex+1])//#4
{
    temp = input[smallerIndex];
    input[smallerIndex] = input[smallerIndex+1];
    input[smallerIndex+1] = temp;
}

//compare the two smaller numbers
// then compare the smaller of the two's partner with larger of the two
// the smaller of THOSE two is the median
if (input[2] > input[0])
//#5
{
    temp = input[2] > input[1] ? input[1] : input[2];//#6
}
else
{
    temp = input[0] > input[3] ? input[3] : input[0];//#6
}
    return temp;
}

Answer 9

-- In Haskell the solution could look like

import Data.Function

median5By pred [a,b,c,d,e] = fst $ merge2 c' d' where
  merge2 = merge2By pred
  merge2By pred x y = if x `pred` y then (x,y) else (y,x)
  ((_,b'), de   ) = merge2By (pred `on` fst) (merge2 a  b) (merge2 d e)
  ((_,c'),(d',_)) = merge2By (pred `on` fst) (merge2 b' c)  de

main = print $ median5By (<) [2,5,4,1,3]

Answer 10

Интересно, сколько сравнений в выборке MSDN ...

public static double Median(this IEnumerable<double> source) {
        if (source.Count() == 0)  throw new InvalidOperationException("Cannot compute median for an empty set.");

        var sortedList = from number in source
                         orderby number
                         select number;

        int itemIndex = (int)sortedList.Count() / 2;

        if (sortedList.Count() % 2 == 0) {
            // Even number of items.
            return (sortedList.ElementAt(itemIndex) + sortedList.ElementAt(itemIndex - 1)) / 2; } else {
            // Odd number of items.
            return sortedList.ElementAt(itemIndex); }
    }