计算c#的中位数

Question

我需要编写接受小数组数组的函数,它会找到中位数.

.net Math库中是否有函数？

Answer 1

看起来其他答案正在使用排序.从性能的角度来看,这不是最佳的,因为它需要O(n logn)时间.可以改为计算O(n)时间中位数.这个问题的广义版本被称为"n阶统计量",这意味着在一个集合中找到一个元素K,使得我们有n个元素小于或等于K,其余大于或等于K.所以0阶统计量将是最小的集合中的元素(注意:有些文献使用从1到N而不是从0到N-1的索引).中位数是简单的(Count-1)/2统计数据.

下面是Cormen等人的第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);
}

几点说明:

1. 此代码将尾递归代码从书中的原始版本替换为迭代循环.
2. 它还在start == end时从原始版本中删除了不必要的额外检查.
3. 我提供了两个版本的Median,一个接受IEnumerable,然后创建一个列表.如果您使用接受IList的版本,请记住它会修改列表中的顺序.
4. 上述方法计算O(n) 预期时间内的中位数或任何i阶统计量.如果你想要O(n) 更糟糕的案例时间,那么有技巧可以使用中位数中位数.虽然这会改善更糟糕的案例性能,但它会降低平均情况,因为常数O(n)现在更大.但是,如果您计算中位数主要是在非常大的数据上,那么值得一看.
5. NthOrderStatistics方法允许传递随机数生成器,然后在分区期间用于选择随机数.除非您知道您的数据具有某些模式,以便最后一个元素不够随机,或者您的代码以某种方式暴露在外部以进行有针对性的利用,否则通常不需要这样做.
6. 如果您有奇数个元素,则中位数的定义是明确的.它只是带有(Count-1)/2排序数组索引的元素.但是当你的元素数量(Count-1)/2不再是一个整数并且你有两个中位数时:降低中位数Math.Floor((Count-1)/2)和Math.Ceiling((Count-1)/2).有些教科书使用较低的中位数作为"标准",而其他教科书则建议平均使用2.对于2个元素的集合,这个问题变得特别重要.以上代码返回较低的中位数 如果您想要平均较低和较高,则需要在上面的代码上调用两次.在这种情况下,请确保测量数据的性能,以确定是否应该使用上面的代码VS直接排序.
7. 对于.net 4.5+,您可以MethodImplOptions.AggressiveInlining在Swap<T>方法上添加属性,以略微提高性能.

Answer 2

感谢Rafe,这会考虑到您的回复者发布的问题.

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 3

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

应该做的伎俩.

- 编辑 -

对于那些想要完整monty的人来说,这里是完整的,简短的纯解决方案(假设是非空的输入数组):

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 4

.net Math库中是否有函数？

没有.

不过要写自己的并不难.朴素算法对数组进行排序,并选择中间(或两个中间的)平均元素.但是,这种算法O(n log n)可以及时解决这个问题O(n).您希望查看选择算法以获得此类算法.

Answer 5

Math.NET是一个开源库,提供了计算中位数的方法.该NuGet包被称为MathNet.Numerics.

用法非常简单:

using MathNet.Numerics.Statistics;

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

Answer 6

这是杰森答案的通用版本

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