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

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

Легкоas cheese.

Этот метод расширения можно использовать для преобразования любых иерархических данных в плоский список, в котором их можно искать с помощью 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);
}