搜索分层列表
我有一个简单的类定义为：
public class IndexEntry { public bool HighScore { get; set; } public List SubEntries { get; set; } //Other properties, etc... } 我现在需要搜索List以找到其HighScore属性设置为true的一个项目。 因为它不是一个平面列表，而是一个层次结构，它可能是一个未知数量级别的深度，因为我正在寻找的项目可能包含在任何一个SubEnties列表中，我不能做一个简单的Lambda像这个：
var foundHighScore = myList.FirstOrDefault(IE => IE.HighScore == true);
这是我的代码。 我知道这很难看（至少对我而言似乎这样）。 它有效，但在一个甚至远程大型列表上的速度很慢，我确信必须有更好的方法。
private IndexEntry GetHighScoreEntry(IEnumerable 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来清理这些代码并使其更高效。
在此先感谢您的帮助。
到目前为止发布的所有解决方案都是专门的 – 它们不是通用的或一般的，因此，下次有分层列表时，您将不得不编写新的解决方案。 呸。
这是一个通用的通用解决方案，可满足您的所有分层需求：
public static IEnumerable Flatten (this IEnumerable sequence, Func> childFetcher) { var itemsToYield = new Queue (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后立即停止生成项目。
此解决方案还避免了递归，这对于深层嵌套的层次结构来说可能是一项代价高昂的操作，从而避免了递归解决方案所产生的许多堆栈分配。
递归是你的朋友。
public IndexEntry FindHighScore(IEnumerable 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); }
您可以使用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
更新
实际上，第一个解决方案不会正常遍历。 我不认为有一个lambda唯一的解决方案，你将不得不做一些forms的递归函数。 在我的头脑中，以下是可行的，它如何处理性能明智我不确定：
public IndexEntry FindHighScore(List 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 entries) { return entries.FirstOrDefault(IE => IE.HighScore); }