Calcular la mediana en C#

Question

Necesito escribir la función que aceptará un conjunto de decimales y encontrará la mediana.

¿Hay alguna función en la biblioteca .net Math?

Answer 1

¿Hay alguna función en la biblioteca .net Math?

Nº

No es difícil escribir su propio embargo. El algoritmo ingenuo ordena la matriz y selecciona los elementos medios (o el promedio de los dos medios). Sin embargo, este algoritmo es O(n log n) mientras que es posible resolver este problema en el tiempo O(n). Desea consultar selection algorithms para obtener dicho algoritmo.

Answer 2

decimal Median(decimal[] xs) { 
    Array.Sort(xs); 
    return xs[xs.Length/2]; 
} 

Debería hacer el truco.

- EDITAR -

Para aquellos que quieren Full Monty, aquí está la solución completa, definitiva, puro (se asume una matriz de entrada que no esté vacía):

decimal Median(decimal[] xs) { 
    var ys = xs.OrderBy(x => x).ToList(); 
    double mid = (ys.Count - 1)/2.0; 
    return (ys[(int)(mid)] + ys[(int)(mid + 0.5)])/2; 
} 

Answer 3

Gracias Rafe, esto tiene en cuenta los problemas que publicaron sus respondientes.

public static double GetMedian(double[] sourceNumbers) { 
     //Framework 2.0 version of this method. there is an easier way in F4   
     if (sourceNumbers == null || sourceNumbers.Length == 0) 
      throw new System.Exception("Median of empty array not defined."); 

     //make sure the list is sorted, but use a new array 
     double[] sortedPNumbers = (double[])sourceNumbers.Clone(); 
     Array.Sort(sortedPNumbers); 

     //get the median 
     int size = sortedPNumbers.Length; 
     int mid = size/2; 
     double median = (size % 2 != 0) ? (double)sortedPNumbers[mid] : ((double)sortedPNumbers[mid] + (double)sortedPNumbers[mid - 1])/2; 
     return median; 
    } 

Answer 4

Parece que hay otras respuestas utilizando la clasificación. Eso no es óptimo desde el punto de vista del rendimiento porque lleva O(n logn) tiempo. En su lugar, es posible calcular la mediana en el tiempo O(n). La versión generalizada de este problema se conoce como "estadísticas de orden n" lo que significa encontrar un elemento K en un conjunto de modo que tengamos n elementos más pequeños o iguales a K y el resto sean mayores o iguales K. Por lo tanto, la estadística de orden 0 sería mínima elemento en el conjunto (Nota: Algunos documentos usan índices de 1 a N en lugar de 0 a N-1). Median es simplemente (Count-1)/2 -orden estadístico.

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

/// <summary> 
/// 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 
/// </summary> 
private static int Partition<T>(this IList<T> list, int start, int end, Random rnd = null) where T : IComparable<T> 
{ 
    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; 
} 

