アルゴリズムを体で覚えてみる 幅優先探索(BFS)

幅優先探索（Breadth First Search）の目的は

* Graph: VertexとEdgeの組み合わせ
* 探索の起点(Source): 起点となるVertex

を与えられた時に、
Sourceから他のすべてのVertexへの

* 最短距離と
* その経路

を求めることのようです。

まずGraph, Vertex, Edgeってなんぞやって話ですが、
Vertexはいわゆるノード(下の図で言うと"東京", "大阪", "仙台", "札幌")で、
Edgeは"東京-大阪", "東京-仙台", "札幌-大阪"間を結ぶ線のことです。
でGraphは下の図全体って感じです。

図: Graphサンプル

サンプルプログラム

def init(graph):
    import sys
    for vertex in graph.vertices:
        vertex.color = Vertex.WHITE
        vertex.distance = sys.maxint
        vertex.parent = None

def bfs(graph, source):
    init(graph)
    source.color = Vertex.GRAY
    source.distance = 0
    source.parent = None

    queue = [source]
    while len(queue) > 0:
        origin = queue.pop(0)
        for target in graph.adjacency_of(origin):
            if target.color == Vertex.WHITE:
                target.color = Vertex.GRAY
                target.distance = origin.distance + 1
                target.parent = origin
                queue.append(target)
           origin.color = Vertex.BLACK

もちろんエントリーポイントはbfs(graph, source)です。
こいつに、graphと探索の起点となるsourceを渡しています。
ざっと眺めてなんじゃこれと思うのは、 Vertex.WHITEやVertex.GRAY、Vertex.BLACKじゃないでしょうか？
それぞれ、

* WHITE: まだ探索されていないVertex
* GRAY: 探索はされたが近隣のVertexの少なくとも一つはWHITE
* BLACK: 近隣のVertexがすべてGRAYもしくはBLACKになった。

を意味します。

アルゴリズムの全体の流れは、

1. graph内のすべてのvertexを初期化(init関数)する。
    (色をWHITE, 距離をinfinity,  親をNoneにする)
2. 起点(source)を探索済み、距離0、親Noneに設定する。
3. 起点をキューにいれ、起点の近隣Vertexが未探索であれば探索済みにして、キューに入れる

て感じです。
この各Vertexで計算されたdistanceが最短距離となり、
各Vertexのparentをたどることで最短距離経路がわかることとなります。

例えば、↑のGraphサンプル図で"東京"を起点として探索して見ると、

1. 東京を探索済みにする。（距離0、親 なし）
2. 東京の近隣の大阪、仙台を探索済みにする。（距離1、親 東京）
3. 大阪の近隣の東京、札幌を探索するが、
    東京は探索済みなので札幌のみ探索。（距離2、 親 大阪）
4. 仙台の近隣の探索をするが、東京は探索済みなので何もしない。

なんで最短経路になるの？

証明の流れは、
その1. δ(s, v) ≤ δ(s, u) + 1
  起点をs、graph内の任意のVertexをu, vとして、δ(s, u)をs=>uまでの最短距離とした時、
  u => vへのEdge(u, v)があれば、↑が成り立つことを証明。
その2.  v.d ≥ δ(s, v)
  BFSで計算した距離は最短距離以上であることを証明
その3. Queue(v1.d, v2.d, ...., vn.d), v1.d ≤ v2.d ≤ ... ≤ vn.d ≤ v1.d + 1
  キューの中にv1, v2, ..., vnが入っていた場合
  常にv1.d ≤ v2.d ≤ ... ≤ vn.d ≤ v1.d + 1
  が成り立つことを証明。

そして最終的にv.d > δ(s, v)となると仮定し、
その矛盾を解くことv.d = δ(s, v)であることを証明する。


その1の証明
帰納法を使うのですが、ざっくりというと、
uまでの最短距離δ(s, u)が成り立っている時、
vが未探索の場合はδ(s, v) = δ(s, u)+1となる。（サンプルコードの20行目）
すでに探索済みの場合は、δ(s, v) ≤ δ(s, u)となる。
（探索済みということはdistanceは単調増加なのでuよりdistanceが短いはずですからね）

その2の証明
これまた帰納法を使うようですが、
vの一個手前のVertex uまではu.d ≥ δ(s, u)が成り立つとすると、
v.d = u.d + 1 ≥ δ(s, u) + 1 ≥ δ(s, v)
が成り立つ。

その3の証明
これまた帰納法で証明します。
v1.d ≤ v2.d ≤ ... ≤ vn.d ≤ v1.d + 1が成り立っている時、
  1. v1をQueueから削除した時、v2.d ≤ ... ≤ vn.d ≤ v2.d + 1が成り立つことを証明する
    v1.d ≤ v2.d から v1.d + 1 ≤ v2.d + 1 が成り立つ。
    そこから↑が成り立つことが言える。
  2. 次にv(n+1)を入れた時にv2.d ≤ ... ≤ vn.d ≤ v(n+1).d ≤ v2.d + 1が成り立つことを証明する
    v(n+1).d = v1.d + 1 ≤ v2.d + 1なので、成り立つといえる。


・・・ということで、
あるvにおいてv.d > δ(s, v)となってしまったとします。
その直前のVertex uではu.d = δ(s, u)が成り立っているとすると、
v.d > δ(s, v) =  δ(s, u) + 1 = u.d + 1
が成り立つ。

vがWHITEの時、v.d = u.d + 1より↑の式と矛盾する。
vがBLACKの時、その３の証明よりv.d ≤ u.dから↑の式と矛盾する。
vがGRAYの時、すでにQueueに入っているので、v.d = w.d + 1となるwが必ず存在する。
wはuより前にdequeueされているのでv.d = w.d + 1 ≤ u.d + 1よってこの場合も矛盾する。

ということでv.d >δ(s, v)となるvは存在しないので、すべてのVertex vにおいて、
v.d = δ(s, v)といえます。

全然関係ないですが・・・

