【本】最強最速アルゴリズマー養成講座

  • 2012.10.17 Wednesday
  • 19:57
評価:
高橋 直大
ソフトバンククリエイティブ
¥ 2,940
(2012-09-29)
コメント:衝動買い(笑)

JUGEMテーマ:コンピュータ
 
ぜんぜん別の本を探していたのに、本屋さんから出ると、なぜか買っている自分がいました・・・。

「プログラミングコンテストというと、極めて敷居の高いものと想像している方が非常に多いです。実際、日本の参加者が増えてきたのは、ここ数年です。ですが、プログラミングコンテストは、むしろ初学者が積極的に取り組むべきものであり、プログラミング学習や、計算機科学の学習に積極的に用いられるべきものです。」

 はじめにという章に上記のように書かれています。私のようなヘボプログラマがいうのもなんですが、全くその通りだと思います。
 私が独学でプログラミングを勉強し始めた頃は、教えてくれる人もいなかったので、ネット掲示板やSNSなんかで自分の書いたコードをアップして、どこがわるいだのと、あーしたらいいだのと、おまえはプログラマに向かないとか(笑)、暴言混じりにご指導(?)いただいたものです。
 社会人プログラマにとってコードを書く時間というのは、かなり少ないと思います。また誰かに見てもらうという時間もほとんどないのではないかと思います。それが、初学者となればなおさらです。自ら進んで学習しようにも手取り足取り指導が必要で、さらに何をすれば良いかこまめな指導と、自分が解決すべき課題などがないと、どうしようもなく、これらの問題をクリアーできずに挫折してしまう人、つまりプログラマをあきらめる人が多いのではないかと思います。「やる気さえあればなんとかなる。」なんてアドバイスを何度も後輩にしたこともありますが、戦場がないのに戦える訳もありません。まったく知らないし過度な期待をしているかもしれませんが、個人的には「プログラミングコンテスト」というのは、自分を鍛えられる戦場となりうるものじゃないか!って思うわけです。

・・・だから衝動買いしてしまいました。









あああ・・・・重要な点を見落としてた・・・これ英語だ(涙)

【アルゴリズム】挿入ソートをC#を使って実装する。

  • 2012.10.02 Tuesday
  • 22:44
JUGEMテーマ:コンピュータ

以前に書いた挿入ソートが間違えたままだったので、改めて書きました。今回はあってると思います。

 public static void Sort(int[] arrary)
{
    for (int i = 1; i < arrary.Length; i++)
    {
        int tmp = arrary[i];
        if (arrary[i - 1] > tmp)
        {
            int j = i;
            for (; j > 0 && arrary[j - 1] > tmp ; j--)
            {
                arrary[j] = arrary[j - 1];
            }
            arrary[j] = tmp;
        }
    }
}

単なる感想なのですが、個人的には挿入ソートは非常にわかりにくいアルゴリズムだと思います。その理由の一つが配列のデータ構造が手続きを面倒にしているからです。

具体的には下記の部分

 for (; j > 0 && arrary[j - 1] > tmp ; j--)
{
    arrary[j] = arrary[j - 1];
}

配列の各要素を一つずつシフトさせているところです。これ線形リストであれば、すんなりと挿入できるわけですが、配列なのでひとつひとつ取り出しては一つ後の要素に移動させているわけです。こういうのは直感的でない印象を受けます。あと、本当に印象なのですが、「これでうまくソートできるの?」と、不安になってしまいます。本当に個人的な感想なんですが・・・。

これも絵にしたらわかりやすそうだなーって思いますが、機会があれば・・・。

※配列に対してシフト演算子とかあったら「おもしろい」かも(笑)何かの言語ではあったようななかったような・・・。

---------------------------
(追記)
・このソート法を、「ふるい分けの手法」「沈殿の手法」と呼ぶこともあるらしいです。

【雑記】自分で考えなくきゃダメだね〜。

  • 2012.09.05 Wednesday
  • 00:41
JUGEMテーマ:コンピュータ
 
「The Art of Computer Programming 3 【日本語版】」に書かれている挿入ソートのアルゴリズムを元にC#でコードにおおしてみたんだけど・・・なんか違いますね。てか、明らかに間違っていますね。

