Creating on-the-fly lookup tables in LINQ

[DaveD]

Let's say I have a collection ("items") of objects that each have a
"string Name" property. I understand I can create a loop like this:

foreach (string name in names) {
var item = (from x in items where name == x.Name select
x).First();
// Work on item
}

Is there a way to make that query more efficient? (My assumption is
that a linear search is performed each time and that any internal
index is lost on each iteration).

One idea I had that didn;t work, but may explain what I mean:

var itemsByName = from x in items group x by x.Name;

foreach (string name in names) {
var item = itemsByName[ name ].First();
// Work on item
}

Thanks for any pointers, and I hope you appreciate the chance to point
and laugh at the LINQ newbie

Regards
Dave Dawkins

 

[Jeroen Mostert]

Let's say I have a collection ("items") of objects that each have a
"string Name" property. I understand I can create a loop like this:

foreach (string name in names) {
var item = (from x in items where name == x.Name select
x).First();
// Work on item
}

Is there a way to make that query more efficient? (My assumption is
that a linear search is performed each time and that any internal
index is lost on each iteration).

One idea I had that didn;t work, but may explain what I mean:

var itemsByName = from x in items group x by x.Name;

foreach (string name in names) {
var item = itemsByName[ name ].First();
// Work on item
}

The purest expression of what you're doing is this:

var filteredItems =
from item in items
group item by item.Name into g
where names.Contains(g.Key)
select g.First();

While this does perform a linear search for every group created, this is not
necessarily a problem if "names" isn't large. Creating the lookup for
grouping will likely consume far more time (and memory).

That said, it *is* possible to avoid this with an explicit lookup:

var itemsByName = items.ToLookup(item => item.Name);
var filteredItems =
from name in names
let namedItems = itemsByName[name]
where namedItems.Any()
select namedItems.First();

This only goes through items and names once.

If "items" is very large and "names" is small, creating the lookup in the
first place may be prohibitive. Some old-fashioned imperative programming
could help there:

string[] namesArr = names.ToArray();
foreach (var item in items) {
int i = Array.IndexOf(namesArr, item.Name);
if (i < 0) continue;
namesArr = null; // remove from further consideration

// work on item
}

This assumes that no item can have a null name (if they can, a separate
array of booleans could be used). If "names" is too large to make linear
searches practical, you could do the same exercise with
names.ToDictionary(name => name).

All this should be considered optimization that may not be necessary or
applicable, though. Try the LINQ versions first and see if they'll suit your
needs.