在C#中搜索嵌套List<>的最快方法

Question

我有一个包含另一个List<>的列表。

我需要查找给定值是否存在于最内层列表中的任何项目中。

如果找到匹配项，我需要返回该特定项。

我正在如下所示地执行此操作：

InnerList inner = null;
foreach(TopList in topListItems)
{
    inner = asn.Owners.Find(x => x.GuestId == guestId);
    if(inner != null)
         break;
}

//item found if inner is not null
//else item absent in the inner list

Any other alternate way that may run faster than this?

编辑： 有所更正：我只需要查看内部列表是否具有特定值的项目。 如果是，则需要返回具有匹配项的顶级项目。 我想逻辑是相同的。

- user762196

Answer 1

这是我使用 Linq 实现的方法。

var answer = from topList in TopListItems
             from innerListItem in topList.InnerList
             where innerListItem.GuestId == guestId
             select topList;

或者按照Clayton的评论使用Lambda表达式

var answer = TopListItems.FirstOrDefault(topList => 
             topList.InnerList.Any(innerList => 
             innerList.GuestId == guestId));

然而，重构为使用GuestId键入的字典将更快。

- Justin Shield

---

使用Linq的更优方法是topList.FirstOrDefault(innerList => innerList.Any(item => item.GuestId == guestId)。 - Clayton

是的，这可能会让你有点困惑，但这种方式会在找到一个项目后立即返回，而不是遍历两个列表的全部内容。 - Clayton

Answer 2

如果你想保留数据结构，那么我唯一看到的改进就是放弃基于代理的搜索，改为手动搜索。我预计这样会有两倍左右的提升。

foreach(var innerList in outerList)
{
    foreach(var item in innerList)
    {
        if(item.GuestId == guestId)
            return innerList;
    }
}
return null;

如果可能的话，你可以以某种方式使用字典。但我不知道你的问题是否适用。这可以大大加快速度，因为在字典中按键搜索是O(1)，而不仅仅是O(n)。

在某些情况下，for循环可能比foreach循环略微提高速度，但我不知道这是否适用于此。所以你需要进行基准测试。

- CodesInChaos

---

你的意思是运行一个双重循环，当匹配到时退出吗？我一开始就是这么做的。然后我想默认委托可能更快。不是吗？ - user762196

根据我的经验，与手动编码相比，Linq 要慢大约两倍。我认为没有委托的嵌套循环将是在不改变数据结构的情况下获得最快速度的方法。 - CodesInChaos

Answer 3

你可以使用递归来实现。这段代码可能对你无效，但它会类似于这样：

public object loopList(List<object> dList,object searchvalue)
{
    foreach(object value in dList)
    {
      if(searchvalue == value)
      {
        return value;
      }
      else
      {
         loopList((List<object>)value);
       }
    }
}

- Kevin Wang

---

它比原始代码更有价值，可读性差是不好的。 - Alexander Beletsky

我通常避免使用递归，但它同样也可以运行。 - user762196

如果列表没有任意嵌套，递归就完全不必要。在 OP 的情况下，有一个外部列表，它是内部列表的列表。这是两个级别，始终如此。 - siride

@siride 在这种情况下，性能将与两个嵌套的foreach循环一样好。这使他在需要更深层次嵌套时拥有更多的灵活性。 - Kevin Wang

@KevinWang：我不太关心性能，而是代码的质量。避免使用庞大的函数确实有很多好处，但是拥有一堆微小的函数可能同样难以管理。 - siride

Answer 4

可能是这样吗？

InnerList inner = null;
foreach (var innr in outerList.SelectMany(c =>c.Owners
                              .Where(x => x.GuestId == guestId)))
{
    inner = innr;
}

- BUFK

Answer 5

内部列表是否已排序？如果是，您可以对内部列表使用二进制搜索，这将提供潜在的性能改进。此外，如果您可以控制内部列表的构造，将其更改为以GuestId为键的字典将为您提供更优化的检查。

- Clayton

---

未排序。但是内部列表每个外部列表项最多可以有10个值。外部列表中有0-20个项目。 - user762196

在这种情况下，使用双重循环，在内部循环中找到一个项目后立即退出两个循环，将是最好的方法。 - Clayton