我需要从双精度数组中找到 n 最低的(不是 0)(我们称之为数组samples)。我需要在循环中多次执行此操作,因此执行速度至关重要。我尝试先对数组进行排序,然后取前 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 个值,对它们进行排序,然后循环遍历样本中的所有其他值,检查该值是否小于排序后的最低样本数组中的最后一个值。如果该值较低,则将其替换为数组中的值并再次对数组进行排序。结果证明这快了大约 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();
}
}
}
虽然这工作相对较快,但我想挑战任何人提出更快更好的解决方案。