2

拡張機能を使用して、以下を機能的なスタイルで記述する方法を見つけたいと思っていました。理想的には、この関数型スタイルは、反復/ループ バージョンと比較してうまく機能します。きっと仕方が無いと思います。おそらく、多くの追加の関数呼び出しとスタック割り当てなどが原因です。

基本的に、面倒なパターンは、Predicate に使用する値を計算し、その計算された値を結果のコレクションの一部として再度必要とすることだと思います。

// This is what is passed to each function.
// Do not assume the array is in order.
var a = (0).To(999999).ToArray().Shuffle();

// Approx times in release mode (on my machine):
// Functional is avg 20ms per call
// Iterative is avg 5ms per call
// Linq is avg 14ms per call

private static List<int> Iterative(int[] a)
{
    var squares = new List<int>(a.Length);

    for (int i = 0; i < a.Length; i++)
    {
        var n = a[i];

        if (n % 2 == 0)
        {
            int square = n * n;

            if (square < 1000000)
            {
                squares.Add(square);
            }
        }
    }

    return squares;
}

private static List<int> Functional(int[] a)
{
    return
    a
        .Where(x => x % 2 == 0 && x * x < 1000000)
        .Select(x => x * x)
        .ToList();
}

private static List<int> Linq(int[] a)
{
    var squares =
        from num in a
        where num % 2 == 0 && num * num < 1000000
        select num * num;

    return squares.ToList();
}
4

4 に答える 4

7

Konrad の提案に代わるものです。これにより、二重計算が回避されますが、必要がない場合は平方を計算することも回避されます。

return a.Where(x => x % 2 == 0)
        .Select(x => x * x)
        .Where(square => square < 1000000)
        .ToList();

個人的には、パフォーマンスの違いは、より大きなコンテキストで重要であることがわかるまで気にしません。

(ちなみに、これは単なる例であると想定しています。通常、1000000 の平方根を 1 回計算してから、それと比較するだけで、数ミリ秒を短縮できます。2 つの比較または操作nが必要です。Absもちろんだけど。）

編集:より機能的なバージョンでは、まったく使用しないことに注意してくださいToList。代わりに戻り、発信者が必要に応じてIEnumerable<int>に変換できるようにします。そうでない場合、彼らは攻撃を受けません。最初の 5 つの値のみが必要な場合は、 を呼び出すことができます。その怠惰は、コンテキストによっては、元のバージョンよりもパフォーマンスが大幅に向上する可能性があります。List<T> Take(5)

于 2012-06-21T16:32:32.093 に答える
2

二重計算の問題を解決するだけです：

return (from x in a
        let sq = x * x
        where x % 2 == 0 && sq < 1000000
        select sq).ToList();

とは言っても、これがパフォーマンスの大幅な向上につながるかどうかはわかりません。機能バリアントは、実際に反復バリアントよりも著しく高速ですか? このコードは、自動化された最適化に非常に多くの可能性を提供します。

于 2012-06-21T16:31:11.573 に答える
1

並列処理はどうですか？または、解決策はLINQでなければなりません（遅いと思います）。

var squares = new List<int>(a.Length);

Parallel.ForEach(a, n =>
{
  if(n < 1000 && n % 2 == 0) squares.Add(n * n);             
}

Linq のバージョンは次のようになります。

return a.AsParallel()
  .Where(n => n < 1000 && n % 2 == 0)  
  .Select(n => n * n)
  .ToList();
于 2012-06-21T16:51:00.193 に答える
0

パフォーマンスに関して、反復ソリューションと完全に同等になる機能的なソリューションはないと思います。私のタイミング（以下を参照）では、OPからの「機能的」実装は、反復実装の約2倍遅いようです。

このようなマイクロベンチマークは、あらゆる種類の問題を引き起こす傾向があります。変動性の問題に対処する一般的な戦術は、時間測定対象のメソッドを繰り返し呼び出し、呼び出しごとの平均時間を計算することです。次のようにします。

// from main
Time(Functional, "Functional", a);    
Time(Linq, "Linq", a);    
Time(Iterative, "Iterative", a);
// ...

static int reps = 1000;
private static List<int> Time(Func<int[],List<int>> func, string name, int[] a)
{
    var sw = System.Diagnostics.Stopwatch.StartNew();
    List<int> ret = null;
    for(int i = 0; i < reps; ++i)
    {
        ret = func(a);
    }
    sw.Stop();
    Console.WriteLine(
        "{0} per call timings - {1} ticks, {2} ms",
        name,
        sw.ElapsedTicks/(double)reps,
        sw.ElapsedMilliseconds/(double)reps);
    return ret;
}

1 つのセッションのタイミングは次のとおりです。

呼び出しタイミングごとの機能 - 46493.541 ティック、16.945 ミリ秒
呼び出しタイミングごとの Linq - 46526.734 ティック、16.958 ミリ秒
呼び出しタイミングごとの反復 - 21971.274 ティック、8.008 ミリ秒

他にも多くの課題があります。タイマーの使用によるストローブ効果、ジャストインタイム コンパイラがいつどのように処理を行うか、ガベージ コレクタがコレクションを実行する方法、競合するアルゴリズムが実行される順序、 cpu、OSが他のプロセスをスワップインおよびスワップアウトするなど。

少し最適化を試みました。テストから平方を削除しました (num * num < 1000000) - それを (num < 1000) に変更しました - 入力に負の値がないので安全に見えました - つまり、不等式の両側の平方根を取りました. 驚いたことに、OP のメソッドと比較して異なる結果が得られました。OP 実装の 3 つの実装からの 241,849 と比較して、最適化された出力には 500 項目しかありませんでした。ではなぜ違いが？2 乗したときの入力の多くは 32 ビット整数をオーバーフローするため、これらの余分な 241,349 項目は、2 乗したときに負の数または 100 万未満の数にオーバーフローした数値であり、それでも偶数テストに合格しています。

最適化された (機能的な) タイミング:

呼び出しタイミングごとに最適化 - 16849.529 ティック、6.141 ミリ秒

これは、提案どおりに変更された機能実装の 1 つです。期待どおりに基準を満たした 500 個のアイテムが出力されました。反復ソリューションよりも少ないアイテムを出力するという理由だけで、一見「高速」です。

実装の周りにチェックされたブロックを追加することで、元の実装を OverflowException で爆発させることができます。「反復」メソッドに追加されたチェック済みブロックを次に示します。

private static List<int> Iterative(int[] a)
{
    checked
    {
        var squares = new List<int>(a.Length);

        // rest of method omitted for brevity...

        return squares;
    }
}
于 2012-08-25T16:27:27.913 に答える