Calcular la mediana en c #

Necesito escribir la función que aceptará una matriz de decimales y encontrará la mediana.

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

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

No.

Aunque no es difícil escribir el tuyo. 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 O(n) tiempo. Desea ver los algoritmos de selección para obtener dicho algoritmo.

Parece que otras respuestas están utilizando la clasificación. Eso no es óptimo desde el punto de vista del rendimiento porque toma el tiempo O(n logn) . 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 rest 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 -order estadístico.

A continuación se muestra el código adoptado de Introduction to Algorithms por Cormen et al, 3rd Edition .

 ///  /// 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 la cola de la versión original en el libro en el 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 orden i en O(n) tiempo esperado . Si quiere O(n) peor tiempo de caso, 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 mayor. 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 tienes un número impar de elementos. Es solo el elemento con índice (Count-1)/2 en array ordenado. Pero cuando incluso el número de elemento (Count-1)/2 ya no es un entero y usted tiene dos medianas: Lower 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 para obtener un rendimiento levemente mejorado.

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; } 
 decimal Median(decimal[] xs) { Array.Sort(xs); return xs[xs.Length / 2]; } 

Debería hacer el truco.

– EDITAR –

Para aquellos que quieran la monty completa, aquí está la solución completa, corta y pura (se supone una matriz de entrada no 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; } 

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

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

  ///  /// Gets the median value from an array ///  /// The array type /// The source array /// If it doesn't matter if the source array is sorted, you can pass false to improve performance ///  public static T GetMedian(T[] sourceArray, bool cloneArray = true) where T : IComparable { //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; } 

La biblioteca NMath de CenterSpace proporciona una función:

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

Opcionalmente, puede optar por utilizar NaNMedian (si su matriz puede contener valores nulos), pero deberá convertir la matriz en un vector:

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

La biblioteca NMath de CenterSpace no es gratuita, pero muchas universidades tienen licencias

Algún día 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(); } } } 

Aquí está la implementación insegura más rápida, el mismo algoritmo anterior, tomado de esta fuente

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

A continuación funciona el código: pero no de manera 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); } } } 

Mis 5 centavos (porque parece más sencillo / más simple y suficiente para listas cortas):

 public static T Median(this IEnumerable items) { var i = (int)Math.Ceiling((double)(items.Count() - 1) / 2); if (i >= 0) { var values = items.ToList(); values.Sort(); return values[i]; } return default(T); } 

PS usando “mediana más alta” según lo describe ShitalShah.