たとえ正しく書かれている文章があったとしても、自分の頭の中で整理して、理解しない状態で、コピペもどきな事をすると劣化コピーでしかないって事を実感しました。

        static void Sort(int[] arrary)
        {
            for (int j = 1; j < arrary.Length; j++)
            {
                int r = arrary[j];
                for (int i = j - 1; i >= 0; i--)
                {
                    if (r >= arrary[i])
                    {
                        arrary[i + 1] = r;
                        break;
                    }
                    arrary[i + 1] = arrary[i];
                }
            }
        }

「The Art of Computer Programming 3 【日本語版】」の最初の方に、ソートの重要な応用がいくつか紹介されています。これまで自分が書いたコードの中にも、該当するケースもあったと感じたので、読み始めた訳なんですが、どうも方向性がかわってきて、どうやったら自分が納得のいく理解を得られるかという点に執着してしまっている気がします。まあ、それでもいっか・・・とりあえず続けてみよ。

【アルゴリズム】図で解説する「分散数え上げソート」

  • 2012.09.02 Sunday
  • 12:06
JUGEMテーマ:コンピュータ
 
分布数え上げソート

分布数え上げソートは、ソート元の配列の末尾の値から、以下の処理を繰り返す事で、ソートされた配列をえるこがでいます。以下の処理とは、

カウンタテーブルを用意する。
ソート後の配列の入れ物を用意する。
配列に格納された値に対して、カウンタテーブルにソート後のインデックスを問い合わせ、ソート後の配列に値を格納します。

1.カウンタテーブルを用意する。
「カウンタテーブルを用意する」に関しての詳細を説明します。カウンタテーブルは、値に対して、ソート後のIndexを教える仕組みです。カウンタテーブルは、配列で実装します。手順は以下の通りです。

1.1.ソート元の配列の最小値から最大値までが格納可能な配列(カウンタテーブル)を用意する。
最小値MINが配列要素の0の位置になり、最大値MAXが配列要素のMAX - MIN - 1となるような配列を用意します。

分布数え上げソート
今回の例では、最小値が0で最大値が5なので、カウンタテーブルは6つの要素を6個の要素を持つ配列を生成することになります。また、C#では値型の配列の要素の初期値は指定しないと0になるので初期化する必要はありませんが、後の処理のため要素を0にしておく必要があります。

1.2.ソート前の配列の値をカウンタテーブルに数え上げます。

分布数え上げソート
今回の例では、
0は2個あるので、カウンタテーブルの0番目の要素の値は2
1は1個あるので、カウンタテーブルの1番目の要素の値は1
2は0個あるので、カウンタテーブルの2番目の要素の値は0
3は3個あるので、カウンタテーブルの3番目の要素の値は3
4は0個あるので、カウンタテーブルの4番目の要素の値は0
5は2個あるので、カウンタテーブルの5番目の要素の値は2

1.3.カウンタテーブルを累積個数にする。
N番目の要素の値を、0からN番目の値の合計に変換します。累積させることにより、たとえばソート前の3という値は、ソート後の3〜5のインデックスに配置されるということが分かるようになります。

分布数え上げソート
カウンタテーブルの0番目の要素は、0未満の要素がないので、累積個数は2個
カウンタテーブルの1番目の要素は、2 + 1 で、累積個数は3個
カウンタテーブルの2番目の要素は、2 + 1 + 0 で、累積個数は3個
カウンタテーブルの3番目の要素は、2 + 1 + 0 + 3 で、累積個数は6個
カウンタテーブルの4番目の要素は、2 + 1 + 0 + 3 + 0 で、累積個数は6個
カウンタテーブルの5番目の要素は、2 + 1 + 0 + 3 + 0 + 2 で、累積個数は8個

ということで、カウンタテーブルの作成は完了です。

2.ソート後の配列の入れ物を用意する。
2.1.ソート前の配列の末尾からカウンタテーブルに配置先を問い合わせて再配置していきます。
さらに、カウンタテーブルは、問い合わされたインデックスの値をデクリメントします。

末尾から処理を行うのは、安定ソートを実現するためです。先頭からおこなった場合、重複キーが存在した場合、重複キー内で順序が逆順になってしまいます。










ソート元の配列の要素の値が、カウンタテーブルのインデックスに対応し、対応したカウンタテーブルの要素の値がソート後の配列のインデックス、つまり格納先になります。

