搜索分层列表

Question

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

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

我现在需要搜索列表以查找其 HighScore 属性设置为 true 的一项。由于它不是一个平面列表，而是一个层次结构，其深度可能未知，并且由于我正在查找的项目可能包含在任何一个子实体列表中，因此我无法执行像这样的简单 Lambda this：

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 将停止生成项目。

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

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

您可以使用 lambda 表达式显着缩小搜索范围，例如：

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

Update

实际上，第一个解决方案将无法正确遍历。我不认为有一个仅限 lambda 的解决方案，您将必须执行某种形式的递归函数。在我的脑海中，以下内容可以工作，但我不确定它将如何应对性能方面的问题：

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