質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.03%

実践で使える,使っているアルゴリズムを教えて下さい

解決済

回答 10

投稿

  • 評価
  • クリップ 20
  • VIEW 3,697

nnahito

score 1838

実戦向け?なアルゴリズムが知りたいです.
ただ単に「プログラムが書ける!」というだけでは,やはりダメだと思っています.
もっと,プログラムを書くなら,このような手法があるぜ!と言った,知識がほしいです.

例えば,c言語で「1〜10でランダムに重複しない数字を持つ配列」を作成する場合ですと,
#include <stdio.h>
#include <stdlib.h>

int main(){
    int $num[10];
    
    //1から10までの数値を代入
    for (int $i=0; $i<10; $i++){
        $num[$i] = $i+1;
    }
    
    //配列の中身をランダムに入れ替える(擬似的な乱数にする)
    for (int $i=0; $i<10; $i++){
        int $rnd = rand()%10;
        int $temp = $num[$rnd];
        $num[$rnd] = $num[$i];
        $num[$i] = $temp;
    }
    
    //結果を出力
    for (int $i=0; $i<10; $i++){
        printf("$num[%d] = %d;\n", $i, $num[$i]);
    }
    
    return 1;
}
といった手法が有ります.
こういった「実践で使える」アルゴリズムを幅広く知りたいと思っています.

皆さんは普段,どのようなアルゴリズムを愛用していらっしゃいますでしょうか.
よろしければご教授ください.

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 10

checkベストアンサー

+5

よくあるやつですが年齢の求め方です。
echo (int)( (20150619 - 19990302) / 10000 );
現在のYmd - 生年月日Ymd / 10000
実装として使えない場合もありますが。。。

http://d.hatena.ne.jp/alittlething/20070827/p1

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/19 14:58

    ご回答有難うございます.
    そういうものです!!ぜひぜひもっと知識を分けてください!
    よろしくお願いいたします.

    キャンセル

+4

