c# - 从数组中获取 n 最低的最快方法

Question

我需要从 double 组(我们称之为数组 samples)中找到 n 个最低的(不为 0)。我需要在循环中多次执行此操作，因此执行速度至关重要。我尝试先对数组进行排序，然后取前 10 个值(不为 0)，然而，尽管 Array.Sort 据说很快，但它成为了瓶颈:

const int numLowestSamples = 10;

double[] samples;

double[] lowestSamples = new double[numLowestSamples];

for (int count = 0; count < iterations; count++) // iterations typically around 2600000
{
    samples = whatever;
    Array.Sort(samples);
    lowestSamples = samples.SkipWhile(x => x == 0).Take(numLowestSamples).ToArray();
}

因此我尝试了一个不同但不太干净的解决方案，首先读取前 n 个值，对它们进行排序，然后遍历 samples 中的所有其他值，检查该值是否小于最后一个排序后的 lowestSamples 数组中的值。如果该值较低，则将其替换为数组中的值并再次对数组进行排序。事实证明这大约快了 5 倍:

const int numLowestSamples = 10;

double[] samples;

List<double> lowestSamples = new List<double>();

for (int count = 0; count < iterations; count++) // iterations typically around 2600000
{
    samples = whatever;

    lowestSamples.Clear();

    // Read first n values
    int i = 0;
    do
    {
        if (samples[i] > 0)
            lowestSamples.Add(samples[i]);

        i++;
    } while (lowestSamples.Count < numLowestSamples)

    // Sort the array
    lowestSamples.Sort();

    for (int j = numLowestSamples; j < samples.Count; j++) // samples.Count is typically 3600
    {
        // if value is larger than 0, but lower than last/highest value in lowestSamples
        // write value to array (replacing the last/highest value), then sort array so
        // last value in array still is the highest
        if (samples[j] > 0 && samples[j] < lowestSamples[numLowestSamples - 1])
        {
            lowestSamples[numLowestSamples - 1] = samples[j];
            lowestSamples.Sort();
        }
    }
}

虽然这工作得相对较快，但我想挑战任何人想出更快更好的解决方案。

Answer 1

这称为选择算法。

此 Wiki 页面上有一些通用解决方案:

http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements

(但您必须做一些工作才能转换为 C#)

您可以使用 QuickSelect 算法找到第 n 个最低的元素，然后遍历数组以获取每个元素 <= 那一个。

这里有一个用 c# 编写的 QuickSelect 示例:http://dpatrickcaldwell.blogspot.co.uk/2009/03/more-ilist-extension-methods.html