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

Question

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

例えば，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;
}

といった手法が有ります．
こういった「実践で使える」アルゴリズムを幅広く知りたいと思っています．

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

Answer 1

ご提示のコードでは（大きな？）偏りが生じる気がします。

int $rnd = rand()%10;

の部分は

int $rnd = $i + rand() % (10 - $i);

とした方がいいかもしれません。

Comments

[nnahito]

ご回答有難うございます．
こういった付加知識も参考になります！
これは，理論的に……何をしているのでしょうか？
その部分もご教授いただければ幸いです．

[退会済みユーザー]

横から失礼します。
このコードはrand()%10によって並べ替えの対象にならなかった要素が無いようにすることが意図だと思われます。
0から$i-1までの要素は$i回目までに位置が決まった要素と考え、
$iから9までの要素をまだ位置が決まっていない要素として扱います。
$i + rand() % (10 - $i)は常に$iから9までの値を取るので、
位置が決まった要素が並べ替えの対象になることはありません。
そして$iはループのたびに増えていくことで位置が決まっていない要素が徐々に減っていくというわけです。
ところで変数名に$が使われているのが気になりました。PHPとCがごっちゃになっているようです。

[IchigoTaruto]

配列の中身をランダムに入れ替える部分で、
ご提示のコードでは、$i と 0～9 のいずれかと交換していますが、
ここは、$i と $i～9 のいずれかと交換するようにした方がより偏りの少ない並び方になると思います。

数学にあまり明るくないので、シミュレーションで試してみたところ
$num[x]にx+1が入る確率がやや高くなるようです。
https://paiza.io/projects/7jNs3b3Iv3BLVEtivT15Kw

細かいことを言い出すと、rand() の戻り値が 0～RAND_MAX なので rand() % 10 は一様ではないかもとか、rand() のアルゴリズムはあまりよくないかもとかあると思います。そのへんの良し悪しについては判断しかねるのですが、その都度求められる精度次第かなと。

[nnahito]

> sbwhitecap　様
ご回答有難うございます．
『並べ替えの対象にならなかった要素が無いようにすることが意図』とのことで，なるほどと思いました．

> IchigoTaruto　様
ご回答有難うございます．
『より偏りの少ない並び方』とのことで，つまりは並べ替えの行われないものをなくすということですね！
ありがとうございます．

[nnahito]

補足ですが，
『ところで変数名に$が使われているのが気になりました。PHPとCがごっちゃになっているようです。』とのことですが，どうなのでしょう…？
最初私も，Cなら$を付けずに変数を定義していました．
が，最近PHPとperlをよく使い，「あれ？$あったほうがわかりやすくね？」となって現在はワザと付けております…
やはり人様が見ると気持ち悪ものですよね……

[IchigoTaruto]

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

[IchigoTaruto]

あと、このコードはC++かと思います。

[退会済みユーザー]

>このコードはC++かと思います
C99からは関数の先頭にまとめて宣言する必要がなくなり、かつ識別子に使える文字種の制限が緩くなっています。ですからこれはCとして合法なコードのはずです。

[IchigoTaruto]

>これはCとして合法なコードのはずです。
失礼しました。手前の環境でコンパイルできなかっただけで早合点してしまいました。
>あと、このコードはC++かと思います。
この発言は取り下げさせていただきます。

[YsMana]

シャッフルの手順って、
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さんが提示している方法と本質的には同じですが、
シャッフルし終わった（位置が決まった）要素を配列の前では無く後ろから並べているところが違います。

[IchigoTaruto]

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

例えば、配列 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

[swordone]

> ご提示のコードの 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個ずつ取り出して並べる，という手法をイメージして下さい．

Answer 2

よくあるやつですが年齢の求め方です。

echo (int)( (20150619 - 19990302) / 10000 );

現在のYmd - 生年月日Ymd / 10000
実装として使えない場合もありますが。。。

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

Comments

[nnahito]

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

Answer 3

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

Comments

[nnahito]

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

Answer 4

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

Comments

[MorimasaMatsuda]

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

[nnahito]

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

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

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

Answer 5

お邪魔します。

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

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

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

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

参考になれば幸いです。

Comments

[nnahito]

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

後「scheme」とは…言語でしょうか…？＾＾；

[ShinpeiYamamoto]

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

Answer 6

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

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

単方向リスト(Singly Linked List)

Comments

[nnahito]

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

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

Answer 7

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

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

例：URL形式のチェック

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

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

Comments

[nanndemoiikara]

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

Laravel Validationより抜粋

[nnahito]

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

Answer 8

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

Comments

[nnahito]

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

[MasaakiIrie]

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

[nnahito]

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

Answer 9

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

Answer 10

katoyさんの意見を支持します。

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

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

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

Comments

[nnahito]

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

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

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