programming - c# coding style guide

Código para calcular "mediana de cinco" en C#

Question

Nota: no interprete esto como "pregunta de tarea". Esto es solo una cosa que tengo curiosidad por saber :)

La mediana de cinco se usa a veces como un ejercicio en el diseño de algoritmos y se sabe que es computable usando solo 6 comparaciones .

¿Cuál es la mejor manera de implementar esta "mediana de cinco utilizando 6 comparaciones" en C #? Todos mis intentos parecen dar como resultado un código incómodo :( Necesito un código agradable y legible mientras sigo usando solo 6 comparaciones.

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

Nota: Creo que debería proporcionar el "algoritmo" aquí también:

No pude explicar el algoritmo claramente como lo hizo Azereal en su publicación en el foro. Así que haré referencia a su publicación aquí. De http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

Bueno, me plantearon este problema en una de mis tareas y recurrí a este foro en busca de ayuda, pero no encontré ayuda. Eventualmente descubrí cómo hacerlo.

1. Comience un mergesort con los primeros 4 elementos y ordene cada par (2 comparaciones)

2. Compara los dos inferiores de cada par y elimina el más bajo de las posibilidades (3 comparaciones)

3. Agregue el quinto número reservado para el número sin un par y compare los dos (4 comparaciones)

4. Compara los dos pares más bajos y elimina el más bajo (5 comparaciones)

5. Compare el uno por sí mismo y el más bajo del último par y el número más bajo es la mediana

   La posible mediana está dentro de la parentesis

(54321)

5: 4 3: 2 2 comparaciones

(4 <5 2 <3 1)

4: 2 3 comparaciones

2 (4 <5 3 1)

1: 3 4 comparaciones

2 (4 <5 1 <3)

4: 1 5 comparaciones

1,2 (4 <5 3)

4: 3 6 comparaciones

1,2 (3) 4,5

Tres es la mediana

EDITAR: Como su pedido y para evitar recibir más votos negativos, este es el código de C ++ que escribí para encontrar la mediana de cinco. No importa es torpeza:

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;

} 

Debería ser más compacto, ¿no?

EDITAR:

Como @pablito señaló en su respuesta. El List.Sort integrado () no puede cumplir este requisito ya que usa hasta 13 comparaciones:]

Answer 1

Esto es bastante feo y podría usar algunas refactorizaciones, pero examina explícitamente todas las comparaciones y los intercambios para que pueda ver lo que está sucediendo.

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 2

Interesante cuántas comparaciones en MSDN muestra ...

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); }
    }

Answer 3

Solo para verificar cuántas comparaciones:

    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);
    }
}

el resultado es 13.

Answer 4

Esto debería hacerlo

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 5

Para completar, la pregunta es un caso específico de una red de clasificación , que Knuth ( Art of Computer Programming , vol 3) cubre en gran detalle. El artículo clásico de KE Batcher sobre el tema es breve y vale la pena leerlo.

Answer 6

Básicamente se trata de factorizar el código de intercambio y clasificación de tu ejemplo de 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 7

Encontré esta publicación interesante y como un ejercicio, creé esto que SOLAMENTE hace 6 comparaciones y NADA más:

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 8

Gracias. Sé que tus publicaciones son bastante antiguas, pero fue útil para mi problema.

Necesitaba una forma de calcular la mediana de 5 registros SSE / AVX (4 flotadores / 8 flotadores a la vez, o 2 dobles / 4 dobles a la vez):

• sin saltos condicionales

• solo con instrucciones min / max

Si las funciones min / max están programadas para registros escalares con saltos condicionales, mi código no es óptimo en términos de comparaciones. Pero si las funciones min / max están codificadas con las instrucciones correspondientes de la CPU, mi código es muy efectivo porque la CPU no realiza ningún salto condicional durante la ejecución.

    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 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

Un hilo interesante aquí:

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

Cita del hilo:

1. Pon los números en una matriz.

2. Utilice tres comparaciones y baraje los números para que a [1] <a [2], a [4] <a [5] y a [1] <a [4].

3. Si a [3]> a [2], entonces el problema es bastante fácil. Si a [2] <a [4], el valor mediano es el menor de un [3] y un [4]. Si no, el valor mediano es el menor de un [2] y un [5].

4. Entonces a [3] <a [2]. Si a [3]> a [4], entonces la solución es la menor de un [3] y un [5]. De lo contrario, la solución es la menor de un [2] y un [4].