ご提示のコードでは(大きな?)偏りが生じる気がします。
int $rnd = rand()%10;
の部分は
int $rnd = $i + rand() % (10 - $i);
とした方がいいかもしれません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/20 18:22

    シャッフルの手順って、
    1. 10個の要素から1つランダムに選ぶ:0~9の乱数が必要
    2. 残った9個の要素から1つランダムに選ぶ:0~8の乱数が必要
    以下続く、
    という風になるので、生成する乱数の範囲はステップが進むごとに狭くする必要があります。
    適当に入れ替えれば良いと考えるのではなくて、1つずつランダムに選ぶ(ピックアップする)という考え方の方が上手くシャッフルできると思います。

    このようにシャッフルするアルゴリズムとしては
    Fisher–Yates shuffleというアルゴリズムが知られています。
    こんなのです。
    ```lang-C
    for (int $i=9; $i>0; $i--){
    int $rnd = rand()%(i+1);
    int $temp = $num[$rnd];
    $num[$rnd] = $num[$i];
    $num[$i] = $temp;
    }
    ```

    IchigoTarutoさんが提示している方法と本質的には同じですが、
    シャッフルし終わった(位置が決まった)要素を配列の前では無く後ろから並べているところが違います。

    キャンセル

  • 2015/06/20 20:22

    蛇足になるかもしれませんが、
    上手くお伝えできてない感があるので補足させていただきます。


    例えば、配列 int Sq[3] = { 0, 1, 2 } をシャッフルすることを考えます。


    全ての要素について「i番目と0~2番目のいずれかと入れ替える」方法を採ると
    0~2の乱数を3つ使用します。
    とりうるパターンは (0, 0, 0), (0, 0, 1) ... (2, 2, 2) の 27 通り
    それぞれのパターンと、シャッフル後の並びは以下のようになります。

    (0, 0, 0) ==> [2, 0, 1]
    (0, 0, 1) ==> [1, 2, 0]
    (0, 0, 2) ==> [1, 0, 2]
    (0, 1, 0) ==> [2, 1, 0]
    (0, 1, 1) ==> [0, 2, 1]
    (0, 1, 2) ==> [0, 1, 2]
    (0, 2, 0) ==> [1, 2, 0]
    (0, 2, 1) ==> [0, 1, 2]
    (0, 2, 2) ==> [0, 2, 1]
    (1, 0, 0) ==> [2, 1, 0]
    (1, 0, 1) ==> [0, 2, 1]
    (1, 0, 2) ==> [0, 1, 2]
    (1, 1, 0) ==> [2, 0, 1]
    (1, 1, 1) ==> [1, 2, 0]
    (1, 1, 2) ==> [1, 0, 2]
    (1, 2, 0) ==> [0, 2, 1]
    (1, 2, 1) ==> [1, 0, 2]
    (1, 2, 2) ==> [1, 2, 0]
    (2, 0, 0) ==> [0, 2, 1]
    (2, 0, 1) ==> [1, 0, 2]
    (2, 0, 2) ==> [1, 2, 0]
    (2, 1, 0) ==> [0, 1, 2]
    (2, 1, 1) ==> [2, 0, 1]
    (2, 1, 2) ==> [2, 1, 0]
    (2, 2, 0) ==> [1, 0, 2]
    (2, 2, 1) ==> [2, 1, 0]
    (2, 2, 2) ==> [2, 0, 1]

    Sq[0] に入る値を集計してみると

    0 ... 9回
    1 ... 10回
    2 ... 8回

    と、Sq[0] には1が入る確率が高く、2が入る確率が低くなります。
    ちなみに Sq[1] も偏りますが Sq[2] は均一になります。


    全ての要素について「i番目とi~2番目のいずれかと入れ替える」方法を採ると

    0~2, 1~2, 2~2 の乱数を使用します。
    とりうるパターンは 6 通り
    それぞれのパターンと、シャッフル後の並びは以下のようになります。

    (0, 1, 2) ==> [0, 1, 2]
    (0, 2, 2) ==> [0, 2, 1]
    (1, 1, 2) ==> [1, 0, 2]
    (1, 2, 2) ==> [1, 2, 0]
    (2, 1, 2) ==> [2, 1, 0]
    (2, 2, 2) ==> [2, 0, 1]

    と、いずれも入る値の確率は均一になります。


    # 対応表はこれで出しました -> https://paiza.io/projects/DeOvFLhp7p9LQI_V37q6hw

    キャンセル

  • 2015/06/24 18:37 編集

    > ご提示のコードの rand() % 10 が一様だったとしても、シャッフル後の並びは一様ではないということです。
    具体的には $num[0] に 1 が入る確率より 2 が入る確率が 1.2 倍くらい高いようです。
    (どうしてそうなるかは、数学に詳しい方が...)

    これについて説明したいと思います.
    あなたのコードだと,配列の先頭から順に見て,配列の中から1つランダムに選んで
    入れ替えるという操作をしています.
    このため,このシャッフル終了時にnum[0]に1が入るパターンは・・・
    1. num[0]の番の時にnum[0]との入れ替えが起き,その後num[0]が入れ替えの対象にならない
    2. 値1がある位置より後ろの位置との入れ替わりが何回か起き,最終的にnum[0]と入れ替わる
    2.は,最初0番にあった1が3番と入れ替わり,その後3番と6番と入れ替わり,最後に6番と0番が入れ替わる,というようなパターンです.
    この時,1回でも自分自身かそれより前(0番以外)の位置と入れ替わると,0番に戻すことがこのコードでは不可能になります.
    これらを計算して合計すると,確率は0.1となります.
    一方,num[0]に2が入る場合を考えると,2.はほぼそのままですが,値2のあとの位置が8箇所であること,そして何より,
    1'. num[0]の番の時にnum[1]との入れ替えが起きるか,
    num[1]の番の時にnum[0]との入れ替えが起き,
    それ以外でnum[0]が入れ替えの対象にならない
    という条件になります.num[0]=1の時の1.の確率の2倍になります.
    これを計算すると約0.129になります.
    実際の計算結果→http://ideone.com/XSWLlV
    num[0]がシャッフル後1~10それぞれになる確率→http://ideone.com/Z0bh4y

    一方,他の方が提示したコードは,箱のなかに入った10個のボールをランダムに1個ずつ取り出して並べる,という手法をイメージして下さい.

    キャンセル

