【アルゴリズム】 数え上げソート

  • 2012.08.28 Tuesday
  • 03:41
JUGEMテーマ:コンピュータ

-------------------------
(追記)
以下のコードはまちがっていました。
-------------------------

数え上げソート
各項目を互い他の項目と比較する。その項目より大きいキーの数によって項目の最終的な位置を決定する。


参考文献によると上記のような処理もソートというらしいです。たとえば、ランダムに整数が格納された配列が合った場合に、数え上げソートで得られる結果は、ソートされた場合に格納されるべきインデックスの配列が得られます。

簡単に実装すると

private static int[] GetOrderingArrary(int[] arrary)
{
    var countedArray = new int[arrary.Length];
    for (int i = 0; i < arrary.Length; i++)
    {
        for (int j = 0; j < arrary.Length; j++)
        {
            if (arrary[i] > arrary[j])
            {
                countedArray[i] += 1;
            }
        }
    }
    return countedArray;
}

上記では重複する値が存在した場合、同じインデックスになってしまうため、
配列内の再配置を行う場合は一工夫必要そうですが、そもそも再配置を行う必要があるのかどうかはアルゴリズムを選択する際に検討するべきですね。

このアルゴリズムは、配列内の変更がないため並列処理で実装が可能となります。
ということで実装してみました。

private static int[] GetOrderingArrary(int[] arrary)
{
    var countedArray = new int[arrary.Length];
    for (int i = 0; i < arrary.Length; i++)
    {
        for (int j = 0; j < arrary.Length; j++)
        {
            if (arrary[i] > arrary[j])
            {
                countedArray[i] += 1;
            }
        }
    }
    return countedArray;
}

private static int[] GetOrderingArrary2(int[] arrary)
{
    var countedArray = new int[arrary.Length];
    for (int i = 0; i < arrary.Length; i++)
    {
        int index = i;
        ParallelEnumerable.Repeat(0, arrary.Length).ForAll(j =>
            {
                if (arrary[index] > arrary[j])
                {
                    countedArray[index] += 1;
                }
            });
    }
    return countedArray;
}

private static int[] GetOrderingArrary3(int[] arrary)
{
    var countedArray = new int[arrary.Length];
    ParallelEnumerable.Repeat(0, arrary.Length).ForAll(i =>
        {
            int index = i;
            ParallelEnumerable.Repeat(0, arrary.Length).ForAll(j =>
                {
                    if (arrary[index] > arrary[j])
                    {
                        countedArray[index] += 1;
                    }
                });
        });
    return countedArray;
}

static void Main(string[] args)
{
    OnTest(10000);
    OnTest(10000);
    OnTest(10000);
    OnTest(10000);
    OnTest(10000);
    OnTest(10000);
    OnTest(10000);
    OnTest(10000);
    OnTest(10000);
}

private static void OnTest(int count)
{
    var stopwatch = new Stopwatch();
    stopwatch.Stop();

    var arrary = Enumerable.Repeat(new Random(), count).Select(r => r.Next()).ToArray();
    Console.Write("Seq:");
    stopwatch.Restart();
    GetOrderingArrary(arrary);
    stopwatch.Stop();
    Console.WriteLine(stopwatch.ElapsedMilliseconds);

    Console.Write("Parallel:");
    stopwatch.Restart();
    GetOrderingArrary2(arrary);
    stopwatch.Stop();
    Console.WriteLine(stopwatch.ElapsedMilliseconds);


    Console.Write("Nested Parallel:");
    stopwatch.Restart();
    GetOrderingArrary3(arrary);
    stopwatch.Stop();
    Console.WriteLine(stopwatch.ElapsedMilliseconds);
}

実行結果は

Seq:303
Parallel:985
Nested Parallel:706
Seq:301
Parallel:788
Nested Parallel:639
Seq:301
Parallel:889
Nested Parallel:788
Seq:299
Parallel:1087
Nested Parallel:512
Seq:297
Parallel:733
Nested Parallel:622
Seq:299
Parallel:986
Nested Parallel:527
Seq:301
Parallel:983
Nested Parallel:498
Seq:300
Parallel:1079
Nested Parallel:481
Seq:296
Parallel:1112
Nested Parallel:478


