8

これは、モジュールのおよび関数がおよびモジュールの同等物に比べてはるかに遅いという以前の質問へのフォロー アップです。SeqitermapArrayList

ソースを見ると、 や などの一部の関数isEmptyはlength、 を使用する前に配列とリストを最適化するために非常に単純な型チェックを実行することがわかりますIEnumerator。

[<CompiledName("IsEmpty")>]
let isEmpty (source : seq<'T>)  = 
    checkNonNull "source" source
    match source with 
    | :? ('T[]) as a -> a.Length = 0
    | :? list<'T> as a -> a.IsEmpty
    | :? ICollection<'T> as a -> a.Count = 0
    | _ -> 
        use ie = source.GetEnumerator()
        not (ie.MoveNext())

[<CompiledName("Length")>]
let length (source : seq<'T>)    = 
    checkNonNull "source" source
    match source with 
    | :? ('T[]) as a -> a.Length
    | :? ('T list) as a -> a.Length
    | :? ICollection<'T> as a -> a.Count
    | _ -> 
        use e = source.GetEnumerator() 
        let mutable state = 0 
        while e.MoveNext() do
            state <-  state + 1;
        state

同じアプローチの場合iter、パフォーマンスを大幅に向上させることができます。関数をシャドウするiterと、組み込みバージョンよりも大幅に向上しました。

[<CompiledName("Iterate")>]
let iter f (source : seq<'T>) = 
    checkNonNull "source" source
    use e = source.GetEnumerator()
    while e.MoveNext() do
        f e.Current;

私の質問は、Seqモジュール内の一部の関数が特定のコレクション型 (配列、list< T> など) で使用するために最適化されていることを考えると、どうして や などの他の関数がiter同様nthの方法で最適化されなかったのでしょうか?

また、map関数の場合、@mausch が指摘したように、同様のアプローチを採用してEnumerable.Select(以下を参照)、さまざまなコレクション タイプに特化したイテレータを作成することはできませんか?

public static IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector)
    {
      if (source == null)
        throw Error.ArgumentNull("source");
      if (selector == null)
        throw Error.ArgumentNull("selector");
      if (source is Enumerable.Iterator<TSource>)
        return ((Enumerable.Iterator<TSource>) source).Select<TResult>(selector);
      if (source is TSource[])
        return (IEnumerable<TResult>) new Enumerable.WhereSelectArrayIterator<TSource, TResult>((TSource[]) source, (Func<TSource, bool>) null, selector);
      if (source is List<TSource>)
        return (IEnumerable<TResult>) new Enumerable.WhereSelectListIterator<TSource, TResult>((List<TSource>) source, (Func<TSource, bool>) null, selector);
      else
        return (IEnumerable<TResult>) new Enumerable.WhereSelectEnumerableIterator<TSource, TResult>(source, (Func<TSource, bool>) null, selector);
    }

よろしくお願いします。

4

2 に答える 2

4

iterの場合、同じアプローチを実行してパフォーマンスを大幅に向上させることができます

これがあなたの質問への答えだと思います。テストは人為的なものであり、これらの方法の実際の例を実際にテストするものではありません。のタイミングの違いを取得するために、これらのメソッドの10,000,000回の反復をテストしましたms。

アイテムごとのコストに換算すると、次のようになります。

          Array   List
Seq.iter   4 ns    7 ns
Seq.map   20 ns   91 ns

これらの方法は通常、コレクションごとに1回使用されます。つまり、このコストは、アルゴリズムのパフォーマンスに対する追加の線形要因です。最悪の場合、リスト内のアイテムごとの損失が少なくなり100 nsます（パフォーマンスをそれほど気にする場合は使用しないでください）。

これをlength、一般的なケースでは常に線形であるケースと比較してください。この最適化を追加することで、長さを手動でキャッシュするのを忘れた人に大きなメリットをもたらしますが、幸いなことに常にリストが提供されます。

同様に、何度も呼び出すisEmptyことができます。直接質問できるのであれば、別のオブジェクト作成を追加するのはばかげています。（これはそれほど強力な議論ではありません）

覚えておくべきもう1つのことは、これらのメソッドのどちらも実際には出力の複数の要素を調べないということです。次のコードで何ができると思いますか（構文エラーや欠落しているメソッドを除く）

type Custom() =
  interface IEnumerable with
    member x.GetEnumerator() =
      return seq {
        yield 1
        yield 2
      }
  interface IList with
    member x.Item with
      get(index) = index
    member x.Count = 12

 let a = Custom()
 a |> Seq.iter (v -> printfn (v.ToString()))
于 2012-06-05T17:39:28.163 に答える
1

表面的には、型チェックインSeq.length/isEmpty間違いのように見えます。ほとんどのSeq関数は直交性についてそのようなチェックを実行しないと思います: 型固有のバージョンはList/Arrayモジュールに既に存在します。なぜそれらを複製するのですか？

これらのチェックは、直接しか使用しないため、LINQ ではより意味がありますIEnumerable。

于 2012-06-04T22:11:08.327 に答える