Calcular la mediana en C#

Nuestros desarrolladores estrellas han agotado sus depósitos de café, por su búsqueda noche y día por la respuesta, hasta que Natalia encontró la contestación en GitLab así que hoy la comparte aquí.

Solución:

Parece que otras respuestas están usando la clasificación. Eso no es óptimo desde el punto de vista del rendimiento porque requiere O(n logn) hora. Es posible calcular la mediana en O(n) tiempo en su lugar. La versión generalizada de este problema se conoce como “estadística de orden n”, lo que significa encontrar un elemento K en un conjunto tal que tengamos n elementos menores o iguales a K y el resto sea mayor o igual a K. Entonces, la estadística de orden 0 sería mínima elemento en el conjunto (Nota: alguna literatura usa índice de 1 a N en lugar de 0 a N-1). La mediana es simplemente (Count-1)/2-Estadístico de orden.

A continuación se muestra el código adoptado de Introducción a los algoritmos por Cormen et al, 3.ª edición.

/// 

/// Partitions the given list around a pivot element such that all elements on left of pivot are <= pivot
/// and the ones at thr right are > pivot. This method can be used for sorting, N-order statistics such as
/// as median finding algorithms.
/// Pivot is selected ranodmly if random number generator is supplied else its selected as last element in the list.
/// Reference: Introduction to Algorithms 3rd Edition, Corman et al, pp 171
/// 
private static int Partition(this IList list, int start, int end, Random rnd = null) where T : IComparable

    if (rnd != null)
        list.Swap(end, rnd.Next(start, end+1));

    var pivot = list[end];
    var lastLow = start - 1;
    for (var i = start; i < end; i++)
    
        if (list[i].CompareTo(pivot) <= 0)
            list.Swap(i, ++lastLow);
    
    list.Swap(end, ++lastLow);
    return lastLow;


/// 

/// Returns Nth smallest element from the list. Here n starts from 0 so that n=0 returns minimum, n=1 returns 2nd smallest element etc.
/// Note: specified list would be mutated in the process.
/// Reference: Introduction to Algorithms 3rd Edition, Corman et al, pp 216
/// 
public static T NthOrderStatistic(this IList list, int n, Random rnd = null) where T : IComparable

    return NthOrderStatistic(list, n, 0, list.Count - 1, rnd);

private static T NthOrderStatistic(this IList list, int n, int start, int end, Random rnd) where T : IComparable

    while (true)
    
        var pivotIndex = list.Partition(start, end, rnd);
        if (pivotIndex == n)
            return list[pivotIndex];

        if (n < pivotIndex)
            end = pivotIndex - 1;
        else
            start = pivotIndex + 1;
    


public static void Swap(this IList list, int i, int j)

    if (i==j)   //This check is not required but Partition function may make many calls so its for perf reason
        return;
    var temp = list[i];
    list[i] = list[j];
    list[j] = temp;


/// 

/// Note: specified list would be mutated in the process.
/// 
public static T Median(this IList list) where T : IComparable

    return list.NthOrderStatistic((list.Count - 1)/2);


public static double Median(this IEnumerable sequence, Func getValue)

    var list = sequence.Select(getValue).ToList();
    var mid = (list.Count - 1) / 2;
    return list.NthOrderStatistic(mid);

Algunas notas:

1. Este código reemplaza el código recursivo de cola de la versión original en el libro en un ciclo iterativo.
2. También elimina la verificación adicional innecesaria de la versión original cuando comienza == finaliza.
3. Proporcioné dos versiones de Median, una que acepta IEnumerable y luego crea una lista. Si usa la versión que acepta IList, tenga en cuenta que modifica el orden en la lista.
4. Los métodos anteriores calculan la mediana o cualquier estadística i-order en O(n)tiempo esperado. Si quieres O(n)el peor de los casos entonces hay una técnica para usar la mediana de la mediana. Si bien esto mejoraría el desempeño del caso peor, degrada el caso promedio porque constante en O(n) ahora es mas grande. Sin embargo, si estuviera calculando la mediana principalmente en datos muy grandes, entonces vale la pena mirarlo.
5. El método NthOrderStatistics permite pasar un generador de números aleatorios que luego se usaría para elegir un pivote aleatorio durante la partición. Por lo general, esto no es necesario a menos que sepa que sus datos tienen ciertos patrones para que el último elemento no sea lo suficientemente aleatorio o si de alguna manera su código está expuesto al exterior para una explotación dirigida.
6. La definición de mediana es clara si tiene un número impar de elementos. Es solo el elemento con índice. (Count-1)/2 en ordenado array. Pero cuando tienes un número par de elementos (Count-1)/2 ya no es un número entero y tiene dos medianas: Mediana inferior Math.Floor((Count-1)/2) y Math.Ceiling((Count-1)/2). Algunos libros de texto usan la mediana inferior como “estándar”, mientras que otros proponen usar un promedio de dos. Esta pregunta se vuelve particularmente crítica para el conjunto de 2 elementos. El código anterior devuelve la mediana inferior. Si desea en cambio un promedio de inferior y superior, debe llamar al código anterior dos veces. En ese caso, asegúrese de medir el rendimiento de sus datos para decidir si debe usar el código anterior VS solo clasificación directa.
7. Para .net 4.5+ puede agregar MethodImplOptions.AggressiveInlining attribute en Swap método para mejorar ligeramente el rendimiento.

Gracias Rafe, esto tiene en cuenta los problemas que publicaron tus respondedores.

public static double GetMedian(double[] sourceNumbers) 
        //Framework 2.0 version of this method. there is an easier way in F4        
        if (sourceNumbers == null 

Math.NET es una biblioteca de código abierto que ofrece un método para calcular la mediana. El paquete nuget se llama MathNet.Numerics.

El uso es bastante simple:

using MathNet.Numerics.Statistics;

IEnumerable data;
double median = data.Median();

Si conservas alguna desconfianza o disposición de acrecentar nuestro crónica te invitamos ejecutar una aclaración y con deseo lo ojearemos.

---

---

Utiliza Nuestro Buscador