これで、最終的には以下のようになります。



「分散数え上げソート」のお絵かき終わり!

C#で実装すると下記のようになります。


public static int[] Sort(int[] arrary)
{
    int max = arrary.Max();
    int min = arrary.Min();

    // 配列のインデックスがarraryの個々の値 - minに対応する配列を用意する。
    // 言語仕様により配列の要素が0になっていることを期待している。
    // ex) arraryが{-1,4,4,5}の場合は、{0,0,0,0,0,0,0}という配列を用意される。
    var countTable = new int[max - min + 1];

    // arraryの要素の値をcountTableの添え字と見立てて、countTableにarraryの値の分布を作成
    // ex) arraryが{-1,4,4,5}の場合は、{1,0,0,0,0,2,1}という配列になる。
    foreach (int value in arrary)
    {
        countTable[value - min]++;
    }

    // 分布を累積分布に変換する。
    // ex) arraryが{-1,4,4,5}の場合は、{1,0,0,0,0,2,1}から{1,1,1,1,1,3,4}という配列になる。
    for (int i = 0; i < countTable.Length - 1; i++)
    {
        countTable[i + 1] += countTable[i];
    }

    var result = new int[arrary.Length];
    for (int arraryIndex = arrary.Length - 1; arraryIndex >= 0; arraryIndex--)
    {
        // arrayの要素の値からcountTableを参考に、結果の配列の格納先の添え字を決定する。
        // 使用したcountTableの要素の値を、使用した目印をつけるため1デクリメントする。
        int countTableIndex = arrary[arraryIndex] - min;
        countTable[countTableIndex] -= 1;
        int resultIndex = countTable[countTableIndex];

        result[resultIndex] = arrary[arraryIndex];
    }
    return result;
}

【アルゴリズム】C#で分布数え上げソートの実装する

  • 2012.08.29 Wednesday
  • 19:30
JUGEMテーマ:コンピュータ

----------------------------
【アルゴリズム】図で解説する「分散数え上げソート」
追記しました。
----------------------------

分布数え上げソート

public static int[] Sort(int[] arrary)
{
    int max = arrary.Max();
    int min = arrary.Min();

    // 配列のインデックスがarraryの個々の値 - minに対応する配列を用意する。
    // 言語仕様により配列の要素が0になっていることを期待している。
    // ex) arraryが{-1,4,4,5}の場合は、{0,0,0,0,0,0,0}という配列を用意される。
    var countTable = new int[max - min + 1];

    // arraryの要素の値をcountTableの添え字と見立てて、countTableにarraryの値の分布を作成
    // ex) arraryが{-1,4,4,5}の場合は、{1,0,0,0,0,2,1}という配列になる。
    foreach (int value in arrary)
    {
        countTable[value - min]++;
    }

    // 分布を累積分布に変換する。
    // ex) arraryが{-1,4,4,5}の場合は、{1,0,0,0,0,2,1}から{1,1,1,1,1,3,4}という配列になる。
    for (int i = 0; i < countTable.Length - 1; i++)
    {
        countTable[i + 1] += countTable[i];
    }

    var result = new int[arrary.Length];
    for (int arraryIndex = arrary.Length - 1; arraryIndex >= 0; arraryIndex--)
    {
        // arrayの要素の値からcountTableを参考に、結果の配列の格納先の添え字を決定する。
        // 使用したcountTableの要素の値を、使用した目印をつけるため1デクリメントする。
        int countTableIndex = arrary[arraryIndex] - min;
        countTable[countTableIndex] -= 1;
        int resultIndex = countTable[countTableIndex];

        result[resultIndex] = arrary[arraryIndex];
    }
    return result;
}

とりあえず実装しなおしてみた。


----------------------------
タイトルを「分散数え上げソート」から「分布数え上げソート」に変更しました。
参考にしていた書籍には分散という言葉が使われていましたが
一般的には「分布」という言葉で表現されているようです。

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

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

【アルゴリズム】【書籍】「アルゴリズム」のキホン

  • 2012.08.26 Sunday
  • 04:46
評価:
杉浦 賢
ソフトバンククリエイティブ
¥ 1,575
(2011-03-18)
コメント:図があってとてもわかりやすい。

