List<T>和IEnumerable的区别

Question

在实现这个通用的合并排序（Merge Sort）时，我把它当做一种代码卡塔。在此期间，我发现了 IEnumerable 和 List 之间的一个区别，希望能得到帮助来解决这个问题。

下面是 MergeSort 的代码：

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

未使用.ToList()

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

编辑

这是我的愚蠢测试。

我像这样进行测试：

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

这里到底发生了什么？

- Jonas Elfström

---

在删除 ToList() 后，必须承认它在我的电脑上运行良好。 - nan

这是一个无法重现的例子（使用mono）： http://ideone.com/7mllZ。 - Kobi

我唯一怀疑的部分是 left=left.Skip(1)，可能会有延迟执行的问题，但我不知道具体情况。 - Kobi

我在问题中添加了一个新的示例，因为我仍然无法准确地弄清楚正在发生什么。 - Jonas Elfström

我已经实现了一个完全惰性计算的版本http://alicebobandmallory.com/articles/2011/01/01/lazy-evaluation-is-no-friend-of-mutable-state - Jonas Elfström

Answer 1

你的函数是正确的 - 如果你检查Merge的结果，你会看到结果已经排序 (示例)。
那么问题出在哪里呢？正如你所怀疑的那样，你的测试方式有问题 - 当你在原始列表上调用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

- Kobi

---

我明白。我也知道可变集合和惰性求值是一个糟糕的组合。但我不明白的是，它如何在这种情况下搞乱了排序，因为已经排序好的列表不应该是一个问题。除非我的小型MergeSort并不完全惰性，而只是半惰性或其他什么原因。 - Jonas Elfström

@Jonas - 我已经更新了我的解释，并加入了更多细节，你的代码似乎有不少复杂性 :) - Kobi

太棒了的解释！现在我终于明白了。谢谢！ - Jonas Elfström

我实现了一个完全惰性求值的版本，并在博客中记录了我所面临的问题。http://alicebobandmallory.com/articles/2011/01/01/lazy-evaluation-is-no-friend-of-mutable-state - Jonas Elfström

@Jonas - 感谢你的关注，很高兴能帮忙！ - Kobi

Answer 2

无法复现 - 我刚刚尝试了一下，它完全正常。显然在各种方面它都相当低效，但是删除ToList调用并不会导致其失败。

这是我的测试代码，使用你的MergeSort代码，但没有ToList()调用：

using System;
using System.Collections.Generic;

public static class Extensions
{
    public static void Dump<T>(this IEnumerable<T> items, string name)
    {
        Console.WriteLine(name);
        foreach (T item in items)
        {
            Console.Write(item);
            Console.Write(" ");
        }
        Console.WriteLine();
    }
}

class Test
{    
    static void Main()
    {
        var ints = new List<int> { 5, 8, 2, 1, 7 };
        var mergeSortInt = new MergeSort<int>();
        var sortedInts = mergeSortInt.Sort(ints);
        sortedInts.Dump("Sorted");
    }
}

输出：

Sorted
1 2 5 7 8

也许问题出在你测试代码的方式上了？

- Jon Skeet

---

我本以为我会弄清楚惰性求值在这里是如何搞砸的，但我就是不明白。我在问题中添加了一个新的例子。 - Jonas Elfström

Answer 3

我用列表和不用列表都运行了它，它都可以工作。
无论如何，归并排序的一个优点是它能够在O(1)空间复杂度下进行原地排序，这个实现不会受益于此。

- Itay Karo

---

归并排序不声称具有O(1)复杂度，它的复杂度为O(n log n)。 - Jon Skeet

它并没有声称自己可以在O(nlgn)时间复杂度和O(1)空间复杂度下实现，但是这两个方面都不太够用。 - Itay Karo

啊，你是指“空间”复杂度吗？我以前从未听说过“位置复杂度”。如果是这样的话，那是真的。这种方法在很多方面都是低效的，但我想这可能是为了教育实验而采用的，这也没问题。 - Jon Skeet

Answer 4

问题是您将左右两边排序，然后将右边合并到一个序列中。这并不意味着您得到了一个完全排序的序列。

首先，您必须合并，然后再进行排序：

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();

    // first merge and than sort
    return Sort(Merge(left, right));
}

- user432219

---

这完全违背了归并排序的初衷 - 你可以直接使用 Sort(arr) 进行排序 - 你提议拆分和合并（=什么也没做），然后再进行排序 :) 。 - Kobi