なんか"探索"って割りには目的物がはっきりしないので
ほんとに"探索"なのか？と思いましたが、
どうも探索で合ってるらしい（当たり前か・・・ずっと探索と呼ばれてますしね）。

ざっくりとですが、

検索=目的のものを探すこと
探索=興味あるモノの解析すること

ということらしいですね。
だから探索なんですね。
はいすんません。

Vagrantドキュメントを意訳してみる Getting Started後篇

多分こんな感じなはず。（たぶん）
オリジナル： http://docs.vagrantup.com/v2/getting-started/index.html

前篇
中篇

VMをストップ！

前篇・中編を通して基本的なWeb開発に必要な機能を持ったVMができあがりましたが、
例えば、途中で別のプロジェクトにとりかからなければダメだったり、
ちょうどランチに行く時間だったり、家に帰る時間だったとすると、
（要はVMを止めたいということですね）
さっき作ったVMをどうしたらいいでしょう？

Vagrantだと、suspend・halt・destroyコマンドでVMの停止ができます。
それぞれ長所もあれば短所もありますので、
ケースバイケースで使いわければよろしいかと思われます。

1. vagrant suspend
 vagrant suspendコマンドは現状を保存しつつVMを停止することができます。
再びVMを使いたいときはvagrant upコマンドを実行するだけで、
VMは停止した時と同じ状態で再開します。
suspendする主なメリットは、むちゃくちゃ速いところです。5-10秒で停止＆再開出来ます。
デメリットは、VMがディスクスペースを食うところです。
VMのメモリ上の情報もディスクに保存しなければならないため余分にディスクを食います。

2. vagrant halt
 vagrant haltコマンドはVMのOSをシャットダウンしてVMの電源を落とします。
vagrant upすることでもう一度ブートできます。
この方法のメリットは、VMのディスクを保存しつつ、きれいにシャットダウンできることです。
デメリットは、再起動するまでに少し時間がかかることと、
ホストマシンのディスクを食ってしまうことです。

3. vagrant destroy
 vagrant destroyすると、VMを作った痕跡を完全に消し去ります。
VMを止め、電源をOFFし、VMのハードディスクを完全に消し去ります。
ただし、再び作業を始めたいときはvagrant upするという点は他と一緒です。
メリットはディスクスペースを全く食わないという点です。
デメリットはもう一度OSをインストールしプロビジョンしなければならないので、
起動に時間がかかるところです。

VMの再構築（再開）

明日であろうと来週であろうと一年後であろうとVMを再起動するのはとても簡単です。

$ vagrant up

VMの環境はVagrantfileによって完全に管理されているので、
たったこれだけで再構築できるんです。

プロバイダー

このGetting Startedガイドでは、VirtualBoxをプロバイダーとして使いましたが、
Vagrantでは他にもVMware FusionやAWSなどを使うこともできます。

一度プロバイダーをインストールしたら、特にVagrantfileを修正する必要はありません。
↓のように適切なプロバイダーでvagrant upするだけです。

$ vagrant up --provider=vmware_fusion

クラウドを使いたいなら↓のようにawsを指定してやるだけ！

$ vagrant up --provider=aws

vagrant up時にプロバイダーを指定すれば、それ以降はどのvagrantコマンドを打つときも、
特にプロバイダーを指定する必要はありません。Vagrantが自動的に判定してくれます。
なので、SSHしたいときやdestroyしたいときなどなど、
ただいつもどおりコマンドを打つだけです。

プロバイダーに関するもっと詳しい情報はこちら

Vagrantドキュメントを意訳してみる Getting Started中篇

多分こんな感じなはず。（たぶん）
オリジナル： http://docs.vagrantup.com/v2/getting-started/index.html

前篇はこちら

同期フォルダ

VMを簡単に作れるのはとてもcoolなことですが、
たいがいの人はターミナルでコンフィグファイルをいじって
sshログインするだけではあまり魅力を感じないでしょう。
しかし、Vagrantの同期フォルダ機能を使えば
そんな人でも少しは魅力を感じるかもしれませんね。
Vagrantではホストマシンの特定のフォルダを
VMの特定のフォルダに自動的に同期してくれます。

デフォルトではホストマシンのプロジェクトディレクトリ（Vagrantfileがあるディレクトリ）と、
VMの/vagrantディレクトリが同期されます。

では、もう一度、vagrant upしてvagrant sshしてVMにログインします。

$ vagrant up
$ vagrant ssh
...
vagrant@precise32:~$ ls /vagrant
Vagrantfile

VM上にもVagrantfileがありますね？これはホストマシンにあるVagrantfileと同じものです。
実際にtouchして確かめましょう。

vagrant@precise32:~$ touch /vagrant/foo
vagrant@precise32:~$ exit
$ ls
foo Vagrantfile

はぅ！"foo"がホストマシンにできましたね。
ということで同期されていることを確認できました。

同期フォルダを使うことで、
ホストマシンで好きなエディタを使って編集したあと、VMと同期することだってできます。

プロビジョニング

UbuntuをベースにしたVMもすでに作ったし、ホストとVMの同期もテストしたので、
次は、Webサーバを作ってみましょうか！

では、早速SSHでVMにログインして、Webサーバをインストール・・・することもできますが、
そうすると、このVagrantfileを使う他のユーザーも同じ作業をしなければなりません。
Vagrantにはビルトインのプロビジョニング機能があるので、それを使いましょう。
プロビジョニング機能を使うとvagrant upしたときに、
Vagrantは自動的にWebサーバなどのソフトウェアをインストールしてくれます。
（なので各ユーザーがWebサーバをインストールする必要がありません）

Apacheのインストールシェルの作成

シェルスクリプトを使ってApacheをインストールしてみましょう。
↓のbootstrap.shを作って、Vagrantfileと同じディレクトリに置きます。

#!/usr/bin/env bash

apt-get update
apt-get install -y apache2
rm -rf /var/www
ln -fs /vagrant /var/www

