搜索层次列表 [英] Searching Hierarchical List

问题描述

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

I've got a simple class defined as:

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

我现在需要搜索一个列表，以查找其HighScore属性设置为 true 的一项.由于它不是一个平面列表，而是一个层次结构，它的层次数可能是未知的，并且由于我要查找的项目可能包含在任何一个SubEnties列表中，因此我无法执行简单的Lambda这样的操作这个:

I now need to search through a List to find the one item that has its HighScore Property set to true. Since it isn't a flat list, but a Hierarchy which can be an unknown number of levels deep and since the item I'm looking for might be contained in any one of the SubEnties lists, I can't do a simple Lambda like this:

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

这是我的代码.我知道这很丑陋(至少在我看来是如此).它可以工作，但是在一个甚至很长的列表上都可以像罪过一样慢，我敢肯定必须有更好的方法.

Here's the code I have. I know it's ugly (at least it seems that way to me). It works, but is slow as sin on an even remotely large list and I'm sure there must be a better way.

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来清理此代码并使之性能更高.

I've got believe that there's a better way using a slightly more complex lambda or with LINQ to clean up this code and make it more performant.

预先感谢您的帮助.

推荐答案

到目前为止发布的所有解决方案都是专门的-它们不是通用或通用的，因此，下次您有了层次结构列表时，您将必须编写新的解决方案. uck.

All the solutions posted so far are specialized - they are not generic or general, and thus, the next time you have a hierarchical list, you'll have to code up a new solution. Yuck.

这是一个通用的通用解决方案，可以满足您所有的层次需求:

Here's a general, generic solution that will work for all your hierarchical needs:

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对其进行搜索.

This extension method can be used to turn any hierarchical data into a flat list, which can them be searched using LINQ.

此解决方案的另一个好处是，它使用了惰性求值，因此它只能完成呼叫者要求的工作.例如，在上面的代码中，Flatten将在找到HighScore后立即停止搅动项目.

Another great thing about this solution is that is uses lazy evaluation, thus it only does as much work as the caller demands. For example, in the above code, Flatten will stop churning out items as soon as a HighScore is found.

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

This solution also avoids recursion, which can be a costly operation for deeply nested hierarchies, avoiding the many stack allocations that recursive solutions incur.

这篇关于搜索层次列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！