15

.NET のIListは有限でなければなりませんか? クラス FibonacciList を実装するとします。IList<BigInteger>

  • プロパティ Item[n] は、n 番目のフィボナッチ数を返します。
  • プロパティ IsReadOnly は true を返します。
  • フィボナッチ数列が増加しているため、メソッド IndexOf および Contains は簡単に実装できます。数値 m がフィボナッチ数であるかどうかをテストするには、m までのフィボナッチ数列の有限数列を計算するだけで済みます。
  • メソッド GetEnumerator() は正しいことをしています

Count() を除いて、読み取り専用 IList に期待されるすべてのメソッドを実装しました。

これはクールですか、それとも IList の悪用ですか?

フィボナッチ数は非現実的なほど急速に大きくなります (したがってIList<BigInteger>上記)。制限付きの無限シーケンスはより賢明かもしれませIList<long>んIList<double>。

補遺 II: フィボナッチ数列は悪い例かもしれません。遠い値を計算するのはコストがかかるからです。n 番目の値を見つけるには、以前の値をすべて計算する必要があります。したがって、Mošmondor が言ったように、それを IEnumerable にして使用することもできます.ElementAt。ただし、以前の値を計算せずに離れた値をすばやく計算できるシーケンスが他にもあります。(驚いたことに、pi の数字はそのようなシーケンスです)。これらのシーケンスはより「リスト化」されており、ランダムアクセスを真にサポートしています。

編集：無限のIEnumerablesに反対する人は誰もいません。Count() をどのように処理しますか?

4

7 に答える 7

17

ほとんどの開発者には、作業する事前評価済みのメモリ内コレクションがあることを意味しますIList。ICollection具体的にIListは、定数時間Add*とインデックス操作の暗黙の契約があります。LinkedList<T>これがを実装しないIList<T>理由です。FibonacciList は、この暗黙の契約に違反していると考えます。

読み取り専用のコレクション インターフェイスを .NET 4.5 に追加する理由について説明している最近の MSDN マガジンの記事の次の段落に注意してください。

IEnumerable<T>型のコレクションを扱うほとんどのシナリオでは十分ですが、提供される以上の機能が必要になる場合があります。

  • マテリアライゼーション:IEnumerable<T>コレクションが既に使用可能 (「具体化」) されているかどうか、またはコレクションを反復処理するたびに計算されるかどうか (たとえば、LINQ クエリを表す場合) を表現することはできません。アルゴリズムがコレクションに対して複数の反復を必要とする場合、シーケンスの計算にコストがかかると、パフォーマンスが低下する可能性があります。また、後続のパスでオブジェクトが再度生成されるときに ID の不一致が原因で、微妙なバグが発生する可能性もあります。

他の人が指摘しているように、あなたが何のために返すかという問題もあります.Count.

これらの型は遅延評価できることが期待されるため、このようなデータのコレクションに対してIEnumerableorを使用してもまったく問題ありません。IQueryable

編集 1 について:はインターフェイス.Count()によって実装されていません:拡張メソッドです。そのため、開発者は時間がかかる可能性があることを想定する必要があり、アイテムの数を実際に知る必要がない場合に呼び出さないようにする必要があります。たとえば、 にアイテムがあるかどうかだけを知りたい場合は、 を使用することをお勧めします。処理するアイテムの最大数があることがわかっている場合は、 を使用できます。コレクションに 個以上のアイテムがある場合、IEnumerable<T>IEnumerable<T>.Any().Take()int.MaxValue.Count()操作オーバーフローが発生します。したがって、無限シーケンスに関連する危険を軽減するのに役立つ回避策がいくつかあります。明らかに、プログラマーがこれらの可能性を考慮していない場合、それでも問題が発生する可能性があります。

編集2について：インデックス作成が一定時間行われるようにシーケンスを実装することを計画している場合、それは私の主なポイントに非常に簡単に対処します。ただし、Sixlettervariables の答えは依然として当てはまります。

*明らかにこれには他にもあります:が返さAddれた場合にのみ動作することが期待されます 変更は、戻り値が false などの場合にのみ可能です。そもそも、よく考えられていないインターフェイスでした。この事実は、.NET 4.5 での読み取り専用コレクション インターフェイスの導入によって最終的に改善される可能性があります。IList.IsFixedSizefalseIsReadOnlyIList