次に、vagrant upしたときにこのスクリプトを実行するように、
Vagrantfileを↓のように編集します。

Vagrant.configure("2") do |config|
  config.vm.box = "precise32"
  config.vm.provision :shell, :path => "bootstrap.sh"
end

"config.vm.provision"の行が新しく追加した行です。
マシン起動時に実行すべきシェルをこの行で設定してます。
ファイルパスはVagrantfileがあるディレクトリからの相対パスで指定します。

プロビジョン！！

↑の準備が整ったら、vagrant upするだけで、自動的にプロビジョニングをしてくれます。
シェルスクリプトからの出力がターミナルで確認できます。
もし、VMをすでに起動しているなら、vagrant reloadコマンドを実行ししてください。
vagrant reloadコマンドは、最初のimport処理（？）をスキップして、すぐにリスタートします。

VMが起動したら、Webサーバも起動しています。
まだ、Webサイトを見ることはできませんが、
プロビジョニングが動いたかどうかはVMにSSHでログインして確認できます。

$ vagrant ssh
  ...
vagrant@precise32:~$ wget -qO- 127.0.0.1

シェルスクリプトでApacheのDocumentRootを/vagrantディレクトリにしたので、
なにがしかを返してくれます。

別のファイルを作ったり、他のソフトをインストールしたりして遊ぶこともできますが、
VMのWebサーバをVMの外から参照するために、
次のステップではネットワークの設定を説明します。

ネットワーク設定

現時点では、Webサーバが起動してて、
ホストとVMで同期しているフォルダをDocumentRootにしている状態ですね。
しかし、VM上からしかアクセス出来ないというのはかなりイマイチな感じですね。
このセクションでは、Vagrantのネットワーク設定について説明します。

ポートフォワーディング

ポートフォワーディングは選択肢のひとつです。
ポートフォワーディングすると、ホストマシンの指定したポートへのアクセスは
VMの指定したポートへ転送されるようになります。

ということで、さっそくVMのApacheにアクセスできるように設定してみましょう。
といっても、Vagrantfileを少しいじるだけです。

Vagrant.configure("2") do |config|
  config.vm.box = "precise32"
  config.vm.provision :shell, :path => "bootstrap.sh"
  config.vm.network :forwarded_port, host: 4567, guest: 80
end

↑のように"config.vm.network"の行をつけたして
vagrant reloadかvagrant upすれば完了です！

VMが再起動したら、http://127.0.0.1:4567/にブラウザでアクセスしてみましょう。
VMのApacheが表示しているページが見えているはずです。

その他のネットワーク設定

Vagrantはその他にもネットワーク設定方法があります。
例えば、VMにIPを静的に割り当ててみたり、
既存のネットワークを使ったブリッジ設定をしてみたりです。
もし、他のネットワーク設定の興味がある場合は、こちらをご参照のこと。

Vagrantドキュメントを意訳してみる Getting Started前篇

多分こんな感じなはず。（たぶん）
オリジナル： http://docs.vagrantup.com/v2/getting-started/index.html

Getting Startedガイド

Getting StartedガイドではVagrantの基本と主な機能を説明します。

初めてのVagrantプロジェクトを作成する前に、Vagrantをインストールしてください。
もし、なぜVagrantを使う必要があるのか疑問がある場合は、"Why Vagrant?"をご参照のこと。

Getting StartedガイドではVagrantを使うために、
VirtualBox（無料でなおかつメジャーなOSで利用可能なので）を使います。
ですが、VagrantはVirtualBoxだけでなくVMWareなどの
他のプロバイダーを使っても動きますのでお忘れなきよう。

ともかく動かしてみる！

$ vagrant init precise32 http://files.vagrantup.com/precise32.box
$ vagrant up

↑の２つのコマンドを実行すると、
VirtualBox上でUbuntu 12.04 LTS 32-bitをインストールしたVMが動きます！
vagrant sshコマンドでこのVMにsshログインできますし、
ひとしきり遊び終わったらvagrant destroyでVMを削除することもできます。

簡単でしょ？

Vagrantでは、vagrant upさえすれば、
プロジェクトに必要な全部の依存関係の解決やネットワークの設定やフォルダの同期などを
勝手にやってくれます。

このガイドの残りでもうちょっと詳しくVagrantの機能について説明します。

プロジェクトのセットアップ

Vagrantを使うためにはまずVagrantfileを編集する必要があります。
Vagrantfileの存在意義は2つあります。

1. Vagrantfileを置いた場所をプロジェクトのrootディレクトリとすること。
Vagrantの設定で使うパスなどはこのrootディレクトリとの相対パスとなります。

2. プロジェクトに必要なVMの設定やインストールすべきソフトウェアや
どうやってVMにアクセスするかの設定を書くこと。

rootディレクトリを初期化するためには
vagrant initコマンドを使います。
ということで、以下のコマンドを実行してみましょう。

$ mkdir vagrant_getting_started
$ cd vagrant_getting_started
$ vagrant init

これで、vagrant_getting_startedディレクトリにVagrantfileが作成されます。
Vagrantfileをちらっと見てください。コメントと実例で埋め尽くしてます。

既存のディレクトリをVagrant用にセットアップすることもできます。

プロジェクトごとにVagrantfileをバージョン管理すると便利です。
そうすると、そのプロジェクトで一緒に働いている人がみんなハッピーになりますから。

BOX

VMをスクラッチからビルドする代わりに、
VagrantはVMにお手軽に環境をcloneするために、ベースとなるイメージを使います。
ベースとなるイメージはVagrantでは"box"と呼んでいます。
Vagrantfileを作成したら、いの一番にプロジェクトで使うboxを指定しましょう。
（こうすることによって、CentOSのISOをダウンロードして、
ISOから一からインストールするというプロセスをスキップできます。）

boxをインストールする！

もし↓のコマンドをすでに打ってたら、

$ vagrant init precise32 http://files.vagrantup.com/precise32.box

