Рассчитать медиану в C#
Мне нужно написать функцию, которая будет принимать массив десятичных дробей и найдет медиану.
Есть ли функция в.net Math библиотеке?
12 ответов
Решение
Есть ли функция в.net Math библиотеке?
Нет.
Это не сложно написать свой собственный, хотя. Наивный алгоритм сортирует массив и выбирает средние (или средние из двух средних) элементов. Тем не менее, этот алгоритм O(n log n) в то время как можно решить эту проблему в O(n) время. Вы хотите посмотреть на алгоритмы выбора, чтобы получить такой алгоритм.
Похоже, что другие ответы используют сортировку. Это не оптимально с точки зрения производительности, потому что это требует O(n logn) время. Можно рассчитать медиану в O(n) время вместо Обобщенная версия этой проблемы известна как "статистика n-го порядка", что означает нахождение элемента K в наборе, в котором у нас n элементов меньше или равно K, а остальные больше или равны K. Таким образом, статистика 0-го порядка будет минимальной элемент в наборе (примечание: в некоторых источниках используется индекс от 1 до N вместо 0 до N-1). Медиана это просто (Count-1)/2порядок статистики.
Ниже приведен код, принятый из введения в алгоритмы Кормена и др., 3-е издание.
/// <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);
}
Несколько заметок:
- Этот код заменяет хвостовой рекурсивный код из исходной версии книги в итеративный цикл.
- Это также устраняет ненужную дополнительную проверку из оригинальной версии, когда start==end.
- Я предоставил две версии Median, одну, которая принимает IEnumerable, а затем создает список. Если вы используете версию, которая принимает IList, имейте в виду, что она изменяет порядок в списке.
- Выше методов рассчитывает медиану или любую статистику i-порядка в
O(n)ожидаемое время Если ты хочешьO(n)В худшем случае есть метод, использующий медиану медианы. Хотя это улучшит производительность в худшем случае, оно ухудшает средний случай, потому чтоO(n)сейчас больше. Однако, если вы рассчитываете медиану в основном на очень больших данных, стоит посмотреть. - Метод NthOrderStatistics позволяет передать генератор случайных чисел, который затем будет использоваться для выбора случайного центра во время разделения. Как правило, в этом нет необходимости, если только вы не знаете, что ваши данные имеют определенные шаблоны, так что последний элемент не будет достаточно случайным или если каким-то образом ваш код будет открыт снаружи для целевой эксплуатации.
- Определение медианы понятно, если у вас нечетное количество элементов. Это просто элемент с индексом
(Count-1)/2в отсортированном массиве. Но когда ты чётный элемент(Count-1)/2больше не является целым числом, и у вас есть две медианы: Нижняя медианаMath.Floor((Count-1)/2)а такжеMath.Ceiling((Count-1)/2), Некоторые учебники используют более низкую медиану в качестве "стандарта", в то время как другие предлагают использовать в среднем два. Этот вопрос становится особенно критичным для набора из 2 элементов. Выше код возвращает нижнюю медиану. Если вы хотите вместо усреднения нижнего и верхнего значений, вам нужно дважды вызвать вышеуказанный код. В этом случае не забудьте измерить производительность ваших данных, чтобы решить, следует ли использовать приведенный выше код VS просто для прямой сортировки. - Для.net 4.5+ вы можете добавить
MethodImplOptions.AggresiveInliningатрибут наSwap<T>метод немного улучшенной производительности.
Спасибо, Рэйф, это учитывает проблемы, опубликованные вашими ответчиками.
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;
}
Math.NET - это библиотека с открытым исходным кодом, которая предлагает метод для вычисления медианы. Пакет nuget называется MathNet.Numerics.
Использование довольно просто:
using MathNet.Numerics.Statistics;
IEnumerable<double> data;
double median = data.Median();
decimal Median(decimal[] xs) {
Array.Sort(xs);
return xs[xs.Length / 2];
}
Должен сделать свое дело.
-- РЕДАКТИРОВАТЬ --
Для тех, кто хочет получить полный монти, вот полное, короткое, чистое решение (предполагается непустой входной массив):
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;
}
Вот общая версия ответа Джейсона
/// <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;
}
Мои 5 центов (потому что это кажется более простым / простым и достаточным для коротких списков):
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 с использованием "более высокой медианы", как описано ShitalShah.
Вот самая быстрая небезопасная реализация, тот же алгоритм ранее, взятый из этого источника
[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;
}
}
}
Когда-нибудь в будущем. Это я думаю так просто, как только можно.
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();
}
}
}
Библиотека NMath CenterSpace предоставляет функцию:
double[] values = new double[arraySize];
double median = NMathFunctions.Median(values);
При желании вы можете использовать NaNMedian (если ваш массив может содержать нулевые значения), но вам нужно будет преобразовать массив в вектор:
double median = NMathFunctions.NaNMedian(new DoubleVector(values));
Библиотека NMath от CenterSpace не бесплатна, но многие университеты имеют лицензии
У меня есть гистограмма с переменной: группа
Вот как я вычисляю свою медиану:
int[] group = new int[nbr];
// -- Fill the group with values---
// sum all data in median
int median = 0;
for (int i =0;i<nbr;i++) median += group[i];
// then divide by 2
median = median / 2;
// find 50% first part
for (int i = 0; i < nbr; i++)
{
median -= group[i];
if (median <= 0)
{
median = i;
break;
}
}
медиана - это групповой индекс медианы
Ниже работает код: но не очень эффективный способ.:(
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);
}
}
}