えムナウ Blog

えムナウ の なすがまま

目次

Blog 利用状況

ニュース


follow mnow at http://twitter.com


えムナウのプログラミングのページ

INETAJ

書庫

日記カテゴリ

ギャラリ

Linqはすごい? その2

Linqはすごいと信じ込まされているあなた以下のプログラムを見てください。

どれがお気に入りですか?もっといいコードがあったら教えてください。

そして、どの順序で速いと思いますか?

static int[] cal1(int[] arr)

{

    var list =

        from a in arr

        select a;

    var sum = list.Sum();

    var count = list.Count();

    var max = list.Max();

    var min = list.Min();

    return new int[] { sum, count, max, min };

}

static int[] cal2(int[] arr)

{

    int sum = 0;

    int count = 0;

    int max = int.MinValue;

    int min = int.MaxValue;

    foreach (int a in arr)

    {

        sum += a;

        count++;

        if (max < a) max = a;

        if (min > a) min = a;

    }

    return new int[] { sum, count, max, min };

}

static int[] cal3(int[] arr)

{

    return new int[] {

        arr.Sum(),

        arr.Count(),

        arr.Max(),

        arr.Min()

    };

}

 

投稿日時 : 2008年1月24日 15:03

コメントを追加

# re: Linqはすごい? その2 2008/01/24 15:53 nsharp

> どれがお気に入りですか?もっといいコードがあったら教えてください。

ParallelEnumerableを使った cal3 に一票。(・∀・)ノ

ところで、cal1 はなぜに引数(すでにIEnumerable<int>)をselectし直してるのですか?

# re: Linqはすごい? その2 2008/01/24 17:52 シャノン

cal1とcal3の違いがわからない…と言ってみる一方で、その違いこそが問題の本質である気もする。

# re: Linqはすごい? その2 2008/01/24 19:52 えムナウ

シャノンさんがいいことを言った。
しかし、大事だけど本質ではない気がする。

# re: Linqはすごい? その2 2008/01/24 20:42 siokoshou

cal1 で select しなおしてるのもなぜなのかわかりません…。あ! IEnumerable<T> と IList<T> の LINQ コード内での扱いの違いですか!プレビューしか見たことありませんが、配列だったりコレクションだったりすると高速化してたりしますね。

もう cal2 は書きたくないなぁと思うほど限定子の恩恵にあずかっています。
なので cal3 に一票。

#そういえば PLINQ まだ遊んでなかった…。

# re: Linqはすごい? その2 2008/01/24 20:50 siokoshou

>そして、どの順序で速いと思いますか?

cal2, cal3, cal1 でしょうか。
cal2 と cal3 は有意な差はないと予想。cal1 のみ若干遅いのかなぁ。でもほとんど差はなさそう。

# re: Linqはすごい? その2 2008/01/24 22:15 えムナウ

22:1:118

# re: Linqはすごい? その2 2008/01/25 1:05 siokoshou

え~、なんででしょう?しかも、かなり大きな差がつきますね…。
1と3の違いが気になります。

# re: Linqはすごい? その2 2008/01/25 1:38 えムナウ

1000000回ループしたときで測定しています。
キャッシュ効果があるようですね。

# re: Linqはすごい? その2 2008/01/25 1:50 えムナウ

800回位で同じくらいの速さですね。
分析ツールなので誤差一杯ですが。

# re: Linqはすごい? その2 2008/01/25 2:07 えムナウ

データ数は{1,20,4,26,3,21} int6個です。
cal2:cal3 は 1:118 で cal2 が速い。
cal1:cal3 は 少ない回数ではcal3 多い回数ではcal1 が速いです。

# re: Linqはすごい? その2 2008/01/25 2:22 えムナウ

データ件数1000000件1回呼ぶだけ。
175:8:70

# re: Linqはすごい? その2 2008/01/25 14:21 とっちゃん

2と3に結構な差があるんですねぇ...
1が遅くなるのはわかるけど...

2と3の差がすごく大きいのが気になる...

# re: Linqはすごい? その2 2008/01/25 15:22 えムナウ

>2と3の差がすごく大きいのが気になる...
foreach のループで言うと4倍です。
その他の安全策などのオーバーヘッドも入りますので9倍近いのも納得できます。

データ数を減らして外側で同じものを何回も回すとその他の安全策などのオーバーヘッドが強調されて比率はもっと増大します。(実際の業務で同じことを1000000回ってのはないと思いますが)

# Linqはすごい? その3 2008/01/25 15:32 えムナウ Blog

Linqはすごい? その3

# Linqはすごい? その4 2008/01/25 22:28 えムナウ Blog

Linqはすごい? その4

# re: Linqはすごい? その2 2008/01/25 22:59 nsharp