もうboxはインストールされているのでもう一回インストールコマンドを打つ必要はないです。
ただ、もうちょっと詳しくboxについて知るためには、
このセクションを読んどいたほうがいいです。

boxはvagrant box addコマンドを打った時に追加されます。
boxは複数のVagrant環境が再利用できるように特定の名前をつけます。

$ vagrant box add precise32 http://files.vagrantup.com/precise32.box

↑のコマンドでboxがhttp://files.vagrantup.com/precise32.boxからダウンロードされ、
"precise32"という名前で保存されます。
（ローカルマシン内のboxファイルも同じ手順で管理することができます）

追加したboxは複数プロジェクトで再利用できます。
各プロジェクトはboxをベースイメージとして使うだけなので、
保存されたboxファイルは修正されません。
つまり、2つのプロジェクトでprecise32（さっきダウンロードしたbox）を利用していても、
お互いに全く影響がありません。

boxを使う

さてさてboxがVagrantに追加されたので、
プロジェクトがさっき追加したboxをベースイメージとするように設定します。
Vagrantfileを開いて以下の内容を編集します。

Vagrant.configure("2") do |config|
  config.vm.box = "precise32
end

"precise32"はさっき追加したbox名と一致してなければなりません。
Vagrantはこの名前にもとづいてどのboxを使うべきかを判断します。

次のセクションではVMを立ち上げて、すこし遊んでみます。

立ち上げてSSHでログインしてみる！

ではさっそくVMを立ち上げてみましょう。

$ vagrant up

1分以内にUbuntuがインストールされたVMが起動されます。
・・・とは言っても、VagrantはUIなしでVMを立ち上げるので、
何も起こってないように見えるでしょう。
実際に起動していることを確かめるため、VMにsshでログインしてみましょう！

$ vagrant ssh

このコマンドでsshログインでき、VM上で好き放題出来ます。
ただし、↓のコマンドだけは気をつけてください、

$ rm -rf /

といいますのも、VM上の/vagrantディレクトリは
ホストマシンのVagrantfileを含むディレクトリと同期しているからです。



・・・ちょっと考えてみてください。
たった一行のコンフィグファイルの修正と一つのコマンドでSSHでログイン可能なVMを作りましたよ。どうですよ？

作ったVMでひと遊びしたら、vagrant destroyコマンドをホストマシンで打ってください。
さっき作ったVMを跡形もなく削除します。

Vagrantドキュメントを意訳してみる インストール篇

多分こんな感じなはず。（たぶん）
オリジナル： http://docs.vagrantup.com/v2/installation/index.html

Vagrantのインストール！

Vagrantのインストールはとても簡単です！
ダウンロードページに行って
各OS用のインストーラーをダウンロードするだけ。
後は他のアプリのインストールとおんなじようにインストールするだけです。

インストールが終わると、ターミナルから"vagrant"コマンドが打てるはずです。
もしコマンドが打てなかったら、
一回OSからログアウトしてまたログインしたら打てるようになっているはず。
（Windowsだとたまに必要）

もし、gemでVagrant 1.0.x系をすでにインストールしてるのなら、
新しいのをインストールする前に1.0.x系をgem uninstallする必要があります。

gemインストール？？
Vagrant 1.0.x系だとgemでインストールすることができますが、
あんまりオススメじゃないからやめた方がいいです。（たぶん今後のサポート無し）
代わりにここからダウンロードしてください。

後方互換性

1.0.x系との互換性

Vagrant 1.1+はpluginを使ってないVagrant 1.0.xとなら完全に互換性があります。
なので、アップグレードしても、Vagrant 1.0.x系で作った環境もそのまんま使えます。

ただし、もし1.0.x系のpluginを使ってるのなら要注意。
Vagrantfileに書いてあるpluginへの参照を完全に削除する必要があります。
Vagrant 1.1+からはpluginのフォーマットが新しくして、
こういう互換性のなさを避けるようにしました。

もし、pluginを使ってない1.0.x系のVagrantfileが1.1でうまく動かなくなったら、
バグを報告してください。


1.X系との互換性

1.x系（1.0以外）の間での後方互換性は保証してません。
さらに言っておくと、Vagrantfileのsyntaxも2.0 finalまではころころ変わるかもしれない。
ただ、互換性がない部分はドキュメントに丁寧に書くつもりなのでそれを見てください。

0.x系のときも同じでしたね。
2.0 finalは1.0系と同じで完全に後方互換性を保つつもりです。

Vagrantのアップグレード！

1.0.x系からアップグレードする場合は一つ↓の項目をみてください。
ここでは1.x系（1.0系以外）間でのアップグレード方法を書くつもりです。

1.x系でのアップグレードはとてもシンプルです。
ただ新しいパッケージをダウンロードしてインストールするだけです。
後はインストーラが勝手にやってくれます。
Linuxのパッケージマネージャー（yumとかaptitude？）を使っている場合も
同じようにうまいことインストールしてくれるはず。

さっきも言いましたが、2.0系になるまでは
1.x系でのVagrantfileのSyntaxの互換性は保証してないから
それだけは要注意です。

1.0.x系からのアップグレード！

1.0.x系から1.x系へのアップグレードはとてもシンプルです。（さっきも言ったな・・・）
ただ新しいパッケージをダウンロードしてインストールするだけです。

ただ、gemで1.0.x系をインストールしてしまったときは要注意です。
その場合は、新しいのをインストールする前に、gem uninstallする必要があります。
1.x系以降は、gemでのインストールはもうサポートしてません。

Vagrantのアンインストール

Vagrantのアンインストールもこれまた簡単です。
Vagrantのバイナリかユーザーデータを削除すればOKです。
もちろん両方削除してもOKです！
↓でもう少し詳しく説明します。

Vagrantプログラムの削除

Vagrantプログラムを削除したら、
vagrantのバイナリや依存してるファイルを全部マシンから削除します。

