У меня есть несколько огромных отсортированных перечислимых последовательностей, которые я хочу объединить. Списки тезисов обрабатываются как IEnumerable, но уже отсортированы. Поскольку списки входных данных сортируются, должно быть возможно объединить их в одну поездку без повторной сортировки.
Я хотел бы сохранить отложенное поведение выполнения.
Я попытался написать наивный алгоритм, который делает это (см. ниже). Однако это выглядит довольно уродливо, и я уверен, что его можно оптимизировать. Он может существовать более академическим алгоритмом...
IEnumerable<T> MergeOrderedLists<T, TOrder>(IEnumerable<IEnumerable<T>> orderedlists,
Func<T, TOrder> orderBy)
{
var enumerators = orderedlists.ToDictionary(l => l.GetEnumerator(), l => default(T));
IEnumerator<T> tag = null;
var firstRun = true;
while (true)
{
var toRemove = new List<IEnumerator<T>>();
var toAdd = new List<KeyValuePair<IEnumerator<T>, T>>();
foreach (var pair in enumerators.Where(pair => firstRun || tag == pair.Key))
{
if (pair.Key.MoveNext())
toAdd.Add(pair);
else
toRemove.Add(pair.Key);
}
foreach (var enumerator in toRemove)
enumerators.Remove(enumerator);
foreach (var pair in toAdd)
enumerators[pair.Key] = pair.Key.Current;
if (enumerators.Count == 0)
yield break;
var min = enumerators.OrderBy(t => orderBy(t.Value)).FirstOrDefault();
tag = min.Key;
yield return min.Value;
firstRun = false;
}
}
Метод можно использовать следующим образом:
// Person lists are already sorted by age
MergeOrderedLists(orderedList, p => p.Age);
при условии, что существует следующий Person класс:
public class Person
{
public int Age { get; set; }
}
Дубликаты должны быть сохранены, нас не волнует их порядок в новой последовательности. Вы видите какую-либо очевидную оптимизацию, которую я мог бы использовать?
