varianza - Calcular la mediana en c#

mediana en netbeans

Question

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

¿Hay una función en la biblioteca matemática .net?

Answer 1

¿Hay una función en la biblioteca matemática .net?

No.

Aunque no es difícil escribir el tuyo. El algoritmo ingenuo ordena la matriz y elige 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 tiempo O(n) . Desea ver los algoritmos de selección para obtener tal algoritmo.

Answer 2

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

}

Answer 3

Algún día en el futuro. Esto es lo más simple posible.

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 4

Aquí está la implementación insegura más rápida, el mismo algoritmo anterior, 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 5

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 6

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

La biblioteca NMath de CenterSpace proporciona una función:

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

Opcionalmente, puede optar por usar NaNMedian (si su matriz puede contener valores nulos) pero necesitará convertir la matriz a un vector:

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

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

Answer 8

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

public static T Median<T>(this IEnumerable<T> 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" como lo describe ShitalShah.

Answer 9

Parece que otras respuestas están utilizando la clasificación. Eso no es óptimo desde el punto de vista del rendimiento porque lleva tiempo O(n logn) . Es posible calcular la mediana en tiempo O(n) lugar. 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 sea mayor o igual K. Por lo tanto, la estadística de orden 0 sería mínima elemento en el conjunto (Nota: algunas publicaciones utilizan el índice de 1 a N en lugar de 0 a N-1). La mediana es una estadística simple (Count-1)/2 .

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

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

Algunas notas:

1. Este código reemplaza el código recursivo de la versión original del libro en el ciclo iterativo.
2. También elimina la verificación adicional innecesaria de la versión original cuando inicio == final.
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 el tiempo esperado de O(n) . Si desea O(n) peor tiempo de caso , existe una técnica para usar la mediana de la mediana. Si bien esto mejoraría el peor desempeño del caso, degrada el caso promedio porque la constante en O(n) ahora es mayor. Sin embargo, si está 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. 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 se expone afuera para una 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 índice (Count-1)/2 en la matriz ordenada. Pero cuando el número par de elementos (Count-1)/2 ya no es un número entero y tiene dos medianas: Math.Floor((Count-1)/2) 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 cambio deseaba un promedio de más bajo y más alto, 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 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 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();

Answer 11

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

Debería hacer el truco.

- EDITAR -

Para aquellos que quieren el dinero completo, 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;
}