如何优化这段代码

Question

它有一个属性： 字符串代码 和其他10个。

常见代码是字符串列表（string[]） 汽车是汽车列表（Car[]） 过滤后的汽车列表是List。

for (int index = 0; index < cars.Length; index++)
{
    Car car = cars[index];
    if (commonCodes.Contains(car.Code))
    {
         filteredListOfCars.Add(car);
    }
}

很遗憾，这个方法执行时间太长了。

我有大约5万条记录。

如何缩短执行时间？

- user278618

Answer 1

最简单的优化方法是将常见代码从 string[] 转换为更快的查找结构，比如 Dictionary<string,object> 或者使用 .Net 3.5 及以上版本的 HashSet<string>。这将减少循环的大 O 复杂度，根据 commonCodes 的大小不同，可能会使此循环执行更快。

- JaredPar

Answer 2

Jared已经正确指出，你可以用HashSet进行优化，但我也想指出整个方法都是不必要的，浪费了输出列表的内存并使代码变得不够清晰。

你可以将整个方法写成：

var commonCodesLookup = new HashSet<int>(commonCodes);
var filteredCars = cars.Where(c => commonCodesLookup.Contains(c.Code));

filteredCars 过滤操作的执行将被延迟，这意味着如果使用 filteredCars.Take(10) 只想要前10个元素，则不需要构建整个列表（或者根本不需要构建任何列表）。

- Aaronaught

---

Linq的Join方法会为您执行查找逻辑，因此您不必指定HashSet。cars.Join(commonCodes, car=>car.Code, code => code, (car, code) => car) - DRBlaise

@DRBlaise：Join使用哈希表是真实的，但这也是一种实现细节，依靠此类细节是有风险的，因为它们可能会发生变化（即使变化不太可能）。如果您想保证某种程度的性能，则应明确语义。 - Aaronaught

@phenevo：是的，你说得对，我只是没有注意到你问题中提到的代码是一个string[]，而是假设它是一个int[]。显然，T应该是你的Code类型（在这种情况下为string）。 - Aaronaught

Answer 3

为了实现您想要的功能，我建议使用 Linq ToLookup 方法创建一个 ILookup 而不是使用字典。ToLookup 特别适用于这种情况。它基本上是对分组进行索引查找。您需要按 Code 对汽车进行分组。

var carCodeLookup = cars.ToLookup(car => car.Code);

创建carCodeLookup可能会比较慢，但是一旦创建完成，你就可以使用它来快速查找基于Code的汽车。通过进行快速查找，你可以获取到在常用代码列表中的汽车清单。

var filteredCarsQuery = commonCodes.SelectMany(code => carCodeLookup[code]);

这假设你的汽车列表不经常更改，而是你的commonCodes在查询之间是动态的。

- DRBlaise

Answer 4

你可以使用linq的join命令，就像这样

var filteredListOfCars = cars.Join(commonCodes, c => c.Code, cC => cC, (car, code) => car).ToArray();

- user287107

Answer 5

这里提供一个替代方案，用于处理 Linq 选项（它们也是不错的想法）：如果您希望快速进行筛选，我建议利用内置类型。您可以创建一个 DataTable，其中包含两个字段，即您数组中汽车的 ID 和代码（如果其他 10 个要素也很重要，您还可以添加它们）。然后，您可以在其周围创建一个 DataView 并使用其筛选属性。它在内部使用一些非常快速的索引（我相信是 B 树），因此您可能无法手动打败它的性能，除非您是算法专家，但如果您是，您就不会在这里提问了。这取决于您在做什么以及性能有多重要。

- Tesserex

Answer 6

看起来你真正需要检查的是“代码”是否通用，而不是汽车。你可以考虑使用享元模式，让汽车共享Code对象的实例。Code对象可以有一个IsCommon属性和一个Value属性。 然后，当commoncodes列表更改时，您可以执行某些操作以更新已使用的Code对象。 现在，当您进行过滤时，您只需要检查每个汽车代码的IsCommon属性即可。

- joboy