Windows ... コンパネからプログラムの追加と削除でアンインストール
Mac OS X ... /Applications/Vagrantディレクトリと/usr/bin/vagrantを削除
Linux ... /opt/vagrantディレクトリと/usr/bin/vagrantを削除

ユーザーデータの削除

ユーザーデータを削除することは、
つまり、boxやpluginやVagrantが保存した状態すべてを削除するってことです。

ユーザーデータを削除すると、
再インストールするときに、Vagrantは全く新しいインストールだと認識します。

ユーザーデータの削除時にやることは、どのOSでもやることは同じです。
~/.vagrant.dディレクトリの削除です。

Vagrantを実行すると勝手に必要なデータを作成するので、
ためらわずに削除しちゃってください。

Gitでほんとによく使うコマンド

自分はもともとsvnでバージョン管理してたので、
正直最初gitにはとっつきにくかったです。

とっつきにくかった理由は、

1. 分散管理がようわからん
2. svnと用語が微妙に違う

ってとこだと思います。

1についてはhttp://git-scm.com/book/jaの
1.1と1.3をよく読めばなんとなくわかってくるかと思います。

2については反復実行して体で覚えるしかないです。

$ git clone <remote> <local>
  リモートリポジトリからローカルリポジトリとワークスペースを作成する。
$ git pull
  最新版のリモートリポジトリを取得してローカルリポジトリ、ワークスペースを更新する
$ git push <remote> <branch>
  リモートリポジトリへローカルリポジトリの変更を更新する
$ git init --bare --shared
  gitのリモートリポジトリを作成する。しかもグループで共有したい。
$ git add <file>
  修正したファイルをステージングにあげる。新しく追加したファイルをバージョン管理する。
$ git reset HEAD <file>
  ステージングに上げたファイルをステージングから下ろす。
$ git commit
  ステージングにあがっている修正をコミットする。
$ git commit -a
  git addなんてめんどくさいって時に便利。
$ git commit --amend
  やっちまった！一つ前のコミットを修正したい・・・
$ git mv  <from> <to>
  ファイルをリネームする
$ git rm <file>
  ファイルを削除し、バージョン管理からも外す
$ git branch
  ブランチを表示し、現在のブランチを知る。
$ git branch <branch>
  ブランチを作成する
$ git checkout <branch>
  ブランチを切り替えたい
$ git checkout -b <branch>
  ブランチを作成しつつ切り替える
$ git merge <branch>
  ブランチをマージする
$ git rebase <branch>
  ブランチをリベースする

リモートリポジトリ関連

リモートリポジトリの取得

社内gitや自分のgitやGitHubからプロジェクトを取得するには、
以下のコマンドを打ちます。

$ git clone <remote> <local> 

svn checkoutとたぶんほぼ同じです。
このコマンドで、<local>で指定したディレクトリに
ローカルリポジトリとワークスペースが作成されます。
また、↓のような感じで<local>を指定しないこともできます。
この場合、nerdtreeディレクトリが作成されます。

$ git clone https://github.com/scrooloose/nerdtree.git

clone以降、開発中はファイルのステータスが
"修正済み", "ステージングに上がっている", "コミット済み"を行き来するわけですが
その間リモートリポジトリとのやり取りは発生しません。

リモートリポジトリ <-> ローカルリポジトリのやり取り

$ git pull
$ git push <remote> <branch>

git pushするとリモートリポジトリを、
ローカルリポジトリと同期するのですが、
複数人で開発している場合は、
その前にgit pullをして他の人の修正を取り込まなければgit pushできません。

リモートリポジトリの作成

$ git init --bare --shared

↑のコマンドを実行すると、リモートリポジトリを作成することができます。
--sharedを忘れると、基本的には複数人で開発できなくなります。
ただし--sharedをつけても、開発者全員が同じグループに所属している必要があります。

ステージング <-> ワークスペースのやり取り

$ git add <file>

git addしたファイル(またはディレクトリ)は
コミット候補生(ステージングされた状態)となります。

なぜステージングなんて中途半端なものがあるのか ・・・
と最初はまどろっこしいわいと思ってましたが、
コミットヒストリーにためらい傷を残さないですむので
そそっかしい人にはちょうどいいです。
(他にもステージングがある理由はあると思いますが・・・)

そして、
あ、間違ってステージングに上げてしまった！って時は慌てずに、

  git reset HEAD iwaswrong.txt

を実行すればステージング前の状態に戻ります。

コミットする

ステージングにあげた修正をコミットする場合は、

$ git commit

を実行します。
実行するとコメントを求められますので、
あとで見直す自分のことを考えて、わかりやすいコメントを入力します。

ちょっとした修正なのでわざわざステージングに上げるのもめんどくさいという時には、

$ git commit -a

なんて便利なコマンドもあります。
これを使うと、ワークスペースの修正がすべてローカルリポジトリに反映されます。

前回のコミットのコメント間違った！とかファイル1個追加し忘れた！って時は、

$ git add forgottenfile.txt
$ git commit --amend

でコミットをやり直せます。

ファイルをリネームしたり削除したり・・・

遠い過去なのであまり覚えてませんが、
ファイルのリネームはsvnだと若干めんどくさかったような記憶があります。

それは置いといて、まずはバージョン管理から外す方法ですが、

$ git rm unnecessary.txt

で可能です。コマンドを実行するとunnecessary.txtはバージョン管理から外れるのみならず、
ファイル自体削除されるので要注意です。(すぐに戻せますが)

ちなみにリネームのプロセスはgitだと以下のプロセスでできます。

$ mv old.txt new.txt
$ git rm old.txt
$ git add new.txt

・・・めんどくさっ！
以下のコマンド一発で同じ事ができるのでご安心ください。

$ git mv old.txt new.txt

ブランチ関連あれこれ

ブランチを知る

$ git branch
* master

でブランチの一覧を表示します。

作成したばかりのリポジトリだとmasterブランチしかないはず。
masterの左に*がついてると思いますが、*がついているところが現在作業中のブランチです。

