搜索分层列表

Question

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

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

我现在需要搜索List以找到其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对其进行搜索.

关于这个解决方案的另一个好处是使用延迟评估,因此它只能执行与调用者要求一样多的工作.例如,在上面的代码中,Flatten将在找到HighScore后立即停止生成项目.

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