我有几个巨大的排序,我想合并枚举序列。论文列表被操纵的的IEnumerable
但已经排序的。因为输入列表是排序的,应该是可以将它们在一次旅行合并,而不重新排序任何东西。
I have several huge sorted enumerable sequences that I want to merge. Theses lists are manipulated as IEnumerable
but are already sorted. Since input lists are sorted, it should be possible to merge them in one trip, without re-sorting anything.
我想保持DEFERED执行行为。
I would like to keep the defered execution behavior.
我试着写一个天真的算法,该算法做到这一点(见下文)。然而,这看起来pretty的丑陋,我敢肯定,它可以被优化。它可能存在更多大专院校算法...
I tried to write a naive algorithm which do that (see below). However, it looks pretty ugly and I'm sure it can be optimized. It may exist a more academical algorithm...
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;
}
}
的方法,可以采用这样的:
The method can be used like that:
// Person lists are already sorted by age
MergeOrderedLists(orderedList, p => p.Age);
假设下面的人
类存在于某个地方:
assuming the following Person
class exists somewhere:
public class Person
{
public int Age { get; set; }
}
重复应该是保守的,我们不关心他们在新的排列顺序。你看不到任何明显的优化,我可以用?
Duplicates should be conserved, we don't care about their order in the new sequence. Do you see any obvious optimization I could use?
这是我第四次(感谢@tanascius沿着推动这个东西更LINQ)削减它:
Here is my fourth (thanks to @tanascius for pushing this along to something much more LINQ) cut at it:
public static IEnumerable<T> MergePreserveOrder3<T, TOrder>(
this IEnumerable<IEnumerable<T>> aa,
Func<T, TOrder> orderFunc)
where TOrder : IComparable<TOrder>
{
var items = aa.Select(xx => xx.GetEnumerator()).Where(ee => ee.MoveNext())
.OrderBy(ee => orderFunc(ee.Current)).ToList();
while (items.Count > 0)
{
yield return items[0].Current;
var next = items[0];
items.RemoveAt(0);
if (next.MoveNext())
{
// simple sorted linear insert
var value = orderFunc(next.Current);
var ii = 0;
for ( ; ii < items.Count; ++ii)
{
if (value.CompareTo(orderFunc(items[ii].Current)) <= 0)
{
items.Insert(ii, next);
break;
}
}
if (ii == items.Count) items.Add(next);
}
else next.Dispose(); // woops! can't forget IDisposable
}
}
结果:
for (int p = 0; p < people.Count; ++p)
{
Console.WriteLine("List {0}:", p + 1);
Console.WriteLine("\t{0}", String.Join(", ", people[p].Select(x => x.Name)));
}
Console.WriteLine("Merged:");
foreach (var person in people.MergePreserveOrder(pp => pp.Age))
{
Console.WriteLine("\t{0}", person.Name);
}
List 1:
8yo, 22yo, 47yo, 49yo
List 2:
35yo, 47yo, 60yo
List 3:
28yo, 55yo, 64yo
Merged:
8yo
22yo
28yo
35yo
47yo
47yo
49yo
55yo
60yo
64yo
改进与.NET 4.0中的元组的支持:
Improved with .Net 4.0's Tuple support:
public static IEnumerable<T> MergePreserveOrder4<T, TOrder>(
this IEnumerable<IEnumerable<T>> aa,
Func<T, TOrder> orderFunc) where TOrder : IComparable<TOrder>
{
var items = aa.Select(xx => xx.GetEnumerator())
.Where(ee => ee.MoveNext())
.Select(ee => Tuple.Create(orderFunc(ee.Current), ee))
.OrderBy(ee => ee.Item1).ToList();
while (items.Count > 0)
{
yield return items[0].Item2.Current;
var next = items[0];
items.RemoveAt(0);
if (next.Item2.MoveNext())
{
var value = orderFunc(next.Item2.Current);
var ii = 0;
for (; ii < items.Count; ++ii)
{
if (value.CompareTo(items[ii].Item1) <= 0)
{ // NB: using a tuple to minimize calls to orderFunc
items.Insert(ii, Tuple.Create(value, next.Item2));
break;
}
}
if (ii == items.Count) items.Add(Tuple.Create(value, next.Item2));
}
else next.Item2.Dispose(); // woops! can't forget IDisposable
}
}