Поиск в иерархическом списке

Question

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

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

Теперь мне нужно выполнить поиск по списку, чтобы найти один элемент, для которого свойство HighScore имеет значение true. Поскольку это не плоский список, а иерархия, которая может иметь неизвестное количество уровней в глубину, и поскольку искомый элемент может содержаться в любом из списков дочерних объектов, я не могу сделать такую ​​простую лямбду, как этот:

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

Рекурсия твой друг здесь.

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

Answer 3

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

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

Обновить

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

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