ブランチの作成と切り替え

例えば、devブランチを新しく作成したい場合は

$ git branch dev

を実行します。
そして、devブランチに作業ブランチを切り替えます。

$ git checkout dev

この一連の流れ(ブランチ作成しーの切り替えーの)をコマンド一発でもできます。

$ git checkout -b dev

ブランチを合併

devブランチで開発をしているさなか、
新機能Aを追加するためにfeatureAブランチを切って開発する一方で、
BUG 1が発見されたのでその解決のためにdevブランチからhotfix1ブランチを作成した。

新機能AもBUG 1も無事修正が終わり、devブランチとマージしたい。
しかし、featureAブランチはhotfix1ブランチから枝分かれしたことにしたい。

というケースを考えてみる。

$ git branch
  master
  dev
  featureA
* hotfix1                         # 現在hotfix1ブランチで作業中
$ git checkout featureA  # featureAブランチへ移動
$ git rebase  hotfix1        # BUG 1の修正をfeatureAブランチに取り込む。
$ git branch
  master
  dev
* featureA
  hotfix1
$ git checkout dev          # devブランチへ移動
$ git merge featureA       # 新機能Aをマージ

git rebaseとgit mergeをこのように使い分けると何がいいかっていうと、
git mergeだけだと、コミットヒストリーは、

--dev--featureA
    |--hotfix1

↓

--14a2b--featureA--dev
      |--hotfix1----------|

となるところを

--dev--featureA
    |--hotfix1

↓

--14a2b--hotfix1--featureA--dev

という綺麗なコミットヒストリーのツリーを作ることができる点です。

しかし、細かいことは忘れましたが、
git push前後でgit rebaseをすると、
とんでもないことが起こって、共同開発者に切れられるらしいので要注意です。

もっと便利にgitを弄びたいという方は、
* Pro Git: http://git-scm.com/book/ja
の1, 2, 3, 5章を読めばだいたいOKかと思われます。

もっと深くgitを知りたいという方は
↑の他の章も読むとよろしいかと思います。

なんにせよ↑の本一冊で十分じゃないかなと思います。

アルゴリズムを体で覚えてみる 二分探索

最近訳あってアルゴリズムの勉強をしてます。

いままであんまりアルゴリズムに強い関心を持ってたわけじゃないですし、
正直アルゴリズムなんて知らなくても大概のプログラムは書けると思うのですが・・・
やはりアルゴリズムは強力だなと思う今日このごろです。

超有名ですが、『二分探索』って改めてすごいなーと思ったので、
二分探索について書いてみたいと思います。

線形探索(配列の先頭から順番に調べてくあれです)と
二分探索の計算のオーダーをそれぞれ比較してみると・・・

* 線形探索 O(n)
* 二分探索 O(log n)

なのはたぶん有名だと思うのですが、
正直この凄さをあまり真面目に考えたことがなかったです。
ほんとプログラマーやっててすみませんでした。

なにがすごいって、、、
n=1,000,000の場合、
線形探索の場合、平均して500,000回の比較が必要となりますが、
二分探索の場合、最悪でもおよそ19回の比較で十分なんですよ。
いやほんとすみません・・・

ちょっとPythonで書いてみます。(バグってたらすみません)

def binsearch_rec(target, arr, l, r): 
    """ 再帰で二分探索をする関数

    target: 見つけ出したい値
    arr: targetを探索する配列
    l: arrの探索範囲の左端
    r: arrの探索範囲の右端

    前提条件: arrは昇順にソートされている必要がある
    戻り値： targetの見つかった位置。見つからなかった場合は-1
    """

    if l > r:
        # 探しに探したが見つからなかった
        return -1

    m = (l + r) / 2 # 探索範囲の真ん中のindexを計算
    if target < arr[m]:
        # 見つけたい値がarrの真ん中より小さかったら
        # mより左の範囲を再帰的に探す。
        return binsearch_rec(target, arr, l, m-1)
    elif target > arr[m]:
        # 見つけたい値がarrの真ん中より大きかったら
        # mより右の範囲を再帰的に探す。
        return binsearch_rec(target, arr, m+1, r)
    else:
        # 見つけた！
        return m

↑は再帰バージョンですが、ループを使う方法もあります。

def binsearch_loop(target, arr):
    l = 0 
    r = len(arr)-1
    while l <= r:
        m = (l + r) / 2 
        if target < arr[m]:
            r = m-1 
        elif target > arr[m]:
            l = m+1
        else:
            return m
    return -1

趣味だとは思いますが、個人的には再帰を使う方が覚えやすいです。
ですが、ループのほうが関数の呼び出し分のロスがない分、
速いという噂もあります。



正直なところ、探索が必要なときは
今まですべて線形探索してました。
というか二分探索する必要すらなかったのですが・・・
・・・にしても自己嫌悪に陥いりますわ。

VagrantとChef SoloでNode.jsの開発環境を作る

Nodeの開発環境ってどうやって準備してますか？
nvmいれてnodeを入れてnpmでパッケージインストールするだけ！
といえばそうなんですけど・・・例えば、別のマシンで環境を作りなおすとなると
少しめんどうですよね。

例えば、VirtualBoxをインストールして、Vagrantをインストールして、
コマンド一発で環境を作り直せるとしたら便利ですよね・・・

node入れるだけならそれほど便利さは実感できないと思いますが、
例えば、そこにApacheやらNginxをいれて、Rails入れたりとかしなきゃいかんとなると、
ゾッとしますね。
それにコマンド一発だとインストール漏れもないという利点も・・・

ということで、VirtualBox + Vagrant + Chef Soloで
Mac上に作ったVirtual Machineにnodeをインストールして、
さらにgruntをインストールするというレシピを作ってみます。

ChefやレシピやChef Soloについては↓でとてもわかりやすく説明されております。

* 明日から始めるChef入門
  http://www.slideshare.net/TakeshiKomiya/chef-20014957
