Il semble que les autres réponses utilisent le tri. Ce n'est pas optimal du point de vue des performances car il faut O(n logn) temps. 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 "statistique d'ordre n", ce qui signifie qu'il faut trouver un élément K dans un ensemble tel que nous avons n éléments inférieurs ou égaux à K et le reste est supérieur ou égal à K. Ainsi, la statistique d'ordre 0 serait l'élément minimal dans l'ensemble (Remarque : certains ouvrages utilisent l'indice de 1 à N au lieu de 0 à N-1). La médiane est simplement (Count-1)/2 -statistique d'ordre.
Voici le code adopté à partir de Introduction aux algorithmes par Cormen et al, 3e é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 :
- Ce code remplace le code récursif de la version originale du livre par une boucle itérative.
- Il élimine également la vérification supplémentaire inutile de la version originale lorsque le début==la fin.
- 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.
- Les méthodes ci-dessus calculent la médiane ou n'importe quelle statistique d'ordre i en
O(n) temps prévu . Si vous voulez O(n) temps dans le pire des cas alors il existe une technique pour utiliser la médiane de la médiane. Bien que cette technique améliore les performances dans le pire des cas, elle dégrade les performances dans le cas moyen, car la constante en O(n) est maintenant plus grande. Cependant, si vous calculez la médiane principalement sur de très grandes données, cela vaut la peine de l'examiner.
- La méthode NthOrderStatistics permet de passer un générateur de nombres aléatoires qui sera ensuite utilisé pour choisir un pivot aléatoire lors de la partition. Cela n'est généralement pas nécessaire, sauf si vous savez que vos données présentent certains modèles, de sorte que le dernier élément ne sera pas suffisamment aléatoire, ou si votre code est exposé à l'extérieur pour une exploitation ciblée.
- La définition de la médiane est claire si le nombre d'éléments est impair. C'est juste l'élément avec l'indice
(Count-1)/2 dans un tableau trié. Mais lorsque vous avez un nombre pair d'éléments (Count-1)/2 n'est plus un nombre entier et vous avez deux médianes : La médiane inférieure Math.Floor((Count-1)/2) y Math.Ceiling((Count-1)/2) . Certains manuels utilisent la médiane inférieure comme "norme" tandis que d'autres proposent d'utiliser la moyenne des deux. Cette question devient particulièrement critique pour les ensembles de 2 éléments. Le code ci-dessus renvoie la médiane inférieure. Si vous voulez plutôt la moyenne de la médiane inférieure et supérieure, vous devez appeler le code ci-dessus deux fois. Dans ce cas, assurez-vous de mesurer les performances de vos données pour décider si vous devez utiliser le code ci-dessus ou simplement le tri direct.
- Pour .net 4.5+, vous pouvez ajouter
MethodImplOptions.AggressiveInlining l'attribut Swap<T> pour des performances légèrement améliorées.
