2012-05-23

初めて symfony でプロジェクトを作ってみた

PHPのフレームワークを使ってみた。あんまり好きじゃないけどお仕事ですからね〜 (>_<)

1.取りあえずrootで作っちゃう

⇒ 本当はアプリケーションアカウントを作って実施すべし。
$ sudo su -

2.プロジェクト用のディレクトリを作成

# cd /var/www/html/
# mkdir world
# cd world/

3.プロジェクト(スケルトン)作成

# symfony init-project world
  Task "init-project" is not defined.
ってエラーが出たら、v1.4系なのにv1.0系のコマンドを使った証拠。やりなおし。 バージョン調べたければ事前に「$ symfony -V」してみる。
# symfony generate:project world
>> file+     /var/www/html/world/symfony
....
>> tokens    /var/www/html/world/config/doctrine/schema.yml
>> tokens    /var/www/html/world/lib/form/BaseForm.class.php
#
いろいろいる物を作ってくれる。 何も無かったところがこんな感じに。
# ls -l
drwxr-xr-x 2 root root 4096 May 23 11:26 apps
drwxrwxrwx 2 root root 4096 May 23 11:26 cache
drwxr-xr-x 3 root root 4096 May 23 11:26 config
drwxr-xr-x 3 root root 4096 May 23 11:26 data
drwxr-xr-x 3 root root 4096 May 23 11:26 lib
drwxrwxrwx 2 root root 4096 May 23 11:26 log
drwxr-xr-x 2 root root 4096 May 23 11:26 plugins
-rwxrwxrwx 1 root root  446 May 23 11:26 symfony
drwxr-xr-x 5 root root 4096 May 23 11:26 test
drwxr-xr-x 6 root root 4096 May 23 11:26 web

4.アプリケーション設置

# symfony generate:app traveler
>> dir+      /var/www/html/world/apps/traveler/modules
....
>> tokens    /var/www/html/public_html/lib/form/BaseForm.class.php
#
なんかまた作ってくれる。
# ls -l ../world/apps/traveler/
drwxr-xr-x 2 root root 4096 May 23 16:41 config
drwxr-xr-x 2 root root 4096 May 23 16:41 i18n
drwxr-xr-x 2 root root 4096 May 23 16:41 lib
drwxr-xr-x 2 root root 4096 May 23 16:41 modules
drwxr-xr-x 2 root root 4096 May 23 16:41 templates

5.開発用ファイルを使えるようにする

# vi web/traveler_dev.php
この部分をコメントアウト
if (!in_array(@$_SERVER['REMOTE_ADDR'], array('127.0.0.1', '::1')))
{
  die('You are not allowed to access this file. Check '.basename(__FILE__).' for more information.');
}
コメントアウトしないと開発環境のアプリケーションにアクセスした時に、 http://hogehoge.jp/hoge1_dev.php/ 「You are not allowed to access this file. Check traveler_dev.php for more information.」 ってでて見えない。

6.Apacheの設定

# vi /etc/httpd/conf.d/vhost.conf
NameVirtualHost *:80


  ServerName world.hoge.jp
  DocumentRoot "/home/web-apps/world/web"
  DirectoryIndex index.php
  
    AllowOverride All
    Allow from All
  

  Alias /sf /usr/share/pear/data/symfony/web/sf
  
    AllowOverride All
    Allow from All
  
