List 和 IEnumerable 的区别

在实现这个通用的同时归并排序 http://en.wikipedia.org/wiki/Merge_sort，作为一种代码卡塔 http://en.wikipedia.org/wiki/Kata_%28programming%29，我偶然发现了 IEnumerable 和 List 之间的区别，我需要帮助才能弄清楚。

这是归并排序

public class MergeSort<T>
{
    public IEnumerable<T> Sort(IEnumerable<T> arr)
    {
        if (arr.Count() <= 1) return arr;

        int middle = arr.Count() / 2;
        var left = arr.Take(middle).ToList();
        var right = arr.Skip(middle).ToList();
        return Merge(Sort(left), Sort(right));
    }

    private static IEnumerable<T> Merge(IEnumerable<T> left, IEnumerable<T> right)
    {
        var arrSorted = new List<T>();

        while (left.Count() > 0 && right.Count() > 0)
        {
            if (Comparer<T>.Default.Compare(left.First(), right.First()) < 0)
            {
                arrSorted.Add(left.First());
                left=left.Skip(1);
            }
            else
            {
                arrSorted.Add(right.First());  
                right=right.Skip(1);  
            }
        }

        return arrSorted.Concat(left).Concat(right);
    }
}

如果我删除.ToList() on the left and right它无法正确排序的变量。你明白为什么吗？

Example

var ints = new List<int> { 5, 8, 2, 1, 7 };
var mergeSortInt = new MergeSort<int>();
var sortedInts = mergeSortInt.Sort(ints);

With .ToList()

    [0]: 1
    [1]: 2
    [2]: 5
    [3]: 7
    [4]: 8
  

Without .ToList()

    [0]: 1
    [1]: 2
    [2]: 5
    [3]: 7
    [4]: 2
  

Edit

正是我愚蠢的测试让我陷入了困境。

我是这样测试的：

var sortedInts = mergeSortInt.Sort(ints);
ints.Sort();
if (Enumerable.SequenceEqual(ints, sortedInts)) Console.WriteLine("ints sorts ok");

只需将第一行更改为

var sortedInts = mergeSortInt.Sort(ints).ToList();

消除了问题（以及惰性评估）。

编辑2010-12-29

我以为我会弄清楚惰性求值是如何把事情弄乱的，但我就是不明白。

去除.ToList()在上面的 Sort 方法中像这样

var left = arr.Take(middle);
var right = arr.Skip(middle);

然后试试这个

var ints = new List<int> { 5, 8, 2 };
var mergeSortInt = new MergeSort<int>();
var sortedInts = mergeSortInt.Sort(ints);
ints.Sort();
if (Enumerable.SequenceEqual(ints, sortedInts)) Console.WriteLine("ints sorts ok");

调试的时候可以看到之前ints.Sort() a sortedInts.ToList() returns

[0]: 2
[1]: 5
[2]: 8

但是之后ints.Sort()它返回

[0]: 2
[1]: 5
[2]: 5

这里究竟发生了什么？

你的功能是正确的 - 如果你检查结果Merge，你会看到结果已排序（例子） http://ideone.com/NirvK.
那么问题出在哪里呢？正如您所怀疑的那样，您的测试是错误的 -你打电话时Sort在您的原始列表中，您可以更改从中派生的所有集合！
这是演示您所做的事情的片段：

List<int> numbers = new List<int> {5, 4};
IEnumerable<int> first = numbers.Take(1);
Console.WriteLine(first.Single()); //prints 5
numbers.Sort();
Console.WriteLine(first.Single()); //prints 4!

您创建的所有集合基本上与first- 在某种程度上，它们是指向位置的惰性指针ints。显然，当你打电话时ToList，问题就消除了。

你的情况比这更复杂。你的Sort是部分懒惰，正如你所建议的：首先你创建一个列表（arrSorted) 并向其添加整数。这部分并不懒惰，这就是您看到前几个元素已排序的原因。接下来，您添加剩余的元素 - 但是Concat很懒。现在，递归的出现让这个问题变得更加混乱：在大多数情况下，你的大多数元素IEnumerableare eager - 您从左侧和右侧创建列表，这些列表也主要由 eager + lazy tail 组成。你最终会得到一个排序的List<int>，惰性连接到一个惰性指针，它应该是只是最后一个元素（之前合并了其他元素）。
这是函数的调用图 - 红色表示惰性集合，黑色表示实数：

当您更改列表时，新列表大部分保持不变，但最后一个元素是惰性的，并指向原始列表中最大元素的位置。

结果基本上不错，但它的最后一个元素仍然指向原始列表：

最后一个例子：考虑您正在更改原始列表中的所有元素。正如您所看到的，排序集合中的大多数元素保持不变，但最后一个元素是惰性的并指向新值：

var ints = new List<int> { 3,2,1 };
var mergeSortInt = new MergeSort<int>();
var sortedInts = mergeSortInt.Sort(ints);
// sortedInts is { 1, 2, 3 }
for(int i=0;i<ints.Count;i++) ints[i] = -i * 10;
// sortedInts is { 1, 2, 0 }

这是 Ideone 上的相同示例：http://ideone.com/FQVR7 http://ideone.com/FQVR7