+3


アルゴリズムは、必要に応じて それなりに google 検索 (英語を毛嫌いせずに) すれば, それなりの情報がえられるはずです。
実践では 設計戦略もとても重要な気がします。
  コーディング規約 ...
  コード履歴管理 ...
  エラー処理 (例外クラスの設計、例外を catch方法の統一、ログ出力の方針) ...
  デザインパターン ....
  ソースコードのlint, 自動テスト、カバレッジ計測 ツール ...

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/21 03:01

    ご回答有難うございます。
    確かに独学故、コーディング規約などは一切勉強したことがありません……
    その辺りも大切ですね

    キャンセル

+2

プログラムを組む際に、扱えると便利なのは、やはり正規表現ですかね・・・。

PHPerなのでC言語ではなくてすみませんが。

例:URL形式のチェック
function is_url($text) {
     if (preg_match('/^(https?|ftp)(:\/\/[-_.!~*\'()a-zA-Z0-9;\/?:\@&=+\$,%#]+)$/', $text)) {
         return TRUE;
     }
     return FALSE;
}

メールアドレスだったり、電話番号だったり、
登録情報の正誤をもとめるときにすごく便利だったり、
スクレピングの時に必要な情報のみを抽出したり、
正規表現が扱えるかどうかで、効率がかなり変わってくると思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/19 17:36

    $url = str_replace(array('http://&#039;, 'https://&#039;, 'ftp://'), '', strtolower($value));
    return ( ( trim($url) !== '' ) ? checkdnsrr($url) : FALSE );

    Laravel Validationより抜粋

    キャンセル

  • 2015/06/21 02:57

    ご回答有難うございます!
    私も専門はBASIC(ActiveBasic)なので大丈夫です←
    正規表現は様々な書き方がありますよね……さらに、言語によって多少異なってきますし……
    勉強せねば

    キャンセル

+2

自分でアルゴリズムを実装するほど高度なことはやっていないので、大抵はライブラリーにあるものを使います。


ただ、とある事情により外部のライブラリーを使えない制限がある中で、これだけはどうしても使いたくて自分で実装したのが、C言語の単方向リストです。削除機能は不要な、ごく単純な実装でしたけれど。

単方向リスト(Singly Linked List)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/21 03:00

    ご回答有難うございます。
    確かに、私もライブラリに頼りがちになってしまいます。
    が、やはり理論はしっかりと学んでみたく、更にそのアルゴリズムの名前を知っておかねばググることもできません。
    なので、せっかくこういったプログラマ用のSNSもあるので質問させて頂いております。

    自分も作ったアウトラインプロセッサのツリービューのデータを保存するのに、ポインタで単方向リストのようなものを作りました……
    木構造は更に難しそうですね…

    キャンセル

+2

お邪魔します。

アルゴリズムといっても、全く同じパターンを書くことはほとんどないのですが。
本当に地味だけど随所に書くようなパターンというと、

ルックアップテーブル - wikipedia
メモ化 - wikipedia
畳み込み加算 - wikipedia
置換表


実践ではあんまり使う機会がまずないけど、アルゴリズムを組み立てる能力を養うのに知ってると良いのは、
不動点コンビネータ - wikipedia
PythonによるYコンビネータの仕組みの(多分)わかりやすい説明 - 時代城年代記

あとは、自分の場合発想を支えているかなと思うのは、scheme触ったときに得た悟り体験ですね。笑


参考になれば幸いです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/21 03:03

    ご回答有難うございます。
    あぁ……こんなにたくさんの情報をありがとうございます。
    すべて全く知りませんでした。
    時間をかけてですが、1から読んでいこうと思います。

    後「scheme」とは…言語でしょうか…?^^;

    キャンセル

  • 2015/06/21 03:59

    schemeはlisp直系の派生言語で、common lispなど、元のlispから色々と言語仕様が膨れ上がってしまったのでそれをそぎ落とした、割と純粋なlispって感じの言語ですね。gaucheとかがschemeの一種です。
    https://ja.wikipedia.org/wiki/Scheme

    キャンセル

+2

そういう方のために、僕が社会人になってから本当に必要だったアルゴリズムだけが勉強できるサイトを個人的に作ってみましたので、よかったらいらしてください。
コードレジュメ http://www.coderesume.com

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/23 23:26

    実践的ということですが対象とするものによりかわります。
     いかに汎用性を持たせるか
     いかに処理時間を短くするか
     いかに組み込みやすくするか
     いかに開発期間を短くするか
     ・・・など
    Cでも、動かすプラットフォームで要求もことなります。
    質問者は、企業でコードを書いている人でしょうか?
    そうでなければ、基礎的な事項から、実際に様々な局面で実践的なアルゴリズムは鍛え上げられていくものです。
    本やネットにあっても実践で使えない場合も多々あります。

    キャンセル

  • 2015/06/24 03:56

    >coderesume 様
    ご回答有難うございます。
    早速登録の方をさせていただきました。

    >MorimasaMatsuda 様
    企業ではありません。しがない情報系のいち学生です。
    『基礎的な事項から、実際に様々な局面で実践的なアルゴリズムは鍛え上げられていくものです。』と御座いますが、例えば研究で必要なプログラムがあるとして、うんうん唸って考えだしたのが、実は「●●の定理」のほうが精度がよく、簡単に実装できる!
    となった場合、すごく時間の無駄ですよね?

    私があげた、数値をランダムに入れ替えるアルゴリズムも、最初は、ランダムな数値を入れて、すでにその数が配列に入っていれば再度乱数をふるという凄まじく無駄なアルゴリズムでした。
    そのような発想が、定理が知りたいのです。

    キャンセル

+1

バリバリ使うのはアニメーションですね。
img[0] = 1.png;
img[1] = 2.png;
anime++;
DrawImage( img[anime%2] );
DrawImage( img[(anime>>2)%2 ];

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/19 16:34

    ご回答有難うございます.
    パッと見てイメージがつかなかったのですが……
    これは何を行っている処理なのでしょうか?

    キャンセル

  • 2015/06/20 21:37

    2枚の画像を交互に描画する処理です。
    animeをビットシフトする事で、切り替えまでの時間を変えれます。

    キャンセル

  • 2015/06/21 02:56

    なるほど!
    DirectXなど、画像処理系はあまりやったことがなかったので少し戸惑いました。
    ビットシフトもそういえばきっちりと理解していないですね……参考になります、ありがとうございます!

    キャンセル

0

少し趣旨からズレているかも知れませんが、Fisher-Yatesシャッフルというものがあります。
上記のシャッフルより精度がいいらしいです(Cではそもそもrandの精度が……という問題が残るので断定できないような気がしてますけど)
以下に、詳しい情報があります。
http://ppp-lab.sakura.ne.jp/ProgrammingPlacePlus/algorithm/other/002.html

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

-2

katoyさんの意見を支持します。
アルゴリズムは、必要に応じて それなりに google 検索 (英語を毛嫌いせずに) すれば, それなりの情報がえられるはずです。 
実践では 設計戦略もとても重要な気がします。

この方の記事で内容を補足しているかもしれません。慌てずにゆっくり読むのをおすすめします。私はとてもよい内容だと思います。
http://d.hatena.ne.jp/nowokay/20110920
http://d.hatena.ne.jp/nowokay/20110922

私個人の意見としては、アルゴリズム基礎を横着せずにきちんと押さえたら、デザインパターンを勉強して欲しいとも思います。アルゴリズム基礎は基本情報試験問題で、自分の理解度を客観的に把握すると良いと思います。私は後者を応用研究に選んだりもしたので、学生の時に学んで良かったと思っています。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/07/05 12:18

    ご回答有難うございます.

    >アルゴリズムは、必要に応じて それなりに google 検索 (英語を毛嫌いせずに) すれば, それなりの情報がえられるはず
    >私個人の意見としては、アルゴリズム基礎を横着せずにきちんと押さえたら、デザインパターンを勉強して欲しいとも思います。

    アルゴリズムを調べるためにも,使うためにも,まずそのアルゴリズム名が必要ですよね.
    そういった情報を集めています.

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.03%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る