c# - 搜索层次列表

Question

我有一个简单的类定义为:

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

我现在需要搜索列表以找到其 HighScore 属性设置为 true 的项目。因为它不是一个平面列表，而是一个层次结构，它的层次数可能是未知的，而且由于我要查找的项目可能包含在任何一个 SubEnties 列表中，所以我不能做一个简单的 Lambda 之类的这个:

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

我相信有更好的方法使用稍微复杂一点的 lambda 或 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 对其进行搜索。

这个解决方案的另一个优点是它使用惰性评估，因此它只做调用者要求的工作。例如，在上面的代码中，一旦找到 HighScore，Flatten 就会停止生产项目。

此解决方案还避免了递归，递归对于深度嵌套的层次结构来说可能是一项代价高昂的操作，避免了递归解决方案产生的许多堆栈分配。