C# - Linq 使用 List 和 Where 子句优化代码

Question

我有以下代码:

        var tempResults = new Dictionary<Record, List<Record>>();            
        errors = new List<Record>();
        foreach (Record record in diag)
        {
            var code = Convert.ToInt16(Regex.Split(record.Line, @"\s{1,}")[4], 16);                
            var cond = codes.Where(x => x.Value == code && x.Active).FirstOrDefault();
            if (cond == null)
            {
                errors.Add(record);
                continue;
            }

            var min = record.Datetime.AddSeconds(downDiff);
            var max = record.Datetime.AddSeconds(upDiff);

            //PROBLEM PART - It takes around 4,5ms
            var possibleResults = cas.Where(x => x.Datetime >= min && x.Datetime <= max).ToList();

            if (possibleResults.Count == 0)
                errors.Add(record);
            else
            {                    
                if (!CompareCond(record, possibleResults, cond, ref tempResults, false))
                {                        
                        errors.Add(record);
                }
            }
        }

变量diag是记录列表

变量 cas 是包含大约 50k 项的记录列表。

问题是它太慢了。第一个 where 子句的部分需要大约 4,6599 毫秒，例如对于 List diag 中的 3000 条记录，它需要 3000*4,6599 = 14 秒。有没有优化代码的选项？

Answer 1

你可以加快你强调的那个特定语句

cas.Where(x => x.Datetime >= min && x.Datetime <= max).ToList();

对 cas 列表进行二分查找。首先按Datetime 对cas 进行预排序:

cas.Sort((a,b) => a.Datetime.CompareTo(b.Datetime));

然后为 Record 创建比较器，它将只比较 Datetime 属性(实现假定列表中没有空记录):

private class RecordDateComparer : IComparer<Record> {
    public int Compare(Record x, Record y) {
        return x.Datetime.CompareTo(y.Datetime);
    }
}

然后你可以这样翻译你的 Where 子句:

var index = cas.BinarySearch(new Record { Datetime = min }, new RecordDateComparer());
if (index < 0)
    index = ~index;
var possibleResults = new List<Record>();    
// go backwards, for duplicates            
for (int i = index - 1; i >= 0; i--) {
    var res = cas[i];
    if (res.Datetime <= max && res.Datetime >= min)
        possibleResults.Add(res);
    else break;
}
// go forward until item bigger than max is found
for (int i = index; i < cas.Count; i++) {
    var res = cas[i];
    if (res.Datetime <= max &&res.Datetime >= min)
        possibleResults.Add(res);
    else break;
}    

想法是使用 BinarySearch 找到 Datetime 等于或大于您的 min 的第一条记录。如果找到完全匹配 - 它返回匹配元素的索引。如果未找到 - 它返回负值，可以通过 ~index 操作将其转换为大于目标的第一个元素的索引。

当我们找到该元素时，我们可以向前移动列表并获取项目，直到我们找到 Datetime 大于最大值的项目(因为列表已排序)。我们还需要倒退一点，因为如果存在重复项 - 二分搜索将不必返回第一个，因此我们需要倒退以寻找潜在的重复项。

其他改进可能包括:

• 将事件代码放入 for 循环之外的 字典(由 Value 键控)，从而用 Where 搜索替换代码Dictionary.ContainsKey.

• 正如@Digitalsa1nt 在评论中所建议的那样 - 使用 Parallel.For、PLINQ 或任何类似技术并行化 foreach 循环。这是并行化的完美案例，因为循环只包含 CPU 绑定(bind)工作。当然，您需要进行一些调整以使其成为线程安全的，例如对错误 使用线程安全集合(或锁定添加错误)。