5

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.

Improve this question

5 Answers 5

Reset to default
8

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

A more optimal approach with Linq would be topList.FirstOrDefault(innerList => innerList.Any(item => item.GuestId == guestId)
yeah it can be a bit more confusing to wrap your head around, but this way it will return as soon as an item is found rather than traversing the entirety of both lists.
4

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.

Improve this answer

2 Comments

You mean run a double loop and exit when match found? I had that at first. Then I thought default delegate might be faster. Not?
In my experience linq is slower by a factor of about two compared to manual coding. I think nested loops without delegates will be about the fastest you can get without changes to your data structure.
1

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); } } }
Improve this answer

5 Comments

It is much more worth then original code, less readability is bad
I usually stay away from recursion. But it would work as well.
Recursion is completely unnecessary if the lists aren't arbitrarily nested. In the OP's case, there is one outer list that is a list of inner lists. That's two levels, all the time.
@siride The performance is going to be just as good as two nested foreach loops in that case. This allows him more flexibility for deeper nesting if he ever chooses.
@KevinWang: I'm not too concerned about performance, but rather the quality of the code. There's much to be said for avoiding giant functions, but having a spaghetti plate of miniscule functions is perhaps equally difficult to manage.
0

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.

Improve this answer

2 Comments

Not sorted. But inner list can have at most 10 values for each of outer list item. Outer list has 0-20 items in it.
@user762196 In that case a double for loop where you exit both loops as soon as an item is found in the inner loop, will be the best approach.
0

Could be this?

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

Comments