在排序列表 C# 中查找小于或等于双精度的项目位置的最快方法

Question

我正在探索遍历三个排序列表以查找等于或小于双精度值的第一项位置的最快方法。列表包含两列双精度

。我在下面附上了以下两个工作示例，它们包含在一个更大的 while 循环(它也修改了更改 [0] 值的当前压力列表(值中。但是，考虑到较大的 while 循环解析的行数 (500,000+(，下面的代码太慢了(三个 while 循环的一次迭代需要>20 毫秒(。

"allPressures" 包含所有行，而 currentPressure 由其余代码修改。while 回路用于将流量、转速和位置列表的时间与压力列表中的时间对齐。

换句话说，我试图找到确定 x 的最快方法 例如

FlowList[x].Time =< currentPressure[0].Time

任何建议将不胜感激！

例子：

for (int i = 0; i < allPressures.Count; i++)
{
if (FlowList[i].Time >= currentPressure[0].Time)
{
fl = i;
break;
}
}
for (int i = 0; i < allPressures.Count; i++)
{
if (RpmList[i].Time >= currentPressure[0].Time)
{
rp = i;
break;
}
}
for (int i = 0; i < allPressures.Count; i++)
{
if (PositionList[i].Time >= currentPressure[0].Time)
{
bp = i;
break;
}
}

使用 while 循环：

while (FlowList[fl].Time < currentPressure[0].Time)
{
fl++;
}
while (RpmList[rp].Time < currentPressure[0].Time)
{
rp++;
}
while (PositionList[bp].Time < currentPressure[0].Time)
{
bp++;
}  

Answer 1

问题是你正在做线性搜索。这意味着在最坏的情况下，您将迭代列表中的所有元素。这为您提供了O(3*n)的计算复杂度，其中n是列表的长度，3是要搜索的列表数。

由于您的列表已排序，因此您可以使用更快的二叉搜索，该搜索具有O(log(n))的复杂性，在您的情况下O(3*log(n))。

幸运的是，您不必自己实现它，因为 .NET 提供了帮助程序方法 List.BinarySearch((。您将需要采用自定义比较器的比较器，因为您要比较PressureData对象。

由于您要查找小于搜索值的最接近值的索引，因此您必须使用一个小技巧：当BinarySearch()找不到匹配值时，它将返回大于搜索值的下一个元素的索引。由此很容易找到比搜索值小的上一个元素。

下面是实现这一点的扩展方法：

public static int FindMaxIndex<T>(
this List<T> sortedList, T inclusiveUpperBound, IComparer<T> comparer = null)
{
var index = sortedList.BinarySearch(inclusiveUpperBound, comparer);
// The max value was found in the list. Just return its index.
if (index >= 0)
return index;
// The max value was not found and "~index" is the index of the
// next value greater than the search value.
index = ~index;
// There are values in the list less than the search value.
// Return the index of the closest one.
if (index > 0)
return index - 1;
// All values in the list are greater than the search value.
return -1;
}

在 https://dotnetfiddle.net/kLZsM5 进行测试

将此方法与可识别PressureData对象的比较器一起使用：

var pdc = Comparer<PressureData>.Create((x, y) => x.Time.CompareTo(y.Time));
var fl = FlowList.FindMaxIndex(currentPressure[0], pdc);

下面是一个工作示例：https://dotnetfiddle.net/Dmgzsv