JUGEMテーマ:コンピュータ

最近、小難しい本ばかり読んでいたので、ちょっと嗜好を変えて、
自分の頭でもわかる範囲の本に触手を伸ばしてみました。

「アルゴリズム」のキホン

アルゴリズムを学習する上で必要となる概念・考え方・手続きなどのポイントを丁寧に列挙しています。
さらに図もまじえることで、脱落者0人を目指しているんじゃないかと
思えるほどアルゴリズムの基本を丁寧に解説しています。

この本は特定のプログラミング言語を使ってアルゴリズムを紹介するといった系統の本ではありません。
(強いて言うとCを念頭に記述されている部分が少しだけあると感じました。)
よって、プログラミング言語を知らない人間が、この本を読んでも、ソートアルゴリズムのいくつかを
実装できるようになるなという事はないでしょう。

私自身はアルゴリズムを実装することでプログラミングになれる、つまりコードをとにかく書く、
わからないときは写経するといった手段でプログラミングを覚えてましたが、
純粋にアルゴリズムを勉強したいのであれば、このような本を読んでみて
コードを書くことだけでは感じられないものを感じるのも重要ではないかと思います。

私のようなコード書きたがりな人が見落としてた部分を気づかせてくれるものがあるかもしれません。

ああ、そうそう、内容は初級者向けだと思います。
たとえば最大値を求めるアルゴリズムを紹介するのに見開き2ページを費やしています。
さらに最小値を求めるアルゴリズムも最大値とは別に見開き2ページです。
あとは察してください。

私自身は、この本を自分は読むべきだと感じたので買って読んでみました。
もちろん読んだ後は読んで良かったと思いました。
この本を読むと別の「イチバンやさしい理工系シリーズ」も読みたくなってきます。きっと罠です。

【アルゴリズム】ソートのメモ

  • 2012.07.19 Thursday
  • 22:08
JUGEMテーマ:コンピュータ

http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88

上記のWikiを見ながら今まで得た知識をまとめたり、
再考察してみたりしています。

グラフを勉強したくてアルゴリズムの本を買ったのに、ソートから抜け出せません。
前に勉強したときはそこまで面白いとは思わなかったのに
めっちゃ面白いですね。ソート(笑)

以下はメモ
ーーーーーーーーーーーーーーーーーーー
ソートとは、データの集合を一定の規則に従ってならべること。
(感想)大小関係以外の規則でもOKってことですね。

小さい値から大きい値に並べる事を昇順と呼ぶ。
大きい値から小さい値に並べる事を降順と呼ぶ。
(感想)時々どちらがどちらかわからなくなります。右左、西東みたいに・・・自分だけ?

データ構造によって使われるアルゴリズムは異なる。
(感想)前々から、データ構造によってアルゴリズムって違うよね?って疑問におもってたんですが
やっぱりそうですよね・・・配列のソートだからバブルソートとかできるわけで、インデックスでアクセスできなようなデータ構造にはバブルソートできないわけだし。

出力によってアルゴリズムは異なる。
(感想)別のIEnumerable<T>インスタンスを返すようなソートもあるわけで、その場合は、アルゴリズム変わりますね。

情報工学や計算機科学での入門題材としてのソートは親しまれている。
分割統治法、データ構造、乱択アルゴリズム、計算量解析、O記法、時間と空間のトレードオフ、下限など
(感想)何を目的にアルゴリズムを学ぶかっていうのはポイントだと思います。また教える側も何を目的にアルゴリズムを教えるのか、または利用するのかって大事ですね。私が、はじめてアルゴリズムを学んだときはifとかforなどの制御文になれるために、アルゴリズムを利用したといった感じでした。

ソートアルゴリズムの分類(計算機科学)
・安定ソート
・内部ソートと外部ソート
・比較ソート
・計算量
・手法
・再帰
(感想)多くのソートアルゴリズムに親しんでくると分類してみたくなりますね。正確に分類して、利点や欠点など人に説明できるくらいにはなりたいと思います。今はソートの名前も正確に言えない状況です。・・・精進あるのみ。

calendar

S M T W T F S
1234567
891011121314
15161718192021
22232425262728
293031    
<< October 2017 >>

あわせて読みたい

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

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