Calculer la médiane en C#

Question

Je dois écrire une fonction qui acceptera un tableau de nombres décimaux et il trouvera la médiane.

Y at-il une fonction dans la bibliothèque mathématique .net?

Answer 1

Y a-t-il une fonction dans la bibliothèque mathématique .net?

n °

Il n'est pas difficile d'écrire votre propre bien. L'algorithme naïf trie le tableau et choisit le milieu (ou la moyenne des deux éléments intermédiaires). Cependant, cet algorithme est O(n log n) alors qu'il est possible de résoudre ce problème en O(n) temps. Vous voulez regarder selection algorithms pour obtenir un tel algorithme.

Answer 2

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

Doit faire l'affaire.

- EDIT -

Pour ceux qui veulent le plein monty, voici la solution complète, bref, pur (un tableau d'entrée non vide est supposé):

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

Merci Rafe, cela prend en compte les problèmes signalés par vos réponses.

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

On dirait que d'autres réponses utilisent le tri. Ce n'est pas optimal du point de vue des performances car cela prend O(n logn) fois. Il est possible de calculer la médiane en O(n) temps à la place. La version généralisée de ce problème est connue sous le nom de "statistiques d'ordre n", ce qui signifie que trouver un élément K dans un ensemble tel que n éléments inférieurs ou égaux à K et au repos sont plus grands ou égaux. élément dans l'ensemble (Note: Certains index d'utilisation de la littérature de 1 à N au lieu de 0 à N-1). La médiane est simplement (Count-1)/2 -ordonnée. Ci-dessous est le code adopté de Introduction aux algorithmes de Cormen et al, 3ème édition.

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

Quelques notes:

1. Ce code remplace la queue du code récursif de la version originale dans le livre pour boucle itérative.
2. Il élimine également la vérification supplémentaire inutile de la version originale lorsque start == end.
3. J'ai fourni deux versions de Median, une qui accepte IEnumerable et crée ensuite une liste. Si vous utilisez la version qui accepte IList, gardez à l'esprit qu'elle modifie l'ordre dans la liste.
4. Les méthodes ci-dessus calculent les statistiques médianes ou d'ordre i dans O(n)temps prévu. Si vous voulez O(n)pire temps de l'affaire puis il ya une technique pour utiliser la médiane de la médiane. Bien que cela améliore les performances des cas les plus défavorables, il dégrade le cas moyen car la constante O(n) est maintenant plus grande. Cependant, si vous calculiez la médiane principalement sur de très grandes données, alors sa valeur à regarder.
5. La méthode NthOrderStatistics permet de passer un générateur de nombres aléatoires qui serait ensuite utilisé pour choisir un pivot aléatoire pendant la partition. Ce n'est généralement pas nécessaire, sauf si vous savez que vos données ont certains modèles, de sorte que le dernier élément ne sera pas assez aléatoire ou si votre code est exposé à l'extérieur pour une exploitation ciblée.
6. La définition de la médiane est claire si vous avez un nombre impair d'éléments. C'est juste l'élément avec l'index (Count-1)/2 dans le tableau trié. Mais quand vous même nombre d'élément (Count-1)/2 n'est plus un entier et vous avez deux médianes: Médiane inférieure Math.Floor((Count-1)/2) et Math.Ceiling((Count-1)/2). Certains manuels utilisent la médiane inférieure comme «standard» tandis que d'autres proposent d'utiliser une moyenne de deux. Cette question devient particulièrement critique pour l'ensemble des 2 éléments. Le code ci-dessus renvoie la médiane inférieure. Si vous vouliez plutôt la moyenne du bas et du haut, vous devez appeler deux fois le code ci-dessus. Dans ce cas, assurez-vous de mesurer la performance de vos données pour décider si vous devez utiliser le code ci-dessus VS juste le tri direct.
7. Pour .net 4.5+, vous pouvez ajouter l'attribut MethodImplOptions.AggresiveInlining sur la méthode Swap<T> pour des performances légèrement améliorées.

Answer 5

est ici la mise en œuvre la plus rapide non sécuritaire, même algorithme avant, tiré de ce 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

Ci-dessous le code approprié: mais pas de manière très efficace. :(

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

bibliothèque NMath de CenterSpace fournit une fonction:

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

option, vous pouvez choisir d'utiliser NaNMedian (si votre tableau peut contenir des valeurs nulles), mais vous devrez convertir le tableau à un vecteur :

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

CenterSpace's NMath Library est pas libre, mais de nombreuses universités ont permis

Answer 8

Voici une version générique de la réponse 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

Un jour dans le futur. C'est je pense aussi simple que possible.

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 est une bibliothèque opensource qui offre une méthode de calcul du Median. Le paquet nuget est appelé MathNet.Numerics.

L'utilisation est assez simple:

using MathNet.Numerics.Statistics; 

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