あとは、Apache起動させてOK.おなじみの画面でたし (*´∀`*)

参考:Practical symfony | symfony | Web PHP Framework

2012-02-22

AmazonEC2にS3領域をマウントしてみる

今日は、EC2にS3のバケットをマウントしてみました。
手順はこんな感じ。
  1. FUSEにいる物をインストール
  2. FUSEインストール
  3. f3sfインストール
  4. A3にバケット作成
  5. マウント
  6. 再起動してもマウント
参考にしたこちらのサイト通りでほぼOKです。
memorycraft: S3ってなんじゃ?(s3fs編)

では、インストールログを。。

1.FUSEにいる物をインストール

# yum -y install gcc
# yum -y install gcc-c++
# yum -y install libstdc++-devel
# yum -y install pkgconfig
# yum -y install make
# yum -y install curl-devel
# yum -y install libxml2-devel
# yum -y install openssl-devel

2.FUSEインストール

バージョン確認 2.8.4より新しくないと駄目。 yumで入れられない場合は⇒http://sourceforge.net/projects/fuse/files/fuse-2.X/
$ yum list | grep fuse
fuse.x86_64                           2.8.6-1.10.amzn1             amzn-updates
fuse-devel.x86_64                     2.8.6-1.10.amzn1             amzn-updates
インストール
# yum -y install fuse
# yum -y install fuse-devel
環境変数設定
# export PKG_CONFIG_PATH=/usr/lib64/pkgconfig
カーネルにロード
# ldconfig 
# modprobe fuse

3.f3sfインストール

# cd /usr/local/src
# wget http://s3fs.googlecode.com/files/s3fs-1.40.tar.gz
# tar zxvf s3fs-1.40.tar.gz 
# cd s3fs-1.40
# ./configure prefix=/usr
# make
# make install

4.A3にバケット作成


5.マウント

キー情報を記載
単一認証
# echo アクセスキー:シークレットキー > /etc/passwd-s3fs
複数認証http://www.blogger.com/blogger.g?blogID=9198835639547511373#editor/target=post;postID=8405377529952507279
# echo バケット名:アクセスキー:シークレットキー > /etc/passwd-s3fs

# chmod 640 /etc/passwd-s3fs 
マウント
# mkdir /mnt/s3
# s3fs myfirst-bucket /mnt/s3
# df -kh
Filesystem            Size  Used Avail Use% Mounted on
/dev/xvda1            7.9G  2.4G  5.5G  30% /
tmpfs                 3.7G     0  3.7G   0% /dev/shm
s3fs                  256T     0  256T   0% /mnt/s3

6.再起動してもマウント

# vi /etc/fstab
+++ s3fs#myfirst-bucket /mnt/s3 fuse allow_other,default_acl=public-read 0 0

# vi /etc/rc.d/rc.sysinit
...
. /etc/init.d/functions
+++ modprobe fuse

*** うーんうまくできなかった (´;ω;`)ウッ… ***

微妙な感じでうまくいかない。見えたり、見えなかったり。。。よって、こちらのバージョンにした。

cloudpack ブログ - S3ってなんじゃ?(s3cmd編) -
オフィシャル:Amazon S3 tools: s3cmd : command line S3 client

2011-09-24

CでDevquiz2011スライドパズル その3

スライドパズルに関するアルゴリズムのサマリー

ソースさらし祭り(?)に参加されている人の解説などを含め今回調べたアルゴリズムを整理したページです。

広く浅く、全体を俯瞰できるようにすることを目標に書いてみます。

 ☆問題の定式化

駒数をKとすると可能な盤面はK!個あり、それらを要素とする集合Sを考える。

Sの各要素は駒を一回移動することで遷移できる要素と繋がっていると考えることで無向グラフとみなすことができる。

与えられた問題面ノードからゴールノードまでの経路探索問題と解釈できる。
なお、Kが36の場合K!は3.7×10^36となり、無限の要素を持つと思って考えていい。

今後、n,g,h,h'を以下の意味で使う。

n:与えられた盤面

g(n):スタートの盤面からnまでの駒の移動回数

h(n):nからゴールまでの最短経路の駒の移動回数

h'(n):h(n)の推定値。(マンハッタンディスタンスなどを利用したnからゴールまでの駒の移動回数の推定値)


 経路探索アルゴリズム:幅探優先探索

駒の移動回数の小さい順に探索していくアルゴリズム。

見つかったノードをキューに入れていく形で実装。

過去の盤面をメモリーに保存するため、メモリーサイズで探索できるノード数が限られる。

http://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

 経路探索アルゴリズム:深さ優先探索

ノードが途切れるか、ゴールに到達するまで深く探索していき、その後はバックトラック。

スライドパズルのような開いた木の最適解を求めるためには下記のIDDFSやIDA*のような手法を使う。

過去の盤面を保存しないのでメモリー消費は小さい。


http://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

 経路探索アルゴリズム:IDA*


深さ優先探索で以下の閾値を設けて探索を行う。

 g(n) + h'(n) <Threshold

ある閾値でゴールが見つからなかった場合は、閾値を徐々に増大させながら探索を繰り返す。

ここでh'(n)が以下を満たす時、最初に見つけた経路が最短経路である事が証明できる。

0 ≦ h'(n) ≦ h(n)


この閾値の評価を単に

  g(n) < Threshold

としたものは反復深化深さ優先探索(IDDFS)と呼ばれる。

