优化C# LINQ查询：从200万条有序数据中筛选最优连续范围

现有一个包含约200万条有序记录的List，每条记录包含5个SubItem，需完成两个核心任务：

• 在固定长度（如20000条）的连续数据范围中，找到SubItem[5]非空记录数量最多的最优范围；
• 在包含指定数量（如10000条）SubItem[5]非空记录的连续范围中，找到总记录数最少的最优范围。

任务1：固定长度范围的最优查询（已解决） #

初始实现的性能问题 #

最初采用逐次偏移查询固定长度范围的方式实现，因每次偏移都要重新遍历范围内的所有记录统计非空数量，导致性能极差——仅处理10万条数据就耗时135秒。

滑动窗口优化方案 #

通过滑动窗口思想，仅遍历原列表一次，每次窗口移动时仅更新离开和进入窗口的记录状态，将耗时降至1秒以内。实现代码如下：

// 初始化第一个窗口的有效记录数
int windowSize = 20000;
int currentValidCount = 0;
for (int i = 0; i < windowSize && i < arrayItems.Count; i++)
{
    if (!string.IsNullOrEmpty(arrayItems[i].SubItems[5].Text))
    {
        currentValidCount++;
    }
}

int highestValidCount = currentValidCount;
int bestStartPosition = 0;
int itmcnt = 0;

// 滑动窗口遍历剩余数据
while (itmcnt < arrayItems.Count - windowSize)
{
    // 移除窗口左端记录的影响
    if (!string.IsNullOrEmpty(arrayItems[itmcnt].SubItems[5].Text))
    {
        currentValidCount--;
    }
    // 添加窗口右端新进入记录的影响
    if (!string.IsNullOrEmpty(arrayItems[itmcnt + windowSize].SubItems[5].Text))
    {
        currentValidCount++;
    }

    // 更新最优结果
    if (currentValidCount > highestValidCount)
    {
        highestValidCount = currentValidCount;
        bestStartPosition = itmcnt + 1;
    }

    itmcnt++;
}

// 使用bestStartPosition和highestValidCount进行后续处理

任务2：指定有效记录数的最短范围查询（性能瓶颈优化） #

初始实现的问题 #

原代码通过LINQ查询过滤有效记录后，每次循环调用Skip(i).Take(20000)获取目标区间，且多次重复枚举LINQ查询（test.Count()和每次Skip/Take都会重新遍历原列表），时间复杂度达O(n²)，处理200万条数据时性能极差。初始代码如下：

// some variables to hold results
int itmscnt = arrayItems.Count;
int itmid = 0;

// get all useful items - idea is to move through useful items only
var test = from lvi in arrayItems where lvi.SubItems[5].Text != "" select lvi;

// go through selected items
for (int i = 0; i < test.Count(); i++)
{
    // take 20 000 items from the complete result - this seems to be too slow
    var targetanalyze = test.Skip(i).Take(20000);
    // retrieve counters from SubItem[0]
    int targetcnt = Int32.Parse(targetanalyze.Last().SubItems[0].Text) - Int32.Parse(targetanalyze.First().SubItems[0].Text);
    // compare
    if (targetcnt < itmscnt)
    {
        itmscnt = targetcnt;
        itmid = i;
    }
}

高效优化方案 #

核心思路是预处理有效记录的关键索引，再通过滑动窗口在预处理后的小列表上操作，彻底避免重复遍历原列表。

优化步骤

1. 预处理有效记录：遍历原列表一次，收集所有SubItem[5]非空记录的SubItem[0]数值（或原列表的位置索引），存储到单独的列表中，时间复杂度O(n)。
2. 滑动窗口找最短区间：在预处理后的列表上，遍历所有包含指定数量有效记录的连续区间，计算每个区间对应的原列表总记录数跨度，记录最小的那个区间。

优化后代码示例

// 预处理：收集所有SubItem[5]非空记录的SubItem[0]数值（假设SubItem[0]是有序递增的唯一标识）
List<int> validRecordIds = new List<int>();
foreach (var item in arrayItems)
{
    if (!string.IsNullOrEmpty(item.SubItems[5].Text))
    {
        validRecordIds.Add(int.Parse(item.SubItems[0].Text));
    }
}

int requiredValidCount = 10000; // 需要包含的有效记录数量
int minTotalRecords = int.MaxValue;
int bestValidStartIndex = 0;

// 滑动窗口遍历有效记录列表
for (int i = 0; i <= validRecordIds.Count - requiredValidCount; i++)
{
    int endId = validRecordIds[i + requiredValidCount - 1];
    int startId = validRecordIds[i];
    int currentTotalSpan = endId - startId; // 若SubItem[0]不是连续标识，需用原列表位置计算跨度

    if (currentTotalSpan < minTotalRecords)
    {
        minTotalRecords = currentTotalSpan;
        bestValidStartIndex = i;
    }
}

// 结果映射：bestValidStartIndex对应validRecordIds中的起始位置，可进一步映射回原列表的具体范围

优化说明

• 预处理仅遍历原列表一次，杜绝了LINQ查询重复枚举的问题。
• 滑动窗口在有效记录列表上操作，时间复杂度降至O(m)（m为有效记录数量，远小于200万）。
• 若SubItem[0]不是连续递增标识，只需在预处理时存储原列表的位置索引，再通过arrayItems[validIndices[i + requiredValidCount - 1]]和arrayItems[validIndices[i]]计算总记录数跨度即可。

内容的提问来源于stack exchange，提问作者niknejm