アルゴリズムとデータ構造：クイックソート
[クイックソートのロジック]
1.ある値を基準として、それより大きい値は後ろ、小さい値は前へ移動
2.2つのグループそれぞれでまた適当な値を基準にして大きい値は後ろ、小さい値は前へ移動
3.またそれぞれのグループで同じ様に、1-2を繰り返す
4.グループ分けが出来なくなった時点で終了
[計算量のオーダ]
作業の効率性を比較する指標。
[クイックソートの計算量]
最良：O(N Log N)
最悪：O(N2)
平均：O(N Log N)
[ソースコード：quick_sort.c]
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 /* データ件数 */ int sort[N]; /* 対象データリスト */ int cnt; /* 交換回数 */ void output(void); void QuickSort(int bottom, int top, int *data); void QuickSort(int bottom, int top, int *data){ int lower, upper, div, temp; /* 再帰処理を終了するために必要 */ if(bottom >= top){ return ; } /* 先頭の値を適当な値とする */ div = data[bottom]; for(lower = bottom, upper = top; lower < upper;){ /* 閾値より大きい数を持つ配列番号を小さい配列番号から順に検索 */ while(lower <= upper && data[lower] <= div){ lower++; } /* 閾値より小さい数を持つ配列番号を大きい配列番号から順に検索 */ while(lower <= upper && data[upper] > div){ upper--; } /* 配列番号が以下の条件に合えば入れ替え発生 */ if(lower < upper){ temp = data[lower]; data[lower] = data[upper]; data[upper] = temp; output(); } ++cnt; } /* 最初に選択した値を中央に移動する */ temp = data[bottom]; data[bottom] = data[upper]; data[upper] = temp; output(); /* 配列の先頭まで繰り返す */ QuickSort(bottom, upper - 1, data); /* 配列の最後尾まで繰り返す */ QuickSort(upper + 1, top, data); } int main(void){ int i; time_t t; srand((unsigned int) time(NULL)); printf("Standby...\n"); for(i = 0; i < N; i++){ /* 配列にランダムな値を格納 */ sort[i] = rand() % 10; } printf("Before => "); output(); printf("Start:%ld\n",time(&t)); QuickSort(0, N - 1, sort); printf("End:%ld\n",time(&t)); printf("After => "); output(); printf("Count:%d\n",cnt); return EXIT_SUCCESS; } void output(void){ int i; for(i = 0; i < N; i++){ printf("%d,",sort[i]); } printf("\n"); }
データ件数10件、10未満の乱数を発生させて実行結果
$ ./quick_sort Standby... Before => 2,9,0,7,8,0,3,7,1,0, Start:1322690066 2,0,0,7,8,0,3,7,1,9, 2,0,0,1,8,0,3,7,7,9, 2,0,0,1,0,8,3,7,7,9, 0,0,0,1,2,8,3,7,7,9, 0,0,0,1,2,8,3,7,7,9, 0,0,0,1,2,8,3,7,7,9, 0,0,0,1,2,7,3,7,8,9, 0,0,0,1,2,7,3,7,8,9, 0,0,0,1,2,3,7,7,8,9, End:1322690066 After => 0,0,0,1,2,3,7,7,8,9, Count:9
ロギングをコメントアウト、乱数の制限も解除、データ件数を1万件にして実行
$ ./quick_sort Standby... Before => Start:1322690264 End:1322690264 After => Count:31519
すごく速いのでもっと件数を増やしてみる。
1000万件でやっと処理時間が1秒を超えた。
$ ./quick_sort Standby... Before => Start:1322690412 End:1322690416 After => Count:54921891
改修予定
- 処理時間をマイクロ秒で出力する
- 引数をデータ件数にする
C言語の標準関数のqsortは処理系によって異なりますが
おおよそクイックソートで実装されているそうです。
クイックソートは基本的にN Log Nの計算量で効率が良いが
元のデータの並び方が悪いとバブルソートと同じ計算量になってしまう。
確実に効率よくソートする方法はないか？ということで
次回のマージソートに続きます。
アルゴリズムとデータ構造：バブルソート
プログラマーとしてもう1STEP進むために
自分がよく理解できていない、データ構造とアルゴリズムの勉強を始めました。
実務でいつ使うの？と聞かれても納得してもらえる説明ができるようにしたいと思います。
この本が良さげだったのでそれに沿って進めます。
- 作者: 紀平拓男,春日伸弥
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2011/03/26
- メディア: 単行本
- 購入: 15人 クリック: 255回
- この商品を含むブログ (31件) を見る
それでは1章のソートから。
まず最初に出て来たのはバブルソート。
名前の由来は泡が水面に上がっていくように、
大きな数から順に整理されて行くところからきているそうです。
bubble_sort.c
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 /* データ件数 */ int sort[N]; /* 対象データリスト */ int cnt; /* 計算回数 */ void BubbleSort(void); void output(void); void BubbleSort(void){ time_t t; printf("Start:%ld\n",time(&t)); int i, j, flag, k = 0; do { flag = 0; for(i = 0; i < N - 1 - k; i++){ if(sort[i] > sort[i + 1]){ flag = 1; j = sort[i]; sort[i] = sort[i + 1]; sort[i + 1] = j; output(); } ++cnt; } ++k; } while(flag == 1); printf("End:%ld\n",time(&t)); } int main(void){ int i; srand((unsigned int) time(NULL)); printf("Standby.....\n"); for(i = 0; i < N; i++){ sort[i] = rand() % 10; } printf("Before => "); output(); BubbleSort(); printf("After => "); output(); printf("Count:%d\n",cnt); return EXIT_SUCCESS; } void output(void){ int i; for(i=0; i < N; i++){ printf("%d,",sort[i]); } printf("\n"); }
実際、本に書いてあるソースコードとソートのロジックは同一ですが
ロギングのために関数や変数を追加しています。
あと対象のデータとなる乱数を目視でわかりやすいように10未満にしました。
まず、どのようにデータが整理されて行くか
10個のデータ数で確認。
$ ./bubble_sort Standby..... Before => 7,2,7,3,7,7,9,9,5,4, Start:1322660011 2,7,7,3,7,7,9,9,5,4, 2,7,3,7,7,7,9,9,5,4, 2,7,3,7,7,7,9,5,9,4, 2,7,3,7,7,7,9,5,4,9, 2,3,7,7,7,7,9,5,4,9, 2,3,7,7,7,7,5,9,4,9, 2,3,7,7,7,7,5,4,9,9, 2,3,7,7,7,5,7,4,9,9, 2,3,7,7,7,5,4,7,9,9, 2,3,7,7,5,7,4,7,9,9, 2,3,7,7,5,4,7,7,9,9, 2,3,7,5,7,4,7,7,9,9, 2,3,7,5,4,7,7,7,9,9, 2,3,5,7,4,7,7,7,9,9, 2,3,5,4,7,7,7,7,9,9, 2,3,4,5,7,7,7,7,9,9, End:1322660011 After => 2,3,4,5,7,7,7,7,9,9, Count:44
計算回数が多い、らしい。
なんとなくバカっぽいけど、
他のソートを試してないとそこは実感できないですよね。
データ件数表すをNを1万以上にすると
結果が返らなくなりました。
とりあえず1万で実行。
データの整理経過のoutput()をコメントアウトしてロギングをせず、
乱数も10未満という制限を外し、（10未満の数で1万件でも時間があまりかからなくて、動いてる感がしなかったので）
Nを10000に設定して実行。
$ ./bubble_sort Standby..... Before => Start:1322660666 End:1322660667 After => Count:49993725
この方法じゃあ更に大量のデータは処理しきれないので
もっと効率のいい方法はないか？
ということで次回超有名クイックソートに続きます。
python -mでSimpleHTTPServerを使う
python -mは標準モジュールにいろいろな機能を提供してくれて便利。
カレントディレクトリをhttpで公開
$ python -m SimpleHTTPServer Serving HTTP on 0.0.0.0 port 8000 ...
これだけで公開できる。1ページしかない時でスピード重視ならこれでいいじゃない。
同じディレクトリにindex.htmlを作っておけばちゃんと読み込まれる。
<!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <title>SimpleHTTPSserver</title> </head> <body> <p>Hello World!!</p> </body> </html>
python -m を使わない場合起動するためだけにファイル作る、ひと手間が発生。
simplehttp.py
import SimpleHTTPServer
SimpleHTTPServer.test()
pythonのシェルで実行するものをそのまま書いただけ。
$ python simplehttp.py Serving HTTP on 0.0.0.0 port 8000 ...
他にもpython -mでsmtpとか簡単に立てれるなどなど。
http://answer.pythonpath.jp/questions/506/python-m
jasmine-nodeを使ってテスト
jasmineのnodejs版を使ってみました。
CoffeeScriptでもテストできそう。
jasmine自体使ったことないのでまずは基本から。
1.npmでインストール
$ npm install -g jasmine-node
2.プロジェクトフォルダの直下にlibとspecというフォルダを作成
$ cd myproject $ mkdir lib $ mkdir spec
libにテスト対象となる実コード、specにスペックファイルを置く。
3.簡単なサンプルを作成
lib/MyClass.js
exports.MyClass = (function(){
return {
list:[1,2,3]
}
})();spec/MySpecs.js
var MyClass = require('../lib/MyClass').MyClass;
describe('MyClass', function() {
it('lengthプロパティで配列長を取得する事ができる', function() {
expect(MyClass.list.length).toEqual(3);
});
});describeメソッド：クラス名など
itメソッド：テスト対象の振る舞い
expectメソッドの引数にテスト対象
toXXXXメソッドの引数に期待値を記述 https://github.com/pivotal/jasmine/wiki/Matchers
4.テスト実行
$ jasmine-node spec/MySpecs.js Started . Finished in 0.001 seconds 1 test, 1 assertion, 0 failures
5.必要があれば初期化、終了処理など。
spec/MySpecs.js
var MyClass = require('../lib/MyClass').MyClass;
describe('MyClass', function() {
beforeEach(function() {
// 初期処理
});
it('テスト１', function() {
expect(テスト対象).toEqual(評価値);
});
it('テスト２', function() {
expect(テスト対象).toEqual(評価値);
});
});beforEach：各itメソッド呼び出しの前に毎回実行される
afterEach：各itメソッドが実行された直後に毎回実行される
次回CoffeeScriptでテスト。
nodejsスクリプトをデーモン化するforever
前回のnode-devもですが、寄り道して見つけたのってすぐ忘れそうなのでメモ。
foreverはnodejsスクリプトをデーモン化するツール。
死活監視して死んでいたら再起動してくれる。
1.npmでインストール
$ npm install forever -g
2.foreverコマンドでアプリを起動
$ forever start app.js info: Running action: start info: Forever processing file: app.js
forever --helpで見た限りでは一般的な操作感。
稼働しているスクリプト一覧。稼働時間も見れていいかも。
$ forever list data: uid command script forever pid logfile uptime data: [0] QEn5 node app.js 29253 29254 /user_name/.forever/QEn5.log 0:0:0:2.492
指定したスクリプトを停止
$ forever stop app.js
稼働している全てのスクリプトを停止
$ forever stopall
などなど。
オプションも色々あって
-m で起動する回数が指定できたり
-l でログの出力先ファイルが指定できました。
$ forever start -l /var/log/forever.log -m 2 app.js
ちなみに-mは1を指定すると最初の起動もカウントされていて、
次回停止時に再起動はされません。
nodejsからAPIとしても使えて
他の言語で書いたスクリプトをデーモン化するなどできるようです。
あとで死活監視はどうやってるのか見てみないと。
使った感じはリアルタイムだったのでプロセスが死んだら
トリガーみたいなの走るのかな？
nodejsでロードバランサーを作る記事を見かけたので
foreverと組み合わせたらいいかも。
node-devをインストールして使ってみる
コードを編集=>アプリ再起動をいちいち手動でやってました、すみません。
node-devはそれらを自動で行ってくれるモジュールです。ちょっと楽チン。
[インストール]
※すでにnodejs、npmがインストールされている状態
1.npmでnode-devをインストール
$ npm install node-dev npm WARN prefer global node-dev@0.1.9 should be installed with -g node-dev@0.1.9 ./node_modules/node-dev
はじめてnpmでWARNを見た。
どうやら-gオプションでグローバルインストールしなさいと。
グローバルインストールは複数のアプリから共通で使いそうなパッケージを共通のパスに保存します。
- gオプションなしでインストールしたものはローカルインストールになりカレントディレクトリのnode_modules内に保存されます。
2.グローバルインストール
$ npm install -g node-dev
[使ってみる]
1.ターミナルを2つ立ち上げる
2.node-devでアプリを起動
$ node-dev wiki/app.js 11 Nov 08:45:54 - [INFO] Started //アプリ起動したよ、のログ
3.空いているターミナルでapp.jsを変更して保存。コメント入れるだけとか。でも画面にも何か変更が現れるものだと確認しやすいかも。
そうするとさっきアプリを起動した方のターミナルを確認すると再起動された模様。
11 Nov 08:46:40 - [INFO] Restarting //アプリ再起動したよ、のログ
これで少し楽に開発できるよ、と。
wikiで復習
WEB+DB編集編のインタービューで増井さんがwikiをランダムで表示して復習している、
とおっしゃっていたので、いいなと思い自分で作ってみました。
本当はChrome Appとして作ってたんだけど
クレジットカードの都合上、公開できるまでに時間がかかりそうだったのでWebに移植。
とりあえず自分のbookmarkに入っていたwikiページを保存してあります。
nodejs + express + jade + mongooseを使いました。
mongodbにシェルでデータを登録したのですが
アプリでコレクションからデータが取れないなと思ったら
"bookmark" というモデルはコレクションになると"bookmarks"になるようです。
リファクタとか不味いsocket.ioの使い方をしてるので直します。
