情報アイランド

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

データの間引き

2017/06/29

数年振りにアルゴリズムに興味が出てきた今日この頃。

それはともかく、データの「間引き」という処理があります。

これは簡単に言うと、(2のべき乗の要素を持つ)配列の偶数番目の要素を上に奇数番目の要素を下に並び替えるような処理です。その後、偶数番目のグループと奇数番目のグループの中で再び同じ処理を行います。これを繰り返し行っていきます。

例えば、8個の要素を持つ配列の場合は、

  A0[8] 0 1 2 3 4 5 6 7

  A1[8] 0 2 4 6 1 3 5 7

  A2[8] 0 4 2 6 1 5 3 7

となります。

これを直感的にプログラムすると下のようになるかと思います。

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

    for (int i = a.Length; i >= 4; i = i >> 1)
    {
        int[] b = new int[a.Length];
        for (int j = 0; j < a.Length / i; j++)
            for (int k = 0; k < a.Length / (a.Length / i) / 2; k++)
            {
                b[i * j + k] = a[i * j + k * 2];
                b[i * j + i / 2 + k] = a[i * j + k * 2 + 1];
            }
        a = b;

        a.Display();  //途中表示
    }

    return a;
}

//表示用
public static class Extension
{
    public static void Display(this int[] a)
    {
        Console.WriteLine(a.Select((e) => e.ToString()).Aggregate((w, n) => w + ", " + n));
    }
}

これだけでは分かりにくいかもしれませんので、上の図にループカウンタの動きを加えてみます。下図と上記プログラムをよく見比べれば処理の内容が分かるかと思います。

                       i   j < a.Length / i   k < a.Length / (a.Length / i) / 2

  A0[8] 0 1 2 3 4 5 6 7  i = 8   j = 0          k = 0~3

  A1[8] 0 2 4 6 1 3 5 7  i = 4   j = 0~1         k = 0~1

  A2[8] 0 4 2 6 1 5 3 7  i = 2   j = 0~3         k = 0

16個のデータについて間引きを行う場合は以下のようになります(分かりやすいようにデータの内容は最初の配列aのインデックスと同じにしました)。

public static void Main(string[] args)
{
    int[] a = Enumerable.Range(0, 16).ToArray();

    a.Display();

    int[] b = Mabiki1(a);

    b.Display();
}

さて、この「間引き」処理をより高速に行うことはできないでしょうか?

結論を先に言えば、できます。

偶数番目を上に奇数番目を下に持っていくということは2進数で考えるとどういうことでしょうか?

2進数の最も右のビットが0のものを上に、1のものを下に持っていくということに他なりません。

更に続けて、偶数番目を上に奇数番目を下に持っていくということは、2進数の右から2番目のビットが0のものを上に1のものを下に持っていくということです。

それを繰り返し行うということは、結局、ビット列を反転するということです。

  000 001 010 011 100 101 110 111

最も右のビットが0のものを上に、1のものを下に持っていくと、

  000 010 100 110 001 011 101 111

右から2番目のビットが0のものを上に、1のものを下に持っていくと、

  000 100 010 110 001 101 011 111

ということで、「間引き」=「ビット列の反転」ということになります。

そうすると、データの「間引き」の処理を行うプログラムは、データをその添え字のビット列を反転した順に並び替えれば良いということになります。

この処理を素朴に実装すると以下のようになるかと思います。

public static int[] Mabiki2(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[BitReverse1(i, r)] = a[i];
    return b;
}

public static int BitReverse1(int a, int r)
{
    int b = 0;
    for (int i = 0; i < r; i ++, a = a >> 1 )
        b = (b << 1) + a % 2;
    return b;
}

更に早くしたかったら、1ビットずつ反転→2ビットずつ反転→・・・→16ビットずつ反転という方法を使います。

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;
}

public static uint BitReverse2(uint x, int r)
{
    x = (x & 0x55555555) << 1 | (x & 0xaaaaaaaa) >> 1;
    x = (x & 0x33333333) << 2 | (x & 0xcccccccc) >> 2;
    x = (x & 0x0f0f0f0f) << 4 | (x & 0xf0f0f0f0) >> 4;
    x = (x & 0x00ff00ff) << 8 | (x & 0xff00ff00) >> 8;
    x = (x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16;

    x = x >> (32 - r);

    return x;
}

最後に、上に挙げた3通りのアルゴリズムでどれくらい処理時間が変わるのか計測してみます。

以下のように、それそれのアルゴリズムを使って1024個のデータの「間引き」処理を65536回行った場合の処理時間を計測しました。

Stopwatch stopWatch = new Stopwatch();

stopWatch.Start();

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

    //a.Display();

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

    //b.Display();
}

stopWatch.Stop();

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

Console.ReadKey();

結果は以下のようになりました。

  • Mabiki1・・・10515ms
  • Mabiki2・・・4263ms
  • Mabiki3・・・2899ms

それなりに早くなっていると思います。

(多分続く...)

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

-C#