Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
156 views
in Technique[技术] by (71.8m points)

c# - 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...
}

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

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.

Thanks in advance for your help.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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

Here's how you'd use it:

myList.Flatten(i => i.SubEntries).FirstOrDefault(i => i.HighScore);

Easy as cheese.

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

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...