情報アイランド

「情報を制する者は世界を制す」をモットーに様々な情報を提供することを目指すブログです。現在はプログラミング関連情報が多めですが、投資関連情報も取り扱っていきたいです。

データの間引き その2

その1:データの間引き

初めに。

もっと早いコードを作ったのですが、オーバーヘッドが大きく、データの数が少ないと却って遅くなってしまいます。

なので、テストコードのパラメータを少し変更します。

以下のように、65536個のデータの「間引き」処理を1024回行った場合の処理時間を計測することにします。

Stopwatch stopWatch = new Stopwatch();

stopWatch.Start();

for (int i = 0; i < 1024; i++)
{
    int[] a = Enumerable.Range(0, 65536).ToArray();

    //a.Display();

    int[] b = Mabiki1(a);  //Mabiki2(a);  //Mabiki3(a);

    //b.Display();
}

stopWatch.Stop();

Console.WriteLine(stopWatch.ElapsedMilliseconds.ToString());

Console.ReadKey();

このテストコードによるMabiki1Mabiki3の結果は以下のようになりました。

  • Mabiki1・・・10349ms
  • Mabiki2・・・5356ms
  • Mabiki3・・・2697ms

さて、これより早くするにはどうすれば良いか、ということですが、前回作ったMabiki3メソッドをよく観察してみましょう。

注目すべきなのは赤色の部分です。

public static int[] Mabiki3(int[] a)
{
    if ((a.Length & (a.Length - 1)) != 0)
        throw new Exception();

    int r = 0;
    for (int i = a.Length; i % 2 != 1; i = i >> 1)
        r++;

    int[] b = new int[a.Length];
    for (int i = 0; i < a.Length; i++)
        b[BitReverse2((uint)i, r)] = a[i];
    return b;
}

プログラムでは至る所で見掛ける普通のforループです。しかも、配列aの要素と配列bの要素は一対一に対応するので、forループの中身は(それぞれのiにおいて)他の部分に依存する部分がなく独立していることが分かります。

つまり、並列化が非常に容易いです。

最近のプロセッサは複数のコアを持っているので、一つのコアに処理を任せるより、それらのコアに処理を分担した方が早いのは確実でしょう。

ということで、Mabiki3メソッドの赤色で示したforループ部分を並列化します。

並列化というと難しそうですが、幸いなことに.NET Framework 4にはTask Parallel Libraryという、処理を複数のコアに分担し複数のコアを有効に使うことが簡単にできる機能が追加されています。

まずはこれを使ってみましょう。

public static int[] Mabiki4(int[] a)
{
    if ((a.Length & (a.Length - 1)) != 0)
        throw new Exception();

    int r = 0;
    for (int i = a.Length; i % 2 != 1; i = i >> 1)
        r++;

    int[] b = new int[a.Length];
    Parallel.For(0, a.Length, (i) =>
    {
        b[BitReverse2((uint)i, r)] = a[i];
    });
    return b;
}

変更したのは赤色の部分だけです。非常に簡単に並列化できます。

テストコードの時間を計ってみると、2466msでした。あまり変わっていないような気もしますが、少しは早くなりました。

因みに、実行した計算機の諸元は以下の通りです。

【Windowsのバージョン】Microsoft Windows NT 6.1.7600.0 (64 ビット)

【CPU】Intel(R) Core(TM) i7 CPU 860 @ 2.80GHz

【ビデオカード】NVIDIA GeForce 8800 GT

【メモリ】4184184KB

次にThreadPoolを使って並列化してみます。以下のようになります。

public static int[] Mabiki5(int[] a)
{
    if ((a.Length & (a.Length - 1)) != 0)
        throw new Exception();

    int r = 0;
    for (int i = a.Length; i % 2 != 1; i = i >> 1)
        r++;

    int[] b = new int[a.Length];

    int N = a.Length;
    int P = 2 * Environment.ProcessorCount;
    int Chunk = N / P;
    AutoResetEvent signal = new AutoResetEvent(false);
    int counter = P;

    for (int c = 0; c < P; c++)
        ThreadPool.QueueUserWorkItem((o) =>
        {
            int lc = (int)o;

            for (int i = lc * Chunk; i < (lc + 1 == P ? N : (lc + 1) * Chunk); i++)
                b[BitReverse2((uint)i, r)] = a[i];

            if (Interlocked.Decrement(ref counter) == 0)
                signal.Set();
        }, c);
    signal.WaitOne();

    return b;
}

一つ注意ですが、データの要素数がPより小さい場合はChunk0となり、逐次実行となります。その場合でもP個のメソッド(ラムダ式)をキューに配置するのは変わりません。そのため、データの要素数がPより小さい場合は無駄が多いでしょう。

Mabiki5を使ったテストコードの時間を計ってみると、1919msでした。Mabiki4よりは0.5秒以上早くなりました。

Pを微調整することでもっと早くできないこともないです。

ここまでの結果を纏めておきます。

  • Mabiki1・・・10349ms
  • Mabiki2・・・5356ms
  • Mabiki3・・・2697ms
  • Mabiki4・・・2466ms
  • Mabiki5・・・1919ms

(多分続く...)

pizyumi
プログラミング歴19年のベテランプログラマー。業務システム全般何でも作れます。現在はWeb系の技術を勉強中。
スポンサーリンク

-C#