Поиск иерархического списка

Question

У меня есть простой класс, определенный как:

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

мне теперь нужно искать через список, чтобы найти один элемент, который установлен его рекорды недвижимости в правда. Поскольку это не плоский список, а иерархия, которая может быть неизвестным количеством уровней, и поскольку элемент, который я ищу, может содержаться в любом из списков SubEnties, я не могу сделать простой Лямбду это:

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

Вот код, который у меня есть. Я знаю, что это уродливо (по крайней мере, мне кажется это так). Он работает, но медленнее, чем грех в даже удаленно большом списке, и я уверен, что должен быть лучший способ.

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; 
} 

Я должен верить, что есть лучший способ, используя немного более сложный лямбда или с помощью LINQ, чтобы очистить этот код и сделать его более производительным.

Заранее за вашу помощь.

Answer 1

Все решения Написал до сих пор специализированы - они не являются универсальными или вообще, и, таким образом, в следующий раз у вас есть иерархический список, вы будете иметь код новое решение. Тьфу.

Вот общее, общее решение, которое будет работать для всех иерархических потребностей:

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); 
      } 
     } 
    } 
} 

Вот как вы бы использовать:

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

Легко как сыр.

Этот метод расширения может быть использован для превращения любых иерархических данных в плоский список, который можно искать с помощью LINQ.

Еще одна замечательная вещь в этом решении заключается в том, что она использует ленивую оценку, поэтому она выполняет столько же работы, сколько требует вызывающий. Например, в вышеприведенном коде Flatten перестанет собирать предметы, как только будет найден HighScore.

Это решение также позволяет избежать рекурсии, что может быть дорогостоящей операцией для глубоко вложенных иерархий, избегая множества распределений стека, которые требуют рекурсивные решения.

Answer 2

Вы могли бы существенно сузить область поиска вниз с выражением чего-то лямбда, как:

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 

Update

На самом деле первое решение не будет проходить через должным образом. Я не думаю, что для этого есть только лямбда-решение, вам нужно будет сделать какую-то рекурсивную функцию. С верхней части моей головы, следующий будет работать, как он будет справляться производительности мудрый я уверен:

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

Рекурсия является вашим другом здесь.

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); 
}