Поиск иерархического списка
Мне определили простой класс как:
public class IndexEntry
{
public bool HighScore { get; set; }
public List<IndexEntry> SubEntries { get; set; }
//Other properties, etc...
}
Я теперь должен перерыть Список для нахождения одного объекта, который имеет его Набор свойств HighScore к истинному. Так как это не плоский список, а Иерархия, которая может быть неизвестным количеством уровней глубоко и начиная с объекта, который я ищу, мог бы содержаться в любом из списков SubEnties, я не могу сделать простой Лямбды как это:
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;
}
Я имею, полагают, что существует лучший способ использовать немного более сложную лямбду или с LINQ, чтобы очистить этот код и сделать это более производительным.
Заранее спасибо за Вашу справку.
3 ответа
Все размещенные до сих пор решения являются специализированными - они не являются общими или общими, и поэтому в следующий раз, когда у вас будет иерархический список, вы должны будете закодировать новое решение. Фу.
Вот общее, общее решение, которое будет работать для всех ваших иерархических нужд:
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.
Это решение также позволяет избежать рекурсии, которая может быть дорогостоящей операцией для глубоко вложенных иерархий, избегая многочисленных распределений стека, которые возникают в рекурсивных решениях.
Рекурсия - ваш друг здесь.
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);
}
Можно значительно сузить поиск лямбда выражением вроде:
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
Обновить
На самом деле первое решение не пройдет должным образом. Я не думаю, что существует лямбда-выражение, вам придется выполнять какую-то рекурсивную функцию. На вершине моей головы сработает следующее, как она справится с производительностью, я не уверен:
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);
}