从阵列中获得n最低的最快方法

Question

我需要从双精度数组中找到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个值,对它们进行排序,然后循环遍历样本中的所有其他值,检查该值是否小于已排序的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

无需重复对 lowerSamples 进行排序，只需将样本插入到其所在的位置即可：

int samplesCount = samples.Count;

for (int j = numLowestSamples; j < samplesCount; j++)
{
    double sample = samples[j];

    if (sample > 0 && sample < currentMax)
    {
        int k;

        for (k = 0; k < numLowestSamples; k++)
        {
           if (sample < lowestSamples[k])
           {
              Array.Copy(lowestSamples, k, lowestSamples, k + 1, numLowestSamples - k - 1);
              lowestSamples[k] = sample;

              break;
           }
        }

        if (k == numLowestSamples)
        {
           lowestSamples[numLowestSamples - 1] = sample;
        }

        currentMax = lowestSamples[numLowestSamples - 1];
    }
}

现在，如果 numLowestSamples 需要非常大（接近样本.count 的大小），那么您可能需要使用可能更快的优先级队列（通常插入新样本的时间复杂度为 O(logn) 而不是 O(n/ 2) 其中 n 是 numLowestSamples)。优先级队列将能够有效地插入新值并在 O(logn) 时间内删除最大值。

当 numLowestSamples 为 10 时，实际上没有必要——特别是因为您只处理双精度数而不是复杂的数据结构。对于堆和小的 numLowestSamples，为堆节点分配内存的开销（大多数优先级队列使用堆）可能会大于任何搜索/插入效率增益（测试很重要）。