我 要合并 几个巨大的 可枚举序列 。这些列表 按已 被处理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; }
}
重复项应该保留,我们不在乎新序列中的顺序。您看到我可以使用的任何明显的优化吗?
这是我的第四篇文章(感谢@tanascius将其推进到更多的LINQ中):
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的Tuple支持进行了改进:
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
}
}
我知道合并排序算法的基本概念,但是当涉及到通过递归实现它时,我很难理解它是如何工作的。据我所知,合并排序函数将我们当前的数组分成两半,并使用递归我们一直这样做,直到每边只剩下一个元素。 如果我们的数组是{38、27、43、3、9、82、10},那么我们的递归将从使用子数组(原始数组的左侧)调用自身开始,并每次重复该过程,将数组减半并存储最左侧,直到达到1个元素: 然后在我们的第二个子例程中,我们继
本文向大家介绍Ruby实现的合并排序算法,包括了Ruby实现的合并排序算法的使用技巧和注意事项,需要的朋友参考一下 算法课的作业,利用分治法,合并排序。
我正在维基百科上阅读关于外部排序的文章,我需要理解为什么两阶段合并比一阶段合并更有效。 Wiki:但是,单次合并有一个限制。随着区块数量的增加,我们将内存分成更多的缓冲区,因此每个缓冲区都较小,因此我们必须进行许多较小的读取,而不是较少的较大读取。 因此,对于100 MB内存中的50 GB的排序,使用单个合并过程是没有效率的:磁盘需要用500个数据块中的每个数据块(我们一次从每个数据块读取100M
我在理解外部排序算法中的合并步骤时遇到了一定的困难。我在维基百科上看到了这个例子,但我无法理解。 外部排序的一个例子是外部合并排序算法,它对每个适合RAM的块进行排序,然后将排序后的块合并在一起。例如,对于仅使用100 MB RAM对900 MB数据进行排序:1)读取主内存中的100 MB数据,并通过一些常规方法进行排序,如快速排序。2) 将排序后的数据写入磁盘。3) 重复第1步和第2步,直到所有
我在理解合并排序算法的“合并”部分时有点困难,因为我试图在上下文中理解算法的部分,而某些变量/循环对我来说没有意义。我理解递归除法过程和合并的排序方面,但在这个特定的合并算法中: 我不明白最后3个循环: 你能解释一下这3个循环在合并的上下文中是用来做什么的吗?还有什么进一步的建议可以帮助你更好地理解合并排序算法的合并部分吗?
问题是关于从16:43到23:34的视频中的合并排序http://youtu.be/M814OagXWTI?t=16m43s 在退出左/右排序合并递归后,我不清楚我们是如何合并回这些子数组的。让我们从最底部开始,当我们的元素被分成两个子数组时,一个左子数组称为B,一个右子数组称为C。在16:43左右,我们跳转到合并函数,对数组B和C进行排序,这两个数组只有8和3。合并排序函数(下面的代码)基本上通
这些是家庭作业问题,但我想了解它们背后的概念,而不仅仅是得到答案。 我知道MergeSort的运行时间是O(nlogn)。似乎合并方法必须运行 n 次(因为它必须合并所有数组,最终会有 n 个数组)。因此,我想我可以推断出 MergeSort() 方法将被称为 logn times。我也认为这是有道理的,因为它正在划分数组,所以它会一直将自己除以 2,所以 logn。 因此,我觉得答案分别是C和A
我有个小问题。我尝试实现合并排序算法递归。 现在我的问题: 左=合并排序(rrays.copyOfRange(iv_sort_list,0,iv_sort_list.length));右=合并排序(rrays.copyOfRange(iv_sort_list,iv_sort_list.length,iv_sort_list.length)); 如果我尝试分配我的左/右数组“mergeSort(..