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