c# - List 和 IEnumerable 的区别

Question

在实现这个通用 merge sort 时, 作为一种 Code Kata ，我偶然发现了 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);
    }
}

如果我删除 left 和 right 变量上的 .ToList()，它无法正确排序。你知道为什么吗？

例子

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

使用 .ToList()

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

Without .ToList()

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

Edit

It was my stupid test that got me.

I tested it like this:

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

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

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

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()之前有一个sortedInts.ToList()返回

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

但在 ints.Sort() 之后返回

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

这里到底发生了什么？

Answer 1

您的函数是正确的 - 如果您检查 Merge 的结果，您会看到结果排序为 (example) .
那么问题出在哪里呢？正如您所怀疑的那样，您正在测试错误 - 当您调用 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很懒惰。现在，递归的出现让事情变得更糟:在大多数情况下，你的 IEnumerable 上的大多数元素。是渴望的——你从左和右创建列表，它们也主要由渴望 + 懒惰的尾部组成。你最终得到一个排序的 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