CODEWITHSUNDEEP
c#linq
Aaron Anodide
Aaron Anodide

Reputation: 17186

LINQ magic for finding multiple items in a collection without researching for each one?

UPDATE: the dictionary solution is great except when the number of thing being looked for pales compared to the number of things in the list. I should have stated that up front.

Say you have the array:

var arr = { 
  Tuple.Create("1", "won"),
  Tuple.Create("4", "fo"),
  Tuple.Create("3", "twee", 
  Tuple.Create("2", "too") 
  // ...
  // ...and many more entires...
};

And you are told to find the strings "1" and "2", so you do this:

string s1 = arr.First(c => c.Item1 == "1").Item2;
string s2 = arr.First(c => c.Item2 == "2").Item2;

But in review, it is noted that you searched the same array twice so you change it to:

string s1;
string s2;
bool founds1 = false;
bool founds2 = false;
foreach(int i; i < arr.Length; i++)
{
  if(arr[i] == "1")
  {
    s1 = arr[i].Item2;
    founds1 = true;
  }
  if(arr[i] == "2")
  {
    s2 = arr[i].Item2
    founds2 = true;
  }
  if(founds1 && founds2)
    break;
}

Is there any LINQ way of achieving the same result without being subject to efficiency problems?

Upvotes: 1

Views: 128

Answers (2)

Servy
Servy

Reputation: 203816

To efficiently search through a collection of key-value pairs you should put them into a dictionary, rather than an array:

var lookup = arr.ToDictionary(pair => pair.Item1, pair => pair.Item2);

This allows you to search for either value extremely quickly:

var s1 = lookup["1"];
var s2 = lookup["2"];

If you are only ever searching for a very small number of items, and don't have a particularly large data set, then you may be better of just doing multiple linear searches, but as the number of searches you're doing rises, the more you have to gain from spending the time up front to create the lookup.

Also note that of the two solutions you provided, they will have virtually equal performance implications. Doing one loop that takes twice as long as two other loops results in the same amount of work. The only real reason to use your second solution is if the sequence that you have cannot reliably be enumerated multiple times (perhaps it represents a database query, causes side effects, doesn't yield the same values on each iteration, etc.).

Upvotes: 3

Justin Niessner
Justin Niessner

Reputation: 245419

If you want to be able to look up items based on the first part of the Tuple, you're using the wrong data structure.

Switch to using a Dictionary<string, string> and you can use the indexer without having to enumerate the entire collection:

var dict = new Dictionary<string, string>
{
    { "1", "won" },
    { "4", "fo" },
    { "3", "twee" },
    { "2", "too" }
};

if(dict.ContainsKey("1"))
{
    founds1 = true;
    s1 = dict["1"];
}

// And so on...

Upvotes: 3

Related Questions