c# - 根据包含ID的列表选择项目

我有一个项目列表，每个项目包含一个Type整数字段。

我想过滤列表以仅获取与给定整数列表匹配的项目。

我现在拥有的代码可以使用，但是我知道可以对其进行优化。

Class Item
{
    int ID;

    //Other fields & methods that are irrelevant here
}

//Selection method
IEnumerable<Item> SelectItems(List<Item> allItems, List<int> toSelect)
{
     return allItems.Where(x => toSelect.Contains(x.ID));
}

我遇到的问题是我遍历allItems，并且在每次迭代中都遍历toSelect。

我觉得有可能变得更有效率，但是我不知道如何使用Linq来实现这一目标。

这可能也是一个已经问过的问题，因为我不知道英语是怎么称呼的。这感觉有点愚蠢，因为我不知道如何在seach引擎中正确地制定公式。

最佳答案

有两种方法可以解决此问题。

当前，您具有O(N×M)性能（其中N是allItems的大小，M是toSelect的大小）。

如果您只是想轻松地将其减少，则可以通过创建O(N)+O(M)的哈希集将其减少为toSelect：

var matches = new HashSet<int>(toSelect);
return allItems.Where(x => matches.Contains(x.ID));

但是，这仍将由N-allItems的大小主导。



更好的长期方法可能是通过Id对数据进行预索引（并使其保持索引）。因此，不是allItems是List<T>-可能是Dictionary<int, T>。请注意，构建词典可能会很昂贵，因此您不想每次都想搜索时这样做：关键是在开始时执行一次（并保持它的状态）。然后这将成为O(M)（toSelect的大小，通常很小），因为字典查找为O(1)。

IEnumerable<Item> SelectItems(Dictionary<int, Item> allItems, List<int> toSelect)
{
     foreach(var id in toSelect)
     {
         if (allItems.TryGetValue(id, out var found))
             yield return found;
     }
}

（由于我们不需要检查toSelect，因此无需预哈希Contains）