wyszukiwania hierarchiczną listę

Question

Mam prostą klasę zdefiniowaną jako:

public class IndexEntry 
{ 
    public bool HighScore { get; set; } 
    public List<IndexEntry> SubEntries { get; set; } 
    //Other properties, etc... 
} 

Teraz trzeba przeglądać listy, aby znaleźć jeden element, który ma jej HighScore nieruchomości ustawiony prawda. Ponieważ nie jest to płaska lista, ale Hierarchia, która może być nieznaną liczbą głębokich poziomów, a przedmiot, którego szukam, może znajdować się na dowolnej liście SubEnties, nie mogę zrobić prostej Lambdy to:

var foundHighScore = myList.FirstOrDefault(IE => IE.HighScore == true); 

Oto kod, który mam. Wiem, że to brzydkie (przynajmniej tak mi się wydaje). Działa, ale jest powolny jak grzech na nawet zdalnie dużej liście i jestem pewien, że musi być lepszy sposób.

private IndexEntry GetHighScoreEntry(IEnumerable<IndexEntry> entryList) 
{ 
    IndexEntry result = null; 
    IndexEntry recursiveResult = null; 
    foreach (IndexEntry currentEntry in entryList) 
    { 
     if (currentEntry.HighScore) 
     { 
      result = currentEntry; 
      break; //Don't need to look anymore, we found our highscore.; 
     } 
     else 
     { 
      if ((currentEntry.SubEntries == null) || (currentEntry.SubEntries.Count < 1)) 
      { 
       continue; 
      } 
      else 
      { 
       recursiveResult = GetHighScoreEntry(currentEntry.SubEntries); 
       if (recursiveResult == null) 
        continue; 
        result = recursiveResult; 
       break; 
      } 
     } 
    } 
    return result; 
} 

Mam uwierzyć, że istnieje lepszy sposób, używając nieco bardziej skomplikowany lambda lub LINQ aby oczyścić ten kod i uczynić go bardziej wydajnych.

Z góry dziękuję za pomoc.

Answer 1

Wszystkie rozwiązania zaksięgowany do tej pory są wyspecjalizowane - nie są ogólne lub ogólne, a więc, następnym razem masz listę hierarchiczną, musisz zakodować nowego rozwiązania. Fuj.

Oto ogólna, ogólne rozwiązanie, które będzie działać na wszystkich hierarchicznych potrzeb:

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> sequence, Func<T, IEnumerable<T>> childFetcher) 
{ 
    var itemsToYield = new Queue<T>(sequence); 
    while (itemsToYield.Count > 0) 
    { 
     var item = itemsToYield.Dequeue(); 
     yield return item; 

     var children = childFetcher(item); 
     if (children != null) 
     { 
      foreach (var child in children) 
      { 
       itemsToYield.Enqueue(child); 
      } 
     } 
    } 
} 

Oto jak chcesz go używać:

myList.Flatten(i => i.SubEntries).FirstOrDefault(i => i.HighScore); 

proste jak ser.

Ta metoda rozszerzenia może być użyta do przekształcenia dowolnych danych hierarchicznych w listę płaską, którą można przeszukać przy użyciu LINQ.

Inną wspaniałą rzeczą w tym rozwiązaniu jest to, że używa leniwej oceny, a zatem wykonuje tylko tyle pracy, ile wymaga osoba dzwoniąca. Na przykład w powyższym kodzie, Flatten przestanie wyrzucać elementy, gdy tylko zostanie znalezione HighScore.

To rozwiązanie pozwala także uniknąć rekursji, co może być kosztowną operacją dla głęboko zagnieżdżonych hierarchii, unikając wielu alokacji stosów, które ponoszą rekurencyjne rozwiązania.

Answer 2

Można znacznie zawęzić wyszukiwanie w dół z lambda wyrażenie czegoś podobnego:

var foundHighScore = myList.FirstOrDefault(IE => IE.HighScore or (IE.SubEntries != null && IE.SubEntries.Any(IES => IES.HighScore)); 

var indexEntry = foundHighScore; 
if (!indexEntry.HighScore) 
{ 
    indexEntry = indexEntry.SubEntries.FirstOrDefault(IE => IE.HighScore); 
} 

// do something with indexEntry 

Aktualizacja

Właściwie pierwsze rozwiązanie nie będzie przechodzić przez prawidłowo. Nie sądzę, że istnieje rozwiązanie oparte na zasadzie lambda, trzeba będzie wykonać jakąś formę funkcji rekursywnej. Z góry mojej głowy działałoby, co by poradziło z wydajnością Nie jestem pewien:

public IndexEntry FindHighScore(List<IndexEntry> entries) 
{ 
    var highScore = GetHighScore(entries); 
    if (highScore == null) 
    { 
     // give me only entries that contain sub-entries 
     var entriesWithSub = entries.Where(e => e.SubEntries != null); 
     foreach (var e in entriesWithSub) 
     { 
      highScore = FindHighScore(e.SubEntries); 
      if (highScore != null) 
       return highScore; 
     } 
    } 
    return highScore; 
} 

private IndexEntry GetHighScore(List<IndexEntry> entries) 
{ 
    return entries.FirstOrDefault(IE => IE.HighScore); 
} 

Answer 3

Rekursja jest tu twoim przyjacielem.

public IndexEntry FindHighScore(IEnumerable<IndexEntry> entries) 
{ 
    foreach (IndexEntry entry in entries) 
    { 
    IndexEntry highScore = FindHighScore(entry); 
    if (highScore != null) 
    { 
     return highScore; 
    } 
    } 
    return null; 
} 

private IndexEntry FindHighScore(IndexEntry entry) 
{ 
    return entry.HighScore ? entry : FindHighScore(entry.SubEntries); 
}