Fastest way to search Nested List<> in C#

Question

I have a List<> which contains another List<>

I need to find if a given value is present in any of the items in the innermost list. If match found, I need that specific item and return.

I am doing this as shown below:

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?

EDIT: Some correction: I just need to see if inner list has an item with a specific value. If yes, then I need to return the top level item that that has the match. I guess the logic is the same.

Answer 1

If you want to keep the data structure then the only improvement I see is throwing out the delegate based search and search manually. I expect an improvement of about factor two with that.

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

If possible you could employ dictionaries in some way. But I don't know enough about your problem to tell you if that's possible. This can give a really big speedup since a search by key in a dictionary is O(1) and not just O(n).

In some situations a for loop might give a slight speedup over the foreach loop, but I don't know if this is one of them. So you'll need to benchmark.

Answer 2

This would be how I would achieve this using Linq.

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

or using Lambdas as per Claytons comment

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

However refactoring to use a keyed dictionary using GuestId would be faster.

Answer 3

You can do it recursively. This code probably won't work for you, but it's gonna be something like it:

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

Answer 4

Is the inner list sorted? If so you could use a binary search for the inner list which would provide a potential performance improvement. Additionally if you have control over the construct of the inner list, changing it to a Dictionary keyed on GuestId would give you a more optimal check.

Answer 5

Could be this?

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