週末モードなので、ゆっくり考えて代案を2つほど出してみますた。(´・ω・`)

案1) Tuple・・・じゃなくて匿名クラスに値をまとめる

  static int[] cal4(int[] arr) {
    var result = arr.Aggregate(
      new {
        Sum  = 0,
        Count = 0,
        Max  = Int32.MinValue,
        Min  = Int32.MaxValue
      },
      (r, v) => new {
        Sum  = r.Sum + v,
        Count = r.Count + 1,
        Max  = v > r.Max ? v : r.Max,
        Min  = v < r.Min ? v : r.Min
      }
    );
    return new[] { result.Sum, result.Count, result.Max, result.Min };
  }

メリット: 配列のiterateが1回で済む。
デメリット: 使い捨てオブジェクトが大量発生。structが使えれば・・・。(つД`)

# re: Linqはすごい? その2 2008/01/25 23:00 nsharp

案2) Applicative Functorとして処理

  static IEnumerable<T3> ZipWith<T1, T2, T3>(this IEnumerable<T1> source1, IEnumerable<T2> source2, Func<T1, T2, T3> selector) {
    using (var e1 = source1.GetEnumerator())
    using (var e2 = source2.GetEnumerator()) {
      while (e1.MoveNext() && e2.MoveNext()) {
        yield return selector(e1.Current, e2.Current);
      }
    }
  }

  static int[] cal5(int[] arr) {
    var funcs = new Func<int, int, int>[] {
      (sum,  v) => sum + v,
      (count, _) => count + 1,
      (max,  v) => v > max ? v : max,
      (min,  v) => v < min ? v : min
    };
    var inits = (IEnumerable<int>) new[] {
      0,
      0,
      Int32.MinValue,
      Int32.MaxValue
    };
    return arr.Aggregate(inits, (results, v) => funcs.ZipWith(results, (f, r) => f(r, v))).ToArray();
  }

メリット: クエリーのまま値を返せる。cal5の戻り値の型がIEnumerable<int>だったら、計算を遅延させられる。
デメリット: 非標準の拡張メソッド(ZipWith)が必要。

・・・というところでしょうか。

# re: Linqはすごい? その2 2008/01/25 23:16 nsharp

> cal5の戻り値の型がIEnumerable<int>だったら、計算を遅延させられる。

reduceだからうそでした。ごめんなさい。

# re: Linqはすごい? その2 2008/01/27 8:38 えムナウ

わんくま勉強会の為回答が遅れていますが、

>foreach のループで言うと4倍です。
>その他の安全策などのオーバーヘッドも入りますので9倍近いのも納得できます。

このことを皆さんが自然に理解してもらえるための記事がその2とその3です。
nsharp の代案はまだ実行していませんが「foreach のループで言うと4倍」を「foreach1回」にするための工夫と思います。
私の意図を正しくくんでいただけたものと思います。

# re: Linqはすごい? その2 2008/01/27 13:21 nsharp

> 「foreach のループで言うと4倍」を「foreach1回」にするための工夫と思います。

案1の方はそうです。

案2の方は、メソッドのシグネチャ(int[] -> int[])に自然に合う内容はどんなものだろうという観点です。
foreachの回数を問題にすれば、ZipWith内で余分なiterateは発生するので、効率は案1ほどよろしくはありません。

「Applicative Functor」と書いてるとおり、実はこれは他言語(Haskell)のコードが元ネタです。

import Control.Applicative

cal :: [Int] -> [Int]
cal = foldl (\results v -> getZipList $ ZipList funcs <*> ZipList results <*> pure v) inits
    where
     funcs = [(+), const . (+1), max, min]
     inits = [0, 0, minBound, maxBound]

# re: Linqはすごい? その2 2008/01/27 16:48 えムナウ

nsharp さん(前回nsharpさん にさんをつけ忘れていたみたいごめんなさい)
Haskell は使ったことがないですねぇ。
Func<int, int, int>[] の発想はいいですねぇ。

# 書いたとおりに動く、信じてるかは関係ない 2008/01/31 11:19 菊池 Blog

書いたとおりに動く、信じてるかは関係ない

# re: Linqはすごい? その2 2008/09/01 19:49 っっ

WebシステムにおけるMVCの意義を理解していれば
LINQは、有用だと感じるのではないでしょうか?
4倍、9倍と言われる、その差が、業務ロジックをも含めて人間が感じる「レスポンスの遅さ」となるのであれば、システムとして問題となるでしょう。
昨今のサーバーのレスポンスは、O/Rマッピングツールを導入した程度で、落ちるものなんでしょうか?
システムの第1命題がレスポンスであれば、
純粋なアセンブラで組むしかないでしょう。
ツールのチョイスは、システム要件に左右される
のではないでしょうか。

# re: Linqはすごい? その2 2008/09/07 13:55 えムナウ

っっさん。
わたしはLinqを使うのをやめようとこういうBlogを書いたわけではないのです。

色々と分かっている方でも速度差に気がつかないで書いてしまう危険性がありデータ数や繰り返し件数によってパフォーマンスの問題が出る場合もあるよと警鐘を鳴らす目的です。

そのためにはLinqはパイプラインであることを正しく理解して使いましょうというのが意図です。

タイトル
名前
URL
コメント