/// <summary> 
/// 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 
/// </summary> 
public static T NthOrderStatistic<T>(this IList<T> list, int n, Random rnd = null) where T : IComparable<T> 
{ 
    return NthOrderStatistic(list, n, 0, list.Count - 1, rnd); 
} 
private static T NthOrderStatistic<T>(this IList<T> list, int n, int start, int end, Random rnd) where T : IComparable<T> 
{ 
    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<T>(this IList<T> 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; 
} 

/// <summary> 
/// Note: specified list would be mutated in the process. 
/// </summary> 
public static T Median<T>(this IList<T> list) where T : IComparable<T> 
{ 
    return list.NthOrderStatistic((list.Count - 1)/2); 
} 

public static double Median<T>(this IEnumerable<T> sequence, Func<T, double> getValue) 
{ 
    var list = sequence.Select(getValue).ToList(); 
    var mid = (list.Count - 1)/2; 
    return list.NthOrderStatistic(mid); 
} 

Pocas notas:

1. Este código sustituye a la cola de código recursivo de la versión original en el libro en un bucle iterativo.
2. También elimina el control adicional innecesario de la versión original cuando start == end.
3. He proporcionado 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 de i-order en O(n)tiempo esperado. Si quiere O(n)peor caso de tiempo, entonces hay una técnica para usar la mediana de la mediana. Si bien esto mejoraría el peor rendimiento del caso, degrada el caso promedio porque la constante en O(n) ahora es más grande. Sin embargo, si usted estaría calculando la mediana principalmente en datos muy grandes, entonces vale la pena mirar.
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. En general, esto no es necesario a menos que sepa que sus datos tienen ciertos patrones, de modo que el último elemento no será lo suficientemente aleatorio o si de alguna manera su código queda expuesto fuera para su explotación específica.
6. La definición de mediana es clara si tiene un número impar de elementos. Es solo el elemento con el índice (Count-1)/2 en una matriz ordenada. Pero cuando incluso el número del elemento (Count-1)/2 ya no es un número entero y usted tiene dos medianas: Baja mediana Math.Floor((Count-1)/2) y Math.Ceiling((Count-1)/2). Algunos libros de texto usan una mediana más baja 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 una mediana más baja. Si en lugar de eso quiere un promedio de más bajo y más alto, entonces necesita 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 para la clasificación directa.
7. Para .net 4.5+ puede agregar el atributo MethodImplOptions.AggresiveInlining en el método Swap<T> para un rendimiento ligeramente mejorado.

Answer 5

Aquí es la implementación más rápida insegura, mismo algoritmo antes, tomado de esta source

[MethodImpl(MethodImplOptions.AggressiveInlining)] 
    private static unsafe void SwapElements(int* p, int* q) 
    { 
     int temp = *p; 
     *p = *q; 
     *q = temp; 
    } 

    public static unsafe int Median(int[] arr, int n) 
    { 
     int middle, ll, hh; 

     int low = 0; int high = n - 1; int median = (low + high)/2; 
     fixed (int* arrptr = arr) 
     { 
      for (;;) 
      { 
       if (high <= low) 
        return arr[median]; 

       if (high == low + 1) 
       { 
        if (arr[low] > arr[high]) 
         SwapElements(arrptr + low, arrptr + high); 
        return arr[median]; 
       } 

       middle = (low + high)/2; 
       if (arr[middle] > arr[high]) 
        SwapElements(arrptr + middle, arrptr + high); 

       if (arr[low] > arr[high]) 
        SwapElements(arrptr + low, arrptr + high); 

       if (arr[middle] > arr[low]) 
        SwapElements(arrptr + middle, arrptr + low); 

       SwapElements(arrptr + middle, arrptr + low + 1); 

       ll = low + 1; 
       hh = high; 
       for (;;) 
       { 
        do ll++; while (arr[low] > arr[ll]); 
        do hh--; while (arr[hh] > arr[low]); 

        if (hh < ll) 
         break; 

        SwapElements(arrptr + ll, arrptr + hh); 
       } 

       SwapElements(arrptr + low, arrptr + hh); 

       if (hh <= median) 
        low = ll; 
       if (hh >= median) 
        high = hh - 1; 
      } 
     } 
    } 

Answer 6

A continuación código funciona, pero no de forma muy eficiente. :(

static void Main(String[] args) { 
     int n = Convert.ToInt32(Console.ReadLine());    
     int[] medList = new int[n]; 

     for (int x = 0; x < n; x++) 
      medList[x] = int.Parse(Console.ReadLine()); 

     //sort the input array: 
     //Array.Sort(medList);    
     for (int x = 0; x < n; x++) 
     { 
      double[] newArr = new double[x + 1]; 
      for (int y = 0; y <= x; y++) 
       newArr[y] = medList[y]; 

      Array.Sort(newArr); 
      int curInd = x + 1; 
      if (curInd % 2 == 0) //even 
      { 
       int mid = (x/2) <= 0 ? 0 : (newArr.Length/2); 
       if (mid > 1) mid--; 
       double median = (newArr[mid] + newArr[mid+1])/2; 
       Console.WriteLine("{0:F1}", median); 
      } 
      else //odd 
      { 
       int mid = (x/2) <= 0 ? 0 : (newArr.Length/2); 
       double median = newArr[mid]; 
       Console.WriteLine("{0:F1}", median); 
      } 
     } 

} 

Answer 7

biblioteca NMath de CenterSpace proporciona una función:

double[] values = new double[arraySize]; 
double median = NMathFunctions.Median(values); 

Opcionalmente se puede optar por utilizar NaNMedian (si la matriz puede contener valores nulos), pero tendrá que convertir la matriz de un vector :

double median = NMathFunctions.NaNMedian(new DoubleVector(values)); 

CenterSpace's NMath Library no es libre, pero muchas universidades tienen licencias

Answer 8

Aquí hay una versión genérica de la respuesta de Jason

/// <summary> 
    /// Gets the median value from an array 
    /// </summary> 
    /// <typeparam name="T">The array type</typeparam> 
    /// <param name="sourceArray">The source array</param> 
    /// <param name="cloneArray">If it doesn't matter if the source array is sorted, you can pass false to improve performance</param> 
    /// <returns></returns> 
    public static T GetMedian<T>(T[] sourceArray, bool cloneArray = true) where T : IComparable<T> 
    { 
     //Framework 2.0 version of this method. there is an easier way in F4   
     if (sourceArray == null || sourceArray.Length == 0) 
      throw new ArgumentException("Median of empty array not defined."); 

     //make sure the list is sorted, but use a new array 
     T[] sortedArray = cloneArray ? (T[])sourceArray.Clone() : sortedArray = sourceArray; 
     Array.Sort(sortedArray); 

     //get the median 
     int size = sortedArray.Length; 
     int mid = size/2; 
     if (size % 2 != 0) 
      return sortedArray[mid]; 

     dynamic value1 = sortedArray[mid]; 
     dynamic value2 = sortedArray[mid - 1]; 
     return (sortedArray[mid] + value2) * 0.5; 
    } 

Answer 9

Algún tiempo en el futuro. Esto es, creo, tan simple como puede ser.

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace Median 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      var mediaValue = 0.0; 
      var items = new[] { 1, 2, 3, 4,5 }; 
      var getLengthItems = items.Length; 
      Array.Sort(items); 
      if (getLengthItems % 2 == 0) 
      { 
       var firstValue = items[(items.Length/2) - 1]; 
       var secondValue = items[(items.Length/2)]; 
       mediaValue = (firstValue + secondValue)/2.0; 
      } 
      if (getLengthItems % 2 == 1) 
      { 
       mediaValue = items[(items.Length/2)]; 
      } 
      Console.WriteLine(mediaValue); 
      Console.WriteLine("Enter to Exit!"); 
      Console.ReadKey(); 
     } 
    } 
} 

Answer 10

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

El uso es bastante simple:

using MathNet.Numerics.Statistics; 

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