移動しました。http://delaemon.hatenablog.jp/

ここまでに出て来たソート、サーチのプログラムは全て数値のみを対象として 操作されていたが、もちろん配列でも同じように書けるよ的な応用。 本の検索がお題。[book_seach.c] #include <stdio.h> #include <stdlib.h> #define N 5 typedef struct { char *title; char *author</stdlib.h></stdio.h>…

ニ分探索。 配列の真ん中の値と探している値を比較、それを繰り返すことでターゲットを絞って行く。 対象となる配列がソートされている必要がある。 データ量が少なかったり、ソートする時間がない場合はリニアサーチにしましょう。 [計算量] O(log N) [bina…

リニアサーチは配列の先頭から順番に調べて行って探している数字と同じであればキーを返す。 単純挿入ソートで使った方法。逐次探索、線形探索とも言う。C++標準ライブラリのfind()が相当する。 [計算量] O(N) [linear_search.c] #include <stdio.h> #include <stdlib.h> #inclu</stdlib.h></stdio.h>…

時間を使ったソート。 今年ちょっと話題になって初めてブログで見たときは、お〜なるほど〜って感じだった。 いつ使うの？と聞かれると、まだわからないとしか言えないけど、何かに使えるはず。 WindowsだったらSleepはミリ秒でスレッド実行できるようなので…

鳩の巣ソート(pigeonhole sort)なんていうのがあるらあしいですよ。 でもバケットソートの方が一般的だし、効率も良いよ。 [計算時間] O(n)高速、安定ソート [bucket_sort.c] #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 /* データ件数 */ int sort[N]; int</time.h></stdlib.h></stdio.h>…

何個かソートの実装例を書いてきたけど その中で最適なソートとはどれなのか。 安定ソート、不安定ソート、内部ソート、外部ソート、O(n2)、O(n log n)。 判断基準は状況によるが、処理するデータ量で考えると 大量のデータの場合はO(n log n)のクイックソー…

単純挿入ソートの改良版。単純挿入ソートでは挿入箇所をリニアサーチで探していた。 2分挿入ソートではバイナリサーチで挿入箇所を探している。 データ数が大きい場合に効率的。[計算量] O(n2) [binary_insert_sort.c] #include <stdio.h> #include <stdlib.h> #include <time.h> #defin</time.h></stdlib.h></stdio.h>…

単純挿入ソートはほとんど整列が終わっているデータに対して効率が良い。 安定ソート。内部ソート。基本挿入法ともいう。 [平均計算時間] O(n2) [最悪計算時間] O(n2) [insertion_sort.c] #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 /* データ件数 */ int </time.h></stdlib.h></stdio.h>…

コームソートは離れた要素を比較・交換して 徐々に距離（ギャップ）を縮めて行く。 荒い目から細かい目ですいていくように 髪をとかすコームが名前の由来らしい。 [計算量] なぜか本に書いてない。 wikiには『実行速度は、ほぼO(n log n)』とありますが。。…

2011/12/17 PHPに打ち克って世界をより良くする『PHP Apocalipse』に行ってきました。[トピック] PHPこれからも楽しいよ ピザとビールが美味しいかった 始めて女子がいる勉強会に参加した [感想] スピーカーの皆さんの話がどれも素晴らしく バラエティーに富…

クイックソートは元データの並びが悪いとバブルソートと同じくらい効率が悪い。 もっと確実に効率の良い方法はないかということでマージソートがありますよ、と。 クイックソートよりも最悪計算量が少ない。[マージソートの計算量] 最悪：O(N Log N) [ソース…

転職活動でよく聞かれた質問をまとめます。[デザインパターン] GoFパターン各々のメリット・デメリットとなるケースを説明して下さい。※もちろんメリット・デメリットは複数ある。 [アルゴリズム] クイックソート、マージソートの概要・特徴・計算量を説明し…

現在、在籍中の企業のオフィスがある中目黒から徒歩15分。 神泉にあるVOYAGE GROUPのオフィスで開催された 全文検索エンジンgroongaを囲む夕べ 2 #groonga : ATNDに行ってきました。 会場がオシャレ過ぎて入るのを躊躇してしまった。 こんな素敵な会場を提供…

[クイックソートのロジック] 1.ある値を基準として、それより大きい値は後ろ、小さい値は前へ移動 2.2つのグループそれぞれでまた適当な値を基準にして大きい値は後ろ、小さい値は前へ移動 3.またそれぞれのグループで同じ様に、1-2を繰り返す 4.グループ分…

プログラマーとしてもう1STEP進むために 自分がよく理解できていない、データ構造とアルゴリズムの勉強を始めました。 実務でいつ使うの？と聞かれても納得してもらえる説明ができるようにしたいと思います。この本が良さげだったのでそれに沿って進めます。…

python -mは標準モジュールにいろいろな機能を提供してくれて便利。カレントディレクトリをhttpで公開 $ python -m SimpleHTTPServer Serving HTTP on 0.0.0.0 port 8000 ...これだけで公開できる。1ページしかない時でスピード重視ならこれでいいじゃない。…

jasmineのnodejs版を使ってみました。 CoffeeScriptでもテストできそう。 jasmine自体使ったことないのでまずは基本から。 1.npmでインストール $ npm install -g jasmine-node 2.プロジェクトフォルダの直下にlibとspecというフォルダを作成 $ cd myproject…

前回のnode-devもですが、寄り道して見つけたのってすぐ忘れそうなのでメモ。 foreverはnodejsスクリプトをデーモン化するツール。 死活監視して死んでいたら再起動してくれる。1.npmでインストール $ npm install forever -g2.foreverコマンドでアプリを起…

コードを編集=>アプリ再起動をいちいち手動でやってました、すみません。 node-devはそれらを自動で行ってくれるモジュールです。ちょっと楽チン。 [インストール] ※すでにnodejs、npmがインストールされている状態 1.npmでnode-devをインストール $ npm ins…

WEB+DB編集編のインタービューで増井さんがwikiをランダムで表示して復習している、 とおっしゃっていたので、いいなと思い自分で作ってみました。 本当はChrome Appとして作ってたんだけど クレジットカードの都合上、公開できるまでに時間がかかりそうだっ…

これまで再帰ってあまり使っていいものではないという認識でいたのですが、 ただの無知だったのでこんな感じで書けるよ的なメモ。 <script type="text/javascript"> var i = 1; function fizzbuzz(){ if((i % 15) == 0) alert("FizzBuzz"); else if((i % 3) == 0) alert("Fizz"); else if((i…

commonjsでライブラリー作ったことある？という質問に対して きっぱりとありません！（というかcommonjsってなんだっけ？）という感じで答えましたよ。 実はあったりして。無知ですみませんでした。 アクセスして来た端末がスマフォかどうかチェックする正規…

完全にネタです。 YAPC::Asiaでmixiさんが出されていた広告に書かれていたPerlが 気になってたら、ネタが明かされたいたのでマネしてやってみました。 http://alpha.mixi.co.jp/blog/?p=3668Perlの文字列は2つの文字列の論理演算で表現することができるらし…

リリース直後からチェックしてましたが 触っていなかったのこの機会に環境をセットアップ。 [環境] サーバ：さくらVSP OS：CentOS 5.7 x86_64 1.mergurialをインストール easy_install mercurial2.goをインストール hg clone -u release https://go.googleco…

もうすぐ、というか前夜祭なら明日からYAPC::Asia！！ ということでタイムテーブルを眺めていたら「SmartPhone development 」 という講演がありまして、CoffeeScriptというキーワードがあったので触ってみました。 実行速度もほぼ変わらないそうで、まあコ…

テストデータを大量に作る際、サブクエリやシェルを書いたりしてましたが ストアドプロシージャを使って作ってみました。参考URL http://d.hatena.ne.jp/IT7C/20100801/1280596927 DROP PROCEDURE insert_generate_series; DELIMITER ]] CREATE PROCEDURE in…

何を今更というツッコミもあるでしょうが、先輩エンジニアに 『ふぃずばずって知ってる？』 って聞かれまして、まあ、知りませんでしたのでいろんな言語の書き方を調べて 見てみて自分でも書いてみました。

python環境を整えて触っていきたいなと思ったので、 perlbrewのpython版、pythonbrewを使ってpython-2.7.2にして Django1.3.1をインストールしてみます。 [環境] サーバ：さくらVSP OS：CentOS 5.7 x86_64 1.pythonbrewをインストール curl -kLO https://git…

Perlを書いてWebアプリを作ってみたいと思ったので環境を構築。 perlbrewというツールでperlのバージョン管理ができ、 cpanmでモジュールを入れるのが割と最近の傾向らしい。 それらと一緒に一番有名であろうフレームワークCatalystも入れてみる。 [環境] サ…