木構造の根元に近い部分を何度も調べることになるため無駄のように見えるが、ノードの多くは木構造の底辺にあるため、それほどコスト増大にはならない。(深さNに応じてx^Nでノード数は増大するため、たとえばx=2の場合、高々2倍の演算量にしかならない)


http://ja.wikipedia.org/wiki/%E5%8F%8D%E5%BE%A9%E6%B7%B1%E5%8C%96%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

 経路探索アルゴリズム:A*

幅優先のキューをプライオリティキューにして、もっとも推定コストの小さいノードを優先して探索しているアルゴリズム。

推定コストとは

f(n) = g(n) + h'(n)

ここでIDA*同様h'(n)が以下を満たす時、最初に見つけた経路が最短経路である事が証明できる。

0 ≦ h'(n) ≦ h(n)

幅優先探索の拡張であるのでメモリが探索深度に応じ指数関数的に消費されていくため、ある程度以上の深度まで探索しようとすると、使われないノードを一旦破棄し必要に応じて再利用(SMA*)が必要になる。

http://ja.wikipedia.org/wiki/A*

 評価関数h'(n)

高得点を得ていたアルゴリズムはほぼA*かIDA*を利用したものだったが、これらのアルゴリズムでは評価関数h'(n)の精度が重要になる。
h'(n)がh(n)に近ければ近いほど演算量は小さくなるので、いかにh(n)に近い関数を見つけるかがとても重要!

以下で説明するようにいくつかの手法が考案されており、これらを組み合わせて使う(もっとも値の大きいh'(n)の値を利用する)こともできる。

 マンハッタンディスタンス(MD)
個々の駒に関してゴール位置への移動回数を計算したもの。

http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%B3%E3%83%8F%E3%83%83%E3%82%BF%E3%83%B3%E8%B7%9D%E9%9B%A2

パターンデータベース(PDB)
前もって特定のパターンとそのパターンのh(n)を計算しておき、それをハッシュ化して保存しておきh'(n)の計算に利用する手法。


http://www.ise.bgu.ac.il/faculty/felner/research/jairpdb.pdf

 ギャップ集合
MDを利用したh'(n)とh(n)とのギャップがいくつであるかに応じたデータベースをあらかじめ作っておく。
探索時にそのDBを参照し、ギャップに応じてMDに値を加算する。


http://www.jstage.jst.go.jp/article/tjsai/26/2/419/_pdf/-char/ja/

 転倒距離
駒の並びを順列と考え、小さい順に並んでいない駒の数(転倒が起こっている回数)を利用

http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html

 ウォーキングディスタンス
ゴール盤面で各行(または各列)に属している駒が、その盤面でそれぞれの各行(または各列)に何個あるかというパターンをデータベース化したもの。
PDBの一種(?)
4×4くらいまでは有効だが、5×5以上ではデータベースが膨大になり現実的ではない。

http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html

 最短経路以外の解を求める探索

ここまでは全て最短経路を求めるためのアルゴリズムだが、今回のDevquizの問題は与えられた移動可能駒数に余裕があり、参加者の多くは非最短解を求めるアルゴリズムを考案・採用されていた。

大別すると以下のパターンに分類できる。

 上限を守らない評価関数

上に述べたように任意の盤面nに対し

0 ≦ h'(n) ≦ h(n)

を満たすような評価関数であれば、最短経路である事が保障されますが、この上限をあえて守らない事でより早くゴールにたどり着こうという発想。

具体的には、MD値を各コマに対して足し上げる際に端の駒の重みを大きくしたり、駒の並び順に応じてペナルティスコアを加算したり等。

 段階を置いてゴールに辿りつこうという方法

いきなりゴール面までの探索をする代わりに、途中に中継点を置いて中継点までの探索を行い、中継点からゴールまでの探索を再度行う方法。

私が行った、端優先、ステップ実行はこれにあたる。
( 端優先、ステップ実行という名前は私が勝手に付けた)

 キューのサイズに上限を設ける方法

A*など幅優先系のアルゴリズムでプライオリティキューのサイズに上限を設け、上限に達したらプライオリティのもっとも低いノードをキューから削除する方法。

 経路探索アルゴリズム:双方向探索

逆方向からも探索する事で演算量を下げる方法。
やり方によっては最適解にもなる。

x^Nがx^(N/2)となり、大幅に演算量を下げることができる。

http://ja.wikipedia.org/wiki/%E5%8F%8C%E6%96%B9%E5%90%91%E6%8E%A2%E7%B4%A2