15

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

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

我们现在已经实现了只读 IList 所期望的所有方法，除了 Count()。

这很酷，还是滥用 IList？

斐波那契数很快变得不切实际地大（因此见IList<BigInteger>上文）。有界无限序列可能更明智，它可以实现IList<long>or IList<double>。

附录二：斐波那契数列可能是一个不好的例子，因为计算遥远的值是昂贵的——要找到第 n 个值，必须计算所有较早的值。因此，正如 Mošmondor 所说，不妨将其设为 IEnumerable 并使用.ElementAt. 但是，还有其他序列可以快速计算远距离值，而无需计算较早的值。（令人惊讶的是 pi 的数字就是这样一个序列）。这些序列更“listy”，它们真正支持随机访问。

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

4

7 回答 7

17

对于大多数开发人员，IList并ICollection暗示您有一个预先评估的内存中的集合可以使用。IList具体而言，存在恒定时间Add*和索引操作的隐式合同。这就是为什么LinkedList<T>不实施IList<T>。我认为 FibonacciList 违反了这个隐含的合同。

请注意最近 MSDN 杂志文章中的以下段落，该文章讨论了将只读集合接口添加到 .NET 4.5 的原因：

IEnumerable<T>对于大多数处理类型集合的场景来说已经足够了，但有时你需要比它提供的更多的功能：

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

正如其他人所指出的，还有一个问题是你会返回什么.Count。

对于这样的数据集合使用IEnumerable或输入是完全可以IQueryable的，因为人们期望这些类型可以被懒惰地评估。

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

关于编辑 2：如果您计划以索引是恒定时间的方式实现您的序列，那么这很容易解决我的主要观点。不过，Sixlettervariables 的答案仍然成立。

*显然还有更多：只有在返回Add时才有望工作。只有在返回 false 等情况下才可能进行修改，等等。这是一个经过深思熟虑的接口：这个事实最终可以通过在 .NET 4.5 中引入只读集合接口来纠正。IList.IsFixedSizefalseIsReadOnlyIList

更新

考虑到这一点，我个人认为IEnumerable<>s 也不应该是无限的。除了物化方法，如.ToList()，LINQ 有几个非流式操作，如在返回第一个结果之前.OrderBy()必须消耗整个操作。IEnumerable<>由于这么多方法都假设IEnumerable<>s 可以安全地遍历它们，因此产生一个IEnumerable<>本质上不安全的无限期遍历将违反 Liskov 替换原则。

如果您发现您的应用程序经常需要斐波那契数列的片段作为 IEnumerables，我建议创建一个具有类似于 签名的方法Enumerable.Range(int, int)，它允许用户定义开始和结束索引。

如果您想开始一个 Gee-Whiz 项目，您可以想象开发一个基于 Fibonacci 的IQueryable<>提供程序，用户可以在其中使用有限的 LINQ 查询语法子集，如下所示：

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

由于您的查询提供者有权将where子句评估为 lambda 表达式，因此您可以有足够的控制权来实现Count方法，并.GetEnumerator()确保查询的限制性足以产生真正的答案，或者尽快抛出异常该方法被调用。

但这听起来很聪明，对于任何现实生活中的软件来说都可能是一个非常糟糕的主意。

于 2012-07-11T15:16:09.830 回答
2

我想一个符合要求的实现必须是有限的，否则你会返回ICollection<T>.Count什么？

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

另一个考虑因素是CopyTo，在其正常过载下，它永远不会在斐波那契情况下停止。

这意味着斐波那契数列的适当实现将是简单IEnumerable<int>的（使用生成器模式）。（Ab）使用 anIList<T>只会导致问题。

于 2012-07-11T15:16:26.823 回答
1

在您的情况下，我宁愿“违反”IEnumerable并随心所欲地处理yield return.

:)

于 2012-07-11T15:19:27.383 回答
1

无限集合可能最好实现为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;
    }
}
于 2012-07-11T15:23:41.557 回答
1

编辑

根据@StriplingWarrior 的评论，花了一天时间来思考我的回答。我担心我必须做出逆转。我昨晚开始尝试这个，现在我想知道放弃我会真正失去IList什么？

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

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

我不同意似乎是共识的观点。虽然IList有许多成员无法为无限系列实现，但它确实有一个IsReadOnly成员。似乎可以接受，当然在 的情况下ReadOnlyCollection<>，用NotSupportedException. 按照这个先例，我不明白为什么这是不可接受的，如果它是一些其他功能增益的副作用。

在这个特定的斐波那契数列案例中，有已建立的算法，请参见此处和此处，用于缩短我认为会产生显着性能优势的正常累积枚举方法。暴露这些好处IList对我来说似乎是有道理的。

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

我正在研究一个实现IList<BigInteger>来说明

于 2012-07-11T17:09:02.013 回答
1

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

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

我们看到 IList 由整数索引，因此它们的长度受 Int32.MaxValue 的限制。更大索引的元素将无法访问。我在写这个问题时想到了这个问题，但我把它留了下来，因为这个问题换个方式思考很有趣。

于 2012-07-11T20:39:11.807 回答
0

总结一下我目前看到的：

你可以满足 5 出 6，扔NotSupportedException上Count()

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

在这种情况下，我会说唯一适合您持续计算流的合同是 IEnumerable。

您拥有的另一个选择是创建一些看起来很像IList但实际上并非如此的东西。

于 2012-07-11T15:25:26.070 回答