アップデート

これを少し考えてみた結果、IEnumerable<>s も無限であってはならないという個人的な意見に行き着きました。のようなメソッドの実体化に加えて.ToList()、LINQ にはいくつかの非ストリーミング操作があり、最初の結果を返す前に.OrderBy()全体を消費する必要があります。IEnumerable<>非常に多くのメソッドが s を完全にトラバースしても安全であると仮定しているため、無期限にトラバースすることが本質的に安全でない をIEnumerable<>作成することは、リスコフの置換原則に違反します。IEnumerable<>

アプリケーションでフィボナッチ数列のセグメントを IEnumerables として必要とすることが多い場合は、 のようなシグネチャを持つメソッドを作成することをお勧めしEnumerable.Range(int, int)ます。これにより、ユーザーは開始インデックスと終了インデックスを定義できます。

Gee-Whiz プロジェクトに着手したい場合は、次のように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を実装するのに十分な制御があり、クエリが実際の回答を生成するのに十分な制限があることを確認したり、すぐに例外をスローしたりすることができます。メソッドが呼び出されます。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; }

もう 1 つの考慮事項はCopyTo、通常の過負荷の下では、フィボナッチ ケースで停止することはありません。

これが意味することは、フィボナッチ数列の適切な実装は単純IEnumerable<int>(ジェネレーター パターンを使用) であることです。(Ab) の使用はIList<T>問題を引き起こすだけです。

于 2012-07-11T15:16:26.823 に答える
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

あなたの場合、私はむしろ「違反」IEnumerableして、自分のやり方でやりたいと思いますyield return。

:)

于 2012-07-11T15:19:27.383 に答える
1

編集

@StriplingWarriorのコメントに照らして、私の答えを振り返る日がありました。私は逆転しなければならないことを恐れています。私は昨夜これを試し始めましたが、放棄することで本当に何を失うのでしょうIListか?

が発生するまで列挙子が実行されないようにするメソッドをスローするIEnumerableローカルメソッドを宣言するだけで実装する方が賢明だと思います。私は引き続きandメソッドとインデクサー プロパティを追加して、Binet の Formula などのよりパフォーマンスの高い代替手段を公開しますが、これらのメンバーのシグネチャを自由に変更して、拡張データ型を潜在的に使用することもできます。Count()NotSupportedExceptionOutOfMemoryExceptionIndexOfContainsItemSystem.Numerics.BigInteger

ISeries複数のシリーズを実装する場合は、これらのメンバーのインターフェイスを宣言します。おそらく、このようなものが最終的にフレームワークの一部になるでしょう。

コンセンサスのように見える意見には同意しません。無限IListシリーズには実装できない多くのメンバーがありますが、メンバーはIsReadOnlyあります。確かに の場合、ReadOnlyCollection<>メンバーの大部分を で実装することは許容できるようNotSupportedExceptionです。この先例に従うと、それが機能の他のゲインの副作用である場合、これが受け入れられない理由がわかりません.

この特定のフィボナチ級数のケースでは、確立されたアルゴリズムがあります。こことここを参照してください。これは、通常の累積列挙アプローチを回避するためのものであり、これによりパフォーマンスが大幅に向上すると考えられます。これらの利点を公開することIListは、私には正当化されているようです.

理想的には、.Net は他のより適切なインターフェイスのスーパー クラスをサポートし、それに近いものをサポートしますIEnumerable<>が、それが将来のバージョンで実現されるまでは、これは賢明なアプローチである必要があります。

IList<BigInteger>説明するための実装に取り​​組んでいます

于 2012-07-11T17:09:02.013 に答える
0

これまで見てきたことをまとめると：

あなたは6つのうち5つを満たすことができますNotSupportedException。Count()

おそらくこれで十分だと思いますが、servy指摘したように、インデクサーは、計算されずにキャッシュされた数値に対しては非常に非効率的です。

この場合、継続的な計算の流れに適合する唯一のコントラクトは IEnumerable です。

もう 1 つのオプションは、によく似ているIListが実際にはそうではないものを作成することです。

于 2012-07-11T15:25:26.070 に答える