* Chef Soloの正しい始め方
  http://tsuchikazu.net/chef_solo_start/

レシピを作る

Vagrantfileがあるディレクトリで、以下のコマンドを実行して
レシピの置き場所を作成します。

  $ knife solo init chef-repo

↑のコマンドを実行すると、
chef-repo以下にいい感じでディレクトリツリーが出来上がります。

3rdパーティーのレシピはchef-repo/cookbooksに置き、
自作レシピはchef-repo/site-cookbooksに置くそうです。

git, curlコマンドをインストールするレシピを作ってみる

nvmをインストールするためにgitとcurlコマンドが必要なので、
git, curlコマンドをインストールします。
まずは先ほど作成したchef-repoディレクトリに移動して、Cookbookの雛型を作成します。

 $ knife cookbook create base -o site-cookbooks/

↑のコマンドを実行すると、
site-cookbooks以下にbaseディレクトリ(Cookbook)が作成されます。

次に、git, curlコマンドをインストールするレシピを書いてみます。

  $ cd site-cookbooks/base/
  $ vi recipes/default.rb
    package "git"
    package "curl"

たったこれだけで、
Ubuntu (Debian系)ならapt-getコマンドが呼ばれ、
CentOS (Redhat系)ならyumコマンドが呼ばれてインストールが始まります。

nvmをインストールするレシピを作ってみる

まずは先ほどと同じく、nvmレシピの雛型を作成します。

  $ knife cookbook create nvm -o site-cookbooks/

ではではnvm & Node.js v0.10.1をインストールするレシピを書いてみます。

  $ cd site-cookbooks/nvm/
  $ vi recipes/default.rb
    git "/usr/local/nvm" do                                            # githubからnvmを/usr/local/nvmへインストール
      repository "git://github.com/creationix/nvm.git"
      notifies :run, "bash[nvm.sh]"                                 # インストールが終わったらnvm.shという名前のbashを実行
    end

    bash "nvm.sh" do                                                     # nvm.shという名前のbash。
      code <<-EOH
        . /usr/local/nvm/nvm.sh                                      # nvmコマンドの読み込み
        nvm install v0.10.1                                               # Node.js v0.10.1をインストール
      EOH
      action :nothing                                                        # git cloneが終わるまで実行したくないのでnothingを指定。
    end

    template "/etc/profile.d/nvm.sh" do                        # nvm.sh.erb (後述)を/etc/profile.d/nvm.shにコピー
      source "nvm.sh.erb"
      mode 00644
    end

最後のブロック(template)なのですが、これはなんというか・・・
基本的には、(chef-repo/site-cookbooks/nvm/)template/default/nvm.sh.erbを
指定した場所にコピーするのですが、
単にコピーするだけではなく、
nvm.sh.erb内でRubyの変数が使われている場合、
変数に適切な値を代入しつつコピーしてくれるといったものです。

ちなみに、nvm.sh.erbの中身はこんな感じです。(特にrubyの変数は使ってないです)

  $ cat template/default/nvm.sh.erb
    #!/bin/sh
    . /usr/local/nvm/nvm.sh
    nvm use v0.10.1

Gruntをインストールするレシピを作ってみる

では最後に、Gruntをインストールするレシピを作成します。
Gruntのレシピはnvm Cookbook内に作成するとします。

  $ vi recipes/grunt.rb
    bash "grunt" do
      code <<-EOH
        . /usr/local/nvm/nvm.sh
        nvm use v0.10.1
        npm install -g grunt-cli
      EOH
      action :nothing                                                                    # nvm.shの実行終了したら走らせるためnothingを指定
      subscribes :run, "bash[nvm.sh]", :delayed                          # nvm.shの実行を監視してます。
    end

VagrantとChef Soloを連携させる

VagrantfileにChef Soloとの連携部分を追記する。

  $ vi Vagrantfile
    ・・・中略 ・・・
    config.vm.provision :chef_solo do |chef|
      chef.cookbooks_path = "chef-repo/site-cookbooks"
      chef.add_recipe "base"
      chef.add_recipe "nvm"
      chef.add_recipe "nvm::grunt"
    end

VMにレシピを適用する！

  $ vagrant halt && vagrant up

でvagrant upするときにChefのレシピも実行されますが、
以下のコマンドを実行するとChefの部分のみ実行することができます。

  $ vagrant provision

Vagrantでお手軽にVMを作っては壊し作っては壊す

Mac OS上にVirtual Machineを作成して
楽しむ方法を以前 (VitrualBoxでMacにいつでも壊せるVMをサクサク作る) 書きました。

が、Vagrantというツールを使うと、
Virtual Machineと連携してもっと簡単にVMを作成出来ます！

詳しくはこちら↓↓
http://www.vagrantup.com/
http://docs.vagrantup.com/v2/installation/index.html

Vagrantのインストール

http://downloads.vagrantup.com/
からdmgをダウンロードする。

※ Gemでインストールすると、
    古いVersionのVagrantをインストールしてしまうそうなので、要注意。

Boxのダウンロード

Boxはなんていうか・・・Vagrantで使うOSイメージみたいなもんらしいです。
ISO的やつです。

ということでOSをインストールするために、まずはBoxをダウンロードします。
今回はubuntuをダウンロードします。

 $ vagrant box add ubuntu http://files.vagrantup.com/precise64.box

ダウンロードできるBoxの一覧はこちら。
http://www.vagrantbox.es/

VMの設計書を作る

次にVagrantfileを作成します。

Vagrantfileとは何かといいますとVMの設計書みたいなものを作ります。
つまり、
* 今から作成するサーバの名前はほにゃららで、
* IPアドレスはほにゃららで
* メモリはふにゃららGB使います
的なことを記述しているファイルです。

  $ vagrant init ubuntu

(ubuntuを指定することでさっきbox addしたOSをインストールしますよ、
って指定してます)
このコマンドを実行すると、Vagrantfileができます。
これがVMの設計書となります。