このソートに速度を求める必要性があるかどうか私には分かりませんが、
比較してみるとシーケンシャルな処理が一番早く、次に並列処理をネストした処理が早く、一番遅かったのがforの中で並列処理を実行する処理でした。並列処理の中でfor文を書いてみるというものあるので気になる方はご自身でお試しください。

---------------
参考文献
The Art of Computer Progoraming 3 【日本語版】

---------------
参考文献に書かれていた処理と実装が異なっていました。
後日改めて紹介します。

----------------
(追記)
下記のコードが正しいようです。下記のロジックでは重複キーが存在した場合でも
先に見つかった方が優先され、安定ソートが実現できます。

static int[] Sort(int[] arrary)
{
    var count = new int[arrary.Length];
    for (int i = arrary.Length - 1; i > 0; i--)
    {
        for (int j = i - 1; j >= 0; j--)
        {
            if (arrary[i] < arrary[j])
            {
                count[j] += 1;
            }
            else
            {
                count[i] += 1;
            }
        }
    }
    return count;
}

コメント
コメントする








    
この記事のトラックバックURL
トラックバック

calendar

S M T W T F S
      1
2345678
9101112131415
16171819202122
23242526272829
30      
<< September 2018 >>

あわせて読みたい

あわせて読みたいブログパーツ

selected entries

categories

archives

recent comment

  • 【キーボード】6年前のRealForceを復活させることはできる!?その3
    art55 (05/22)
  • 【キーボード】6年前のRealForceを復活させることはできる!?その3
    分解大好き (05/18)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    art55 (02/04)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    Gen (02/04)
  • 【キーボード】RealForce が壊れて帰ってきた。
    art55 (04/29)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    art55 (02/23)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    かるあ (02/22)
  • 【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。
    art55 (01/16)
  • 【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。
    karuakun (01/16)
  • 【NetOffice】【Excel】死なないExcelプロセスをKillする。
    art55 (12/05)

recent trackback

recommend

recommend

recommend

C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION)
C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION) (JUGEMレビュー »)
Sasha Goldshtein,Dima Zurbalev,Ido Flatow,サシャ・ゴルドシュタイン,ディマ・ズルバレフ,イド・フラトー

recommend

ろんりと集合
ろんりと集合 (JUGEMレビュー »)
中内 伸光
とてもわかりやすいです。

recommend

recommend

シャノン・ノイマン・ディジタル世界
シャノン・ノイマン・ディジタル世界 (JUGEMレビュー »)
市川 忠男
4章がリレーショナルデータベースな内容になってます。ページ数があまりありませんが、ポイントがものすごく的確にまとまっていて、感動します。

recommend

recommend

東プレ Realforce91UBK-S 静音キーボード 静電容量無接点方式 変荷重 ブラック NG01BS
東プレ Realforce91UBK-S 静音キーボード 静電容量無接点方式 変荷重 ブラック NG01BS (JUGEMレビュー »)

テンキーレス、静音のRealForce91UBK-S。スコスコ感がたまらなく気持ちいいです。家と会社で2台持ってます。

recommend

recommend

プログラミング.NET Framework 第4版 (プログラミングシリーズ)
プログラミング.NET Framework 第4版 (プログラミングシリーズ) (JUGEMレビュー »)
Jeffrey Richter
発売予定美 2013年10月10日。.NET Frameworkとお付き合いする人のバイブルですね。

recommend

recommend

キャット・シッターの君に。
キャット・シッターの君に。 (JUGEMレビュー »)
喜多嶋 隆
私のイラストレータデビュー本です。

recommend

Essential .NET ― 共通言語ランタイムの本質
Essential .NET ― 共通言語ランタイムの本質 (JUGEMレビュー »)
ドン・ボックス,クリス・セルズ,Don Box,Chris Sells,吉松 史彰

links

profile

search this site.

others

mobile

qrcode

powered

無料ブログ作成サービス JUGEM