アルゴリズムとデータ構造：2分挿入ソート
単純挿入ソートの改良版。単純挿入ソートでは挿入箇所をリニアサーチで探していた。
2分挿入ソートではバイナリサーチで挿入箇所を探している。
データ数が大きい場合に効率的。
[計算量]
O(n2)
[binary_insert_sort.c]
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 /* データ件数 */ int sort[N]; int count; void BinaryInsertSort(void); void output(void); void BinaryInsertSort(void){ int i, sorted, temp, insert; int left, mid, right; for(sorted = 1; sorted < N; sorted++){ insert = sort[sorted]; left = 0; right = sorted; while(left < right){ mid = (left + right) / 2; if(sort[mid] < insert){ left = mid + 1; } else{ right = mid; } ++count; } printf("insert:%d,left:%d \n",insert,left); i = left; while(i <= sorted){ temp = sort[i]; sort[i] = insert; insert = temp; i++; output(); } } } int main(void){ int i; clock_t start,end; srand((unsigned int) time(NULL)); for(i=0; i< N; i++){ sort[i] = rand() % 10 + 1; } printf("Stundy...\n"); output(); printf("Start...\n"); start = clock(); BinaryInsertSort(); end = clock(); printf("End...\n"); output(); printf("Count:%d\n",count); printf("Time:%.2f\n",(double)(end-start)/CLOCKS_PER_SEC); return EXIT_SUCCESS; } void output(void){ int i; printf("sort => ["); for(i=0; i<N; i++){ printf("%d,",sort[i]); } printf("]\n"); }
データ10件の実行結果
./binary_insert_sort Stundy... sort => [10,2,5,9,3,3,6,10,4,6,] Start... insert:2,left:0 sort => [2,2,5,9,3,3,6,10,4,6,] sort => [2,10,5,9,3,3,6,10,4,6,] insert:5,left:1 sort => [2,5,5,9,3,3,6,10,4,6,] sort => [2,5,10,9,3,3,6,10,4,6,] insert:9,left:2 sort => [2,5,9,9,3,3,6,10,4,6,] sort => [2,5,9,10,3,3,6,10,4,6,] insert:3,left:1 sort => [2,3,9,10,3,3,6,10,4,6,] sort => [2,3,5,10,3,3,6,10,4,6,] sort => [2,3,5,9,3,3,6,10,4,6,] sort => [2,3,5,9,10,3,6,10,4,6,] insert:3,left:1 sort => [2,3,5,9,10,3,6,10,4,6,] sort => [2,3,3,9,10,3,6,10,4,6,] sort => [2,3,3,5,10,3,6,10,4,6,] sort => [2,3,3,5,9,3,6,10,4,6,] sort => [2,3,3,5,9,10,6,10,4,6,] insert:6,left:4 sort => [2,3,3,5,6,10,6,10,4,6,] sort => [2,3,3,5,6,9,6,10,4,6,] sort => [2,3,3,5,6,9,10,10,4,6,] insert:10,left:6 sort => [2,3,3,5,6,9,10,10,4,6,] sort => [2,3,3,5,6,9,10,10,4,6,] insert:4,left:3 sort => [2,3,3,4,6,9,10,10,4,6,] sort => [2,3,3,4,5,9,10,10,4,6,] sort => [2,3,3,4,5,6,10,10,4,6,] sort => [2,3,3,4,5,6,9,10,4,6,] sort => [2,3,3,4,5,6,9,10,4,6,] sort => [2,3,3,4,5,6,9,10,10,6,] insert:6,left:5 sort => [2,3,3,4,5,6,9,10,10,6,] sort => [2,3,3,4,5,6,6,10,10,6,] sort => [2,3,3,4,5,6,6,9,10,6,] sort => [2,3,3,4,5,6,6,9,10,6,] sort => [2,3,3,4,5,6,6,9,10,10,] End... sort => [2,3,3,4,5,6,6,9,10,10,] Count:24 Time:0.00
データ1万件の実行結果
./binary_insert_sort Stundy... Start... End... Count:119422 Time:0.17
データ10万件の実行結果
./binary_insert_sort Stundy... Start... End... Count:1527327 Time:18.24
データ100万件だと返ってこなかった。
アルゴリズムとデータ構造：単純挿入ソート
単純挿入ソートはほとんど整列が終わっているデータに対して効率が良い。
安定ソート。内部ソート。基本挿入法ともいう。
[平均計算時間]
O(n2)
[最悪計算時間]
O(n2)
[insertion_sort.c]
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 /* データ件数 */ int sort[N]; int count; void InsertSort(void); void output(void); void InsertSort(void){ int i, sorted, temp, insert; for(sorted=0; sorted < N - 1; sorted++){ insert = sort[sorted + 1]; for(i=0; i<=sorted; i++){ if(sort[i] > insert){ break; } ++count; } while(i <= sorted + 1){ temp = sort[i]; sort[i] = insert; insert = temp; i++; } output(); } } int main(void){ int i; clock_t start,end; srand((unsigned int) time(NULL)); for(i=0; i< N; i++){ sort[i] = rand() % 10 + 1; } printf("Stundy...\n"); output(); printf("Start...\n"); start = clock(); InsertSort(); end = clock(); printf("End...\n"); output(); printf("Count:%d\n",count); printf("Time:%.2f\n",(double)(end-start)/CLOCKS_PER_SEC); return EXIT_SUCCESS; } void output(void){ int i; printf("sort => ["); for(i=0; i<N; i++){ printf("%d,",sort[i]); } printf("]\n"); }
データ10件の実行結果
$ ./insertion_sort Stundy... sort => [9,8,8,5,3,3,10,2,3,7,] Start... sort => [8,9,8,5,3,3,10,2,3,7,] sort => [8,8,9,5,3,3,10,2,3,7,] sort => [5,8,8,9,3,3,10,2,3,7,] sort => [3,5,8,8,9,3,10,2,3,7,] sort => [3,3,5,8,8,9,10,2,3,7,] sort => [3,3,5,8,8,9,10,2,3,7,] sort => [2,3,3,5,8,8,9,10,3,7,] sort => [2,3,3,3,5,8,8,9,10,7,] sort => [2,3,3,3,5,7,8,8,9,10,] End... sort => [2,3,3,3,5,7,8,8,9,10,] Count:16 Time:0.00
データ1万件の実行結果
$ ./insertion_sort Stundy... Start... End... Count:27529798 Time:0.24
データ100万件にしたらレスポンスは返ってこなかった。
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 20931 dela 25 0 7576 4260 292 R 100.0 0.8 2:40.77 insertion_sort
アルゴリズムとデータ構造：コームソート
コームソートは離れた要素を比較・交換して
徐々に距離（ギャップ）を縮めて行く。
荒い目から細かい目ですいていくように
髪をとかすコームが名前の由来らしい。
[計算量]
なぜか本に書いてない。
wikiには『実行速度は、ほぼO(n log n)』とありますが。。。あとで調べる。
[comb_sort.c]
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 /* データ件数 */ int sort[N]; int count; void CombSort(void); void output(int list[]); void CombSort(void){ int i, temp, flag, gap; gap = N; do { gap = (gap * 10) / 13; if(gap == 0){ gap = 1; } flag = 1; printf("gap:%d\n",gap); for(i = 0; i < N - gap; i++){ printf("sort[%d]:%d > sort[%d]:%d\n",i,sort[i], i+gap, sort[i+gap]); if(sort[i] > sort[i+gap]){ flag = 0; temp = sort[i]; sort[i] = sort[i+gap]; sort[i+gap] = temp; output(sort); } ++count; } } while((gap > 1) || flag != 1); } int main(void){ int i; clock_t start,end; srand((unsigned int) time(NULL)); printf("Stundy...\n"); for(i = 0; i < N; i++){ sort[i] = rand() % 10 + 1; } output(sort); printf("<< Start!! >>\n"); start = clock(); CombSort(); end = clock(); printf("<< End!! >>\n"); printf("Count:%d\n",count); printf("Time:%.2f\n",(double)(end-start)/CLOCKS_PER_SEC); return EXIT_SUCCESS; } void output(int list[]){ int i=0; printf("sort => ["); while(1){ printf("%d",list[i]); ++i; if(list[i] == '\0') break; else printf(","); } printf("]\n"); }
データ10件で実行したときのログ
[dela@www20328u sort]$ ./comb_sort Stundy... sort => [4,5,9,5,6,9,9,2,8,6] << Start!! >> gap:7 sort[0]:4 > sort[7]:2 sort => [2,5,9,5,6,9,9,4,8,6] sort[1]:5 > sort[8]:8 sort[2]:9 > sort[9]:6 sort => [2,5,6,5,6,9,9,4,8,9] gap:5 sort[0]:2 > sort[5]:9 sort[1]:5 > sort[6]:9 sort[2]:6 > sort[7]:4 sort => [2,5,4,5,6,9,9,6,8,9] sort[3]:5 > sort[8]:8 sort[4]:6 > sort[9]:9 gap:3 sort[0]:2 > sort[3]:5 sort[1]:5 > sort[4]:6 sort[2]:4 > sort[5]:9 sort[3]:5 > sort[6]:9 sort[4]:6 > sort[7]:6 sort[5]:9 > sort[8]:8 sort => [2,5,4,5,6,8,9,6,9,9] sort[6]:9 > sort[9]:9 gap:2 sort[0]:2 > sort[2]:4 sort[1]:5 > sort[3]:5 sort[2]:4 > sort[4]:6 sort[3]:5 > sort[5]:8 sort[4]:6 > sort[6]:9 sort[5]:8 > sort[7]:6 sort => [2,5,4,5,6,6,9,8,9,9] sort[6]:9 > sort[8]:9 sort[7]:8 > sort[9]:9 gap:1 sort[0]:2 > sort[1]:5 sort[1]:5 > sort[2]:4 sort => [2,4,5,5,6,6,9,8,9,9] sort[2]:5 > sort[3]:5 sort[3]:5 > sort[4]:6 sort[4]:6 > sort[5]:6 sort[5]:6 > sort[6]:9 sort[6]:9 > sort[7]:8 sort => [2,4,5,5,6,6,8,9,9,9] sort[7]:9 > sort[8]:9 sort[8]:9 > sort[9]:9 gap:1 sort[0]:2 > sort[1]:4 sort[1]:4 > sort[2]:5 sort[2]:5 > sort[3]:5 sort[3]:5 > sort[4]:6 sort[4]:6 > sort[5]:6 sort[5]:6 > sort[6]:8 sort[6]:8 > sort[7]:9 sort[7]:9 > sort[8]:9 sort[8]:9 > sort[9]:9 << End!! >> Count:41 Time:0.00 [dela@www20328u sort]$ ./comb_sort Stundy... sort => [4,5,9,5,6,9,9,2,8,6] << Start!! >> gap:7 sort[0]:4 > sort[7]:2 sort => [2,5,9,5,6,9,9,4,8,6] sort[1]:5 > sort[8]:8 sort[2]:9 > sort[9]:6 sort => [2,5,6,5,6,9,9,4,8,9] gap:5 sort[0]:2 > sort[5]:9 sort[1]:5 > sort[6]:9 sort[2]:6 > sort[7]:4 sort => [2,5,4,5,6,9,9,6,8,9] sort[3]:5 > sort[8]:8 sort[4]:6 > sort[9]:9 gap:3 sort[0]:2 > sort[3]:5 sort[1]:5 > sort[4]:6 sort[2]:4 > sort[5]:9 sort[3]:5 > sort[6]:9 sort[4]:6 > sort[7]:6 sort[5]:9 > sort[8]:8 sort => [2,5,4,5,6,8,9,6,9,9] sort[6]:9 > sort[9]:9 gap:2 sort[0]:2 > sort[2]:4 sort[1]:5 > sort[3]:5 sort[2]:4 > sort[4]:6 sort[3]:5 > sort[5]:8 sort[4]:6 > sort[6]:9 sort[5]:8 > sort[7]:6 sort => [2,5,4,5,6,6,9,8,9,9] sort[6]:9 > sort[8]:9 sort[7]:8 > sort[9]:9 gap:1 sort[0]:2 > sort[1]:5 sort[1]:5 > sort[2]:4 sort => [2,4,5,5,6,6,9,8,9,9] sort[2]:5 > sort[3]:5 sort[3]:5 > sort[4]:6 sort[4]:6 > sort[5]:6 sort[5]:6 > sort[6]:9 sort[6]:9 > sort[7]:8 sort => [2,4,5,5,6,6,8,9,9,9] sort[7]:9 > sort[8]:9 sort[8]:9 > sort[9]:9 gap:1 sort[0]:2 > sort[1]:4 sort[1]:4 > sort[2]:5 sort[2]:5 > sort[3]:5 sort[3]:5 > sort[4]:6 sort[4]:6 > sort[5]:6 sort[5]:6 > sort[6]:8 sort[6]:8 > sort[7]:9 sort[7]:9 > sort[8]:9 sort[8]:9 > sort[9]:9 << End!! >> Count:41 Time:0.00
データ1万件の結果
Stundy... << Start!! >> << End!! >> Count:286738 Time:0.00
データ100万件の結果
Stundy... << Start!! >> << End!! >> Count:46666765 Time:0.26
データ1億件の結果
Stundy... << Start!! >> << End!! >> Count:-2023267793 Time:33.89
速い。
コームソート、クイックソートは不安定ソート。
マージソートは安定ソート。
[安定ソート]
- 同等の値があった場合、それらの入れ替えが発生しない。
- 同等なデータのソート前の順序が、ソート後も保存される。
- ソート途中の各状態において、常に順位の位置関係を保っている。
[不安定ソート]
- 同等の値があった場合、それらの入れ替えが発生する可能性がある。
例は名と姓でソートする場合に、通常は姓でソートした後に名でソートする。
同じ姓があった場合、名の方でも五十音順にソートできている。不安定ソートは五十音順に並ばない。
[内部ソート]
ソートされるデータの格納領域を変更して処理を進めていくIn-placeのソート
[外部ソート]
ソートされるデータの格納領域以外に O(n) 以上の一時的な記憶領域が必要であるソートを外部ソート
PHP Apocalipseに行ってきました
2011/12/17 PHPに打ち克って世界をより良くする『PHP Apocalipse』に行ってきました。
[トピック]
- PHPこれからも楽しいよ
- ピザとビールが美味しいかった
- 始めて女子がいる勉強会に参加した
[感想]
スピーカーの皆さんの話がどれも素晴らしく
バラエティーに富んだ内容で非常に楽しかったです。
個人的にとくに印象的だったのは[twitter:@tsuyoshikawa]さんのレガシーコードくだりですね。
レガシーコードを過去の負債とせず遺産にしましょう、自分たちも未来への遺産となるコードを書こう。
自分の今の状況とシンクロする部分が大きいからだと思われますが。
あとは[twitter:@koriym]さんのDIS IS PHP、[twitter:@shirokappa]さんのTelephone Driven Developmentもとてもおもしろかったです。
そしてワールドカフェという形で参加された方々とグループを作ってディスカッションするってことをしたのですが
TDD、スクラムを取り入れて開発している方が結構いらっしゃってドキドキしました。
他にもたくさん刺激を貰えて、とても楽しい勉強会でした。
主催者の[twitter:@tsuyoshikawa]さん、会場運営のかとうさん、他関係者、参加者の皆様お疲れさまでした。
アルゴリズムとデータ構造：マージソート
クイックソートは元データの並びが悪いとバブルソートと同じくらい効率が悪い。
もっと確実に効率の良い方法はないかということでマージソートがありますよ、と。
クイックソートよりも最悪計算量が少ない。
[マージソートの計算量]
最悪：O(N Log N)
[ソースコード：merge_sort.c]
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 8 /* データ件数 */ int sort[N]; int buffer[N]; int count; /* 交換回数 */ void MergeSort(int n, int x[]); void output(int list[],int j,char *name); void MergeSort(int n, int x[]) { int i, j, k, m; if(n <= 1){ return; } m = n / 2; /* ブロックを前半と後半に分ける */ MergeSort(m, x); MergeSort(n - m,x + m); /* 併合（マージ）操作 */ for(i = 0; i < m; i++){ buffer[i] = x[i]; } output(buffer,i,"buffer"); output(x+m,m,"x"); j = m; i = k = 0; while(i < m && j < n){ if(buffer[i] <= x[j]){ x[k++] = buffer[i++]; } else{ x[k++] = x[j++]; } output(sort,N,"sort"); ++count; } while(i < m){ x[k++] = buffer[i++]; output(sort,N,"sort"); } printf("-- result --\n"); output(sort,N,"sort"); printf("\n"); } int main(void){ int i; clock_t start,end; srand((unsigned int) time (NULL)); printf("Standby...\n"); for(i = 0; i < N; i++){ /* ランダムな数値を格納 */ sort[i] = rand() % 10 + 1; } output(sort,N,"sort"); printf("\n<< Start >>\n"); start = clock(); MergeSort(N, sort); end = clock(); printf("\n<< End >>\n"); output(sort,N,"sort"); printf("Count:%d\n",count); printf("Time:%.2f\n",(double)(end-start)/CLOCKS_PER_SEC); return EXIT_SUCCESS; }
データ件数8件、1〜10の乱数を発生させて実行した結果
$ ./merge_sort Standby... sort => [6,10,4,8,2,6,7,5] << Start >> buffer => [6] x => [10] sort => [6,10,4,8,2,6,7,5] -- result -- sort => [6,10,4,8,2,6,7,5] buffer => [4] x => [8] sort => [6,10,4,8,2,6,7,5] -- result -- sort => [6,10,4,8,2,6,7,5] buffer => [6,10] x => [4,8] sort => [4,10,4,8,2,6,7,5] sort => [4,6,4,8,2,6,7,5] sort => [4,6,8,8,2,6,7,5] sort => [4,6,8,10,2,6,7,5] -- result -- sort => [4,6,8,10,2,6,7,5] buffer => [2] x => [6] sort => [4,6,8,10,2,6,7,5] -- result -- sort => [4,6,8,10,2,6,7,5] buffer => [7] x => [5] sort => [4,6,8,10,2,6,5,5] sort => [4,6,8,10,2,6,5,7] -- result -- sort => [4,6,8,10,2,6,5,7] buffer => [2,6] x => [5,7] sort => [4,6,8,10,2,6,5,7] sort => [4,6,8,10,2,5,5,7] sort => [4,6,8,10,2,5,6,7] -- result -- sort => [4,6,8,10,2,5,6,7] buffer => [4,6,8,10] x => [2,5,6,7] sort => [2,6,8,10,2,5,6,7] sort => [2,4,8,10,2,5,6,7] sort => [2,4,5,10,2,5,6,7] sort => [2,4,5,6,2,5,6,7] sort => [2,4,5,6,6,5,6,7] sort => [2,4,5,6,6,7,6,7] sort => [2,4,5,6,6,7,8,7] sort => [2,4,5,6,6,7,8,10] -- result -- sort => [2,4,5,6,6,7,8,10] << End >> sort => [2,4,5,6,6,7,8,10] Count:16 Time:0.00
データ件数を100000000にして実行しても1分弱で
クイックソートのときよりも多い件数でもちゃんと計算できた。
ログが上手く吐けなく前回から随分日が経ってしまった。
x[k++]の挙動を考えれば当たり前なのですが、すぐ気付けなかった。
x[k++] = buffer[i++];ってやってる箇所の直線で
printf("x[%d]:%d = buffer[%d]:%d",k++,x[k++],i++,buffer[i++]);とかやっちゃって。
そりゃもう、結果もめちゃくちゃですよねえ。
これでやっと次に行ける。
プログラマーの転職活動
転職活動でよく聞かれた質問をまとめます。
[デザインパターン]
- GoFパターン各々のメリット・デメリットとなるケースを説明して下さい。※もちろんメリット・デメリットは複数ある。
[アルゴリズム]
[アーキテクチャー]
[ミドルウェア]
- 構築経験のあるサーバ構成について、それに構成に至った経緯を説明して下さい
[DB]
- クラスターインデックスの概要を説明して下さい
- インデックスを使うデメリットを挙げて下さい
- これまでに行ったことのあるパフォーマンスチューニングの具体例を述べて下さい
- レプリケーションの概要を説明して下さい
- シャーディングの概要を説明して下さい
- staticメソッドの利用例を挙げて下さい
- テーブルの行ロックについて
[PHP]
- 高速化を計る上で実施した項目を挙げて下さい
- ヴァージョン4系と5系の違いを説明して下さい
- 5系で導入された項目を可能な限り挙げて下さい
- PHPのオブジェクト指向とJavascriptのオブジェクト指向の違いを説明して下さい
[その他]
[プグラミング] ※紙とかホワイトボードなどに書くいて回答。基本好きな言語でOK
- fizzbuzz
- 再帰を使ったmethod
- 変数a = "abc",変数b = "def"を使って変数cに"fcebda"として代入して出力
- 変数iが1〜100のループを作り、正規表現で3または4が含まれる場合にその数値を出力
過去の実績が自分の一番のアピールになるのは言わずもがな。
実績がなくとも自分のプロダクトを公開して、見せられるようにした方がいい。
次回の転職活動ではこのような質問をされないレベルになっていたい。
全文検索エンジンgroongaを囲む夕べ 2に行ってきました
現在、在籍中の企業のオフィスがある中目黒から徒歩15分。
神泉にあるVOYAGE GROUPのオフィスで開催された
全文検索エンジンgroongaを囲む夕べ 2 #groonga : ATNDに行ってきました。
会場がオシャレ過ぎて入るのを躊躇してしまった。
こんな素敵な会場を提供してくれるVOYAGE GROUPさんは素敵！
どのくらい素敵かはこちら => 株式会社 VOYAGE GROUP に行ってきた！ - 941::blog
groongaは検索エンジンなのに索引を動的構築してるということで
リアルタイム検索で活用できます。
HTTPでしゃべれたり、既存のストレージエンジンと組み合わせたりなど
色々な使い方ができ、基本的にパフォーマンスも良く参照・更新が高速です。
そういえば今度MariaDBにgroongaがバンドルされそうですよ！かっこいい！
勉強会に合わせて新しいバージョンがリリースされて
これまで、サポートしていなかったステートメントに対応したなど多々できることが増えたようです。
お知らせ — Groonga v9.0.2ドキュメント
Mroonga - mroonga 1.10リリース
実際導入するにあたっては冗長化、負荷分散、復旧対応などを解決できればかなり良さそう。
MySQLの国産ストレージエンジンSpiderを使えばそれらも実現でき現実的に導入できそうです。
Spiderの作者の斯波さんはgroongaにも携わっておられました。今日知りました。
Spiderについてはわかりやすいのはコレとか Spider DeNA Technology Seminar #2
公式 => SpiderForMySQL.com
さて、とりあえずインストールしないと始まらない。
昼間も別のサーバーに入れたので本日2度目。
[マニュアル]
http://groonga.org/ja/docs/install.html
[環境]
さくらVPS CentOS release 5.7
[手順]
1.レポジトリ追加
$ su - # rpm -ivh http://packages.groonga.org/centos/groonga-repository-1.0.0-0.noarch.rpm
2.インストール
# yum install groonga
※マニュアルではyum updateをした後にインストールするように書いてありますが、
この環境ではyum updateしたくないものが多数あるのでスキップ。
3.確認
# groonga --version groonga 1.2.8 [linux-gnu,x86_64,utf8,match-escalation-threshold=0,nfkc,mecab,epoll]
って感じです。
そして今回の勉強会でnode用ライブラリーであるnroongaっていうのを知りましたので
これ使ってみたいと思います。
groongaの索引動的構築とwebsocketは相性が良さそうですよね。
GitHub - nroonga/nroonga: A library for building Groonga powered nodes