初期設定する

ホスト名の設定

config.vm.hostname = "HOSTNAME"

をVagrantfileに追加します。
そうするとホスト名が設定されます。

ネットワークの設定

1. NAT的設定

  config.vm.network :forwarded_port, guest: 80, host: 8080

  とVagrantfileに書くことでホストマシンの8080へのアクセスは、
  ゲストVMの80ポートへ転送されます。

2. Bridge的設定

  config.vm.network :public_network

  とVagrantfileに書くことでローカルネットワークからゲストVMを見ることができます。

3. NAT + Host Only Adapter的設定

  config.vm.network :private_network, ip: "192.168.33.10"

  とVagrantfileに書くことで、ホストマシンからのみアクセスを許可する。

メモリサイズの設定

デフォルトだとOSが推奨する最小限のメモリになるような気がします。(たぶん)
なので、ちょっと多めに割り当てたいときは、

  config.vm.provider :virtualbox do |vb|
    vb.customize ["modifyvm", :id, "--memory", "1024"]
  end

のようにVagrantfileに記述します。
この場合、メモリを1024MBに設定してます。

VMを作る

設計書ができたので、以下のコマンドで実際にVMを作成してみます。

  $ vagrant up

しばらく待ったらVMができてます。

VMにログインする

以下のコマンドをVagrantfileを置いたディレクトリで実行すると
さっき作成したVMにsshでログインします。

  $ vagrant ssh

デフォルトではvagrantユーザーで~/.vagrant.d/insecure_private_keyを使った
鍵認証でログインします。

VMを壊す

  $ vagrant destroy

をホストマシンで実行するだけで完全にVMを消し去ります。

もう一回同じ設定で作りなおすときは、

  $ vagrant up

でOK。

単にshutdownしたいだけなら、

  $ vagrant halt

で終了。

で？

まーここまでだとあんまり良さを実感できないですよね。
単にOSのインストールでいろいろ選ばなきゃダメなところを勝手にやってくれるだけ？
って感じですね。

VagrantはChefやPuppetと連携することでもっと威力を発揮します。
次回Chef Soloとの連携を書くと思います。

VitrualBoxでMacにいつでも壊せるVMをサクサク作る

ローカルマシン上にVirtual Machine (VM)を作れるといろいろと便利ですよね。

無駄にソフトウェアをインストールして失敗してはVMを作りなおしたり、
 MacにWindowsを入れてみたりできますしね。

VirtualBoxは無料でWindowsやMac、Linux上にVMを作れる Oracleが提供するサービスです。
https://www.virtualbox.org/

VMWareも同じようなものですが、
Macで無料というのはVirtualBoxだけかと思われます。

VirtualBoxのインストール

https://www.virtualbox.org/wiki/Downloads
こちらのURLからダウンロード。

ダウンロードしたdmgをダブルクリックして、
指示通りやればインストール完了。

UbuntuのVMを作ってみる

Ubuntu Serverのisoをダウンロード

まずはここから

http://www.ubuntu.com/server

Ubuntu Server 13.04をダウンロードする。

VMの箱だけとりあえず作ってみる

箱という呼び方が正しいかどうかわかりませんが、
とりあえずUbuntuをインストールする前準備をします。
では、インストールしたVirtualBoxを起動して、VMを作成しまーす。

1. 新規作成

2. 名前は適当でいいですがタイプはLinuxでバージョンはUbuntu (64bit)を選ぶ

3. メモリの割り当ては後で変えれるのでデフォでOK
4. 仮想ハードドライブを作成するを選ぶ。あとはVDI、可変タイプを選択。
  サイズは20GBくらい？

ネットワークの設定

あんまりネットワーク詳しくないのですが、以下の3つの方法があるかと。

1. NAT
  NATだけだと、IPがホストマシンと同じになるので、
  SSHでログインとかするときに別のポート設定しなきゃだめだし、
  サービス増えるごとにポートの設定も増えるのでなし。

2. Bridge
  Bridgeだとホストマシンとローカルネットワーク内で同列に並べることができるので、
  ホストマシン以外からも閲覧可能にしたい場合はBridgeがいい。

3. NAT + Host Only Adapter
  VM -> ホストの通信(VMからwgetしたりとか)にはNATを使い、
  VM <- ホストの通信(VMへログインしたり)にはHost Only Adapterを使う方法。

ローカルネットワークから見える必要はないので、3でやってみる。

NAT + Host Only Adapterの設定

0. 環境 -> ネットワークタブでホストオンリーネットワークを追加する。

1. 作ったVMを選択
2. 設定ボタンを押してネットワークタブを選択
3. アダプター2を選択
    * ネットワークアダプタを有効
    * ホストオンリーアダプターを選択

4. でOK

ようやくUbuntuのインストール

VirtualBoxのウィンドウ上の左側からさきほど作ったVMを選択しますね。
そしたら、↓のような画面が表示されるので、
さっきダウンロードしたUbuntuのISOを選んでインストールを開始します。
あんまり細かいことを気にしないのであれば、
基本yes的なボタンを押し続けていればインストールは完了します。

起動してみる

一応インストールが終わったはずなので起動してみます。

◯で囲んだところをダブルクリックでVMを起動。

起動したらゲストVMにログインしてネットワークの設定をします。

  $ sudo vi /etc/network/interfaces
    auto eth1
    iface eth1 inet dhcp

設定が終わったら

  $ sudo service networking restart

でネットワークを再起動してさきほどの変更内容を有効にします。

ネットワークの再起動が終わったらホストマシンからsshでログイン可能に。

ウィンドウ無しで起動する

なんというかVMのウィンドウ？ (GUI)があるとなんかうっとうしいですね。
基本ターミナルからsshでログインして使いたいので、
VMのGUIを作らずにVMを起動します。
これをHeadlessというらしい (たぶん)

以下のコマンドをホストマシンで実行したらHeadlessで起動できます。

  $ VBoxManage startvm "test" --type headless