IList必须是有限的吗？

Question

必须将.NET的IList设为有限吗？假设我编写了一个实现IList<BigInteger>的类FibonacciList

• 属性Item[n]返回第n个斐波那契数。
• 属性IsReadOnly返回true。
• 我们可以轻松地实现IndexOf和Contains方法，因为斐波那契序列是递增的-要测试数字m是否为斐波那契数，我们只需要计算斐波那契数列直到m（有限）。
• 方法GetEnumerator()做正确的事情

现在，除了Count()之外，我们已经实现了只读ILists预期的所有方法。

这很酷，还是滥用了IList？

---

斐波那契数列很快变得不切实际大（因此上面使用了 IList<BigInteger>） 。一个有界的无限序列可能更明智，它可以实现 IList<long> 或 IList<double>。

补充二：斐波那契数列可能是一个糟糕的例子，因为计算远距离的值是昂贵的 - 要找到第n个值，必须计算所有较早的值。因此，正如Mošmondor所说，人们可能会将其作为IEnumerable并使用.ElementAt。然而，存在其他序列，可以快速计算远距离的值而不计算先前的值。 （令人惊讶的是，pi的数字就是这样的序列）。这些序列更具“列表”性，它们真正支持随机访问。

编辑：没有人反对无限的IEnumerables。它们如何处理Count()？

- Colonel Panic

---

你不能实现 Count()，所以这看起来确实是对 IList<T> 的滥用。毕竟，你不能部分地实现一个接口。 - Frédéric Hamidi

我会简单地返回 int.MaxValue。索引也受 int 大小的限制，而且枚举在现实时间范围内也无法到达那里。 - CodesInChaos

斐波那契数列的第n个成员是否存在数学快捷方式，还是只是简单地将中间成员相加？即索引器是否比求和枚举更快？ - Jodrell

@Colonel Panic，斐波那契数列有一个明确的公式（参见：http://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio）。 - phipsgabler

显式公式使用实数（即sqrt(5)），因此精确使用将会很困难。 - Colonel Panic

Answer 1

对于大多数开发人员来说，IList和ICollection意味着你有一个预先评估的内存中集合可供使用。特别是对于IList，存在常数时间的Add和索引操作的隐含契约。这就是为什么LinkedList<T>没有实现IList<T>。我认为FibonacciList违反了这个隐含的契约。

注意下面这段话来自最近一篇MSDN Magazine文章，讨论添加只读集合接口到.NET 4.5的原因：

“对于大多数涉及类型集合的场景来说，IEnumerable<T>已经足够了，但有时您需要比它提供更多的功能。”

• 材料化： IEnumerable<T>不允许您表达集合是否已经可用（“材料化”）或者是否在每次迭代时都被计算（例如，如果它表示一个LINQ查询）。当算法需要对集合进行多次迭代时，如果计算序列很昂贵，则可能导致性能下降；由于在后续的传递中再次生成对象时可能导致身份不匹配，因此也可能会导致微妙的错误。”

正如其他人所指出的那样，还有一个问题，即对于.Count应该返回什么。

对于这种数据集合，使用IEnumerable或者IQueryable都是可以的，因为这些类型可以被惰性评估。

关于Edit 1： .Count()没有被IEnumerable<T>接口实现：它是一个扩展方法。因此，开发人员需要预期它可能需要任意数量的时间，并且在不需要实际知道项数的情况下避免调用它。例如，如果您只想知道IEnumerable<T>是否有任何项，最好使用.Any()。如果您知道有最大数量的项要处理，可以使用.Take()。如果一个集合中有超过int.MaxValue个项，.Count()将遇到操作溢出。因此，有一些解决办法可以帮助减少与无限序列相关的危险。但是，如果程序员没有考虑到这些可能性，仍然可能会导致问题。

关于Edit 2：如果您计划以索引是常数时间的方式实现序列，那么这很方便地解决了我的主要观点。六个字母的变量答案仍然成立。 ^{*显然这还有更多要考虑：只有在IList.IsFixedSize返回false时，Add才能正常工作。只有在IsReadOnly返回false时，修改才是可能的等等。首先，IList是一个设计不佳的接口：这个事实可能通过在.NET 4.5中引入只读集合接口来得到纠正。}

更新

经过进一步的思考，我个人认为，IEnumerable<>

<code>// LINQ to Fibonacci!
var fibQuery = from n in Fibonacci.Numbers // (returns an IQueryable<>)
               where n.Index > 5 && n.Value < 20000
               select n.Value;
var fibCount = fibQuery.Count();
var fibList = fibQuery.ToList();
</code>

由于您的查询提供程序将有权将where子句评估为lambda表达式，因此您可以具有足够的控制来实现Count方法和.GetEnumerator()，以确保查询足够严格限制以产生真正的答案，或者在调用方法时立即抛出异常。

但是这种做法过于巧妙，并且在任何现实软件中都可能是一个非常糟糕的想法。

- StriplingWarrior

---

一个 IList<T> 可以是只读的，所以 Add 不是必需的。 - user7116

在我看来，这里最重要的问题是索引器效率非常低下，这对于 IList 来说是不可接受的。 - Servy

在.NET 4.5中添加只读集合接口，终于来了。他们晚了2.5个版本... - CodesInChaos

@StriplingWarrior：新的IReadOnlyCollection<out T>使得期望顺序索引的Animal集合的代码可以接受SiameseCat集合，但我没有注意到其中关于不可变性的任何内容。假设Enumerable.Range(1,1000000)被传递给一个想要持久化它的类。稍后，该类将其传递给另一个类，后者再传递给第三个类。最终结果是：每个类都持有一个百万项数组，如果两个类想要检查它们是否持有相同的序列，则需要比较一百万项。 - supercat

@StriplingWarrior：如果有一种方法可以让Enumerable.Range(1,1000000)报告自己是不可变的，而类在复制序列之前检查它是否是不可变的，或者调用一个AsImmutable方法来检查，那么所有对象最终都可以使用由Enumerable.Range返回的相同实例。SequenceEqual方法可以注意到被比较的序列是相同的不可变对象，并且无需比较即可返回true。这将大大提高性能。 - supercat

Answer 2

我认为符合规范的实现必须是有限的，否则你会为ICollection<T>.Count返回什么呢？

（注：该段内容涉及IT技术）

/// <summary>
/// Gets the number of elements contained in the <see cref="ICollection{T}" />.
/// </summary>
int Count { get; }

另一个需要考虑的问题是“CopyTo”，在正常情况下，它不会在斐波那契案例中停止。

这意味着适当实现斐波那契序列应该只是使用生成器模式的“IEnumerable”。滥用“IList”将会导致问题。

- user7116

---

一个想法是返回到目前为止计算的最大索引。因此，如果您已经计算了fib(10)，将10作为当前计数返回可能是合理的。如果我的下一个请求要求fib(100)，则必须添加所有这些中间值。 - duffymo

@duffymo：假设我的第一个用法是 if (fib.Count > 0) ...，现在怎么办？ - user7116

那很可能会破坏任何L2O优化。 - user7116

"NotImplementedException" 是错误的。 应该使用 "NotSupportedException"。 - CodesInChaos

Answer 3

在你的情况下，我宁愿“违反”IEnumerable并使用yield return来达到我的目的。 :)

- Daniel Mošmondor

---

IEnumerable 实际上非常适合支持无限序列，并且有先例可循。这绝对不是滥用。 - Servy

个人而言，我不认为这是强制的。我甚至认为懒惰列表可以保存潜在的无限数据（也称为“流”）。 - phipsgabler

Answer 4

编辑

经过一天的思考和考虑到@StriplingWarrior的评论，我不得不改变我的看法。昨晚我开始尝试这个方法，现在我想知道如果放弃IList，我真正会失去什么？

我认为更明智的做法是只实现IEnumerable，并声明一个本地的Count()方法，该方法抛出一个NotSupportedException方法来防止枚举器运行，直到发生OutOfMemoryException。我仍然会添加一个IndexOf和Contains方法以及Item索引器属性，以公开更高性能的替代方案，如Binet's Formula，但我可以自由地更改这些成员的签名，使用扩展数据类型，甚至是System.Numerics.BigInteger。

如果我要实现多个系列，我会为这些成员声明一个ISeries接口。谁知道，也许像这样的东西最终会成为框架的一部分。

---

我不同意似乎达成共识的观点。虽然 IList 有许多成员无法为无限序列实现，但它确实有一个 IsReadOnly 成员。如果在某些其他功能的副作用下出现这种情况，那么按照惯例，实现大多数成员使用 NotSupportedException 在 ReadOnlyCollection<> 的情况下似乎是可以接受的。因此，我不明白为什么这样做会不可接受。

在这个具体的斐波那契数列案例中，有已经建立的算法，参见 here 和 here，可以短路正常的累积枚举方法，我认为这将产生显著的性能优势。通过 IList 公开这些好处对我来说是合理的。

理想情况下，.Net 将支持一些其他更适当的超级接口类，与 IEnumerable<> 更接近，但在未来版本中出现之前，这必须是一个明智的方法。

---

我正在实现一个 IList<BigInteger> 来进行说明。

- Jodrell

---

值得注意的是，ICollection<T>.Add 方法和 IList<T>.Item 索引器的文档都指定，如果集合是只读的，则会抛出 NotSupportedException 异常，并且有一个 IsReadOnly 属性，用户可以检查以确定实现在调用这些方法之前是否为只读。另一方面，CopyTo 方法和 Count 属性对于无限集合没有特殊的让步。 - StriplingWarrior

@StriplingWarrior，收到，反思后我已经编辑了我的回答。只是很高兴我不是政治家。 - Jodrell

我知道你的意思。顺便说一下，声明一个本地的 Count() 方法是不足以防止执行的，如果人们将 LINQ 扩展方法与你的对象强制转换为 IEnumerable<>。你的类必须实现 ICollection<> 才能起作用。 :-( - StriplingWarrior

Answer 5

一个无限集合最好实现为 IEnumerable<T>，而不是 IList<T>。在实现时，您还可以使用 yield return 语法，就像这样（忽略溢出问题等）：

public IEnumerable<long> Fib()
{
    yield return 1;
    yield return 1;
    long l1 = 1;
    long l2 = 1;
    while (true)
    {
        long t = l1;
        l1 = l2;
        l2 = t + l1;
        yield return l2;
    }
}

- Steve Czetty

Answer 6

正如@CodeInChaos在评论中指出的那样，IList的Item属性具有签名

T this[ int index ] { get; set; }

我们看到ILists是由int索引的，因此它们的长度受Int32.MaxValue的限制。更大索引的元素将无法访问。这在我写问题时发生了，但我把它留了下来，因为除此之外，这个问题很有趣。

- Colonel Panic

Answer 7

总结我目前所见到的：

你可以实现其中的5个，对于Count()抛出NotSupportedException

我本来会说这已经足够好了，但是正如servy所指出的，对于任何非计算和缓存数字，索引器都非常低效。

在这种情况下，我认为适合你不断计算流的唯一契约是IEnumerable。

你还有另一个选择，就是创建一个看起来很像IList但实际上并不是的东西。

- cjk