第5回「ふつうのHaskell読書会」＠CSNAGOYA 開催しました。

5月 12th, 2008 admin

5月11日に名古屋の芸術創造センターにて「ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門」の読書会を行いました。

関数型言語の勉強は楽しい！

正確に言うと、今までやったことの無いタイプの言語の勉強は楽しい。です。
オブジェクト脳（オブ脳）というのがあるように関数型言語脳というのがあるらしいとわかってきたのでとても楽しくなっています。
たとえば前回やった練習問題に「読み込んだファイルをnバイトごとに改行して出力せよ。」というのがあって、僕は手続き型言語脳なのでRubyでいうなら下記のように、nバイトあるかどうか調べ、その結果によって改行を加えるというHaskellのコードを書いたんです。

PLAIN TEXT
RUBY:
  1. str = STDIN.read
  2.  
  3. def splitAt(i,str,ans = "")
  4.   if str.length> i
  5.     tmp = str[0,i]
  6.     str[0,i] = ""
  7.     ans += splitAt(i,str,tmp)
  8.     ans
  9.   else
  10.     ans += str
  11.   end
  12. end
  13.  
  14. p splitAt(6,str)

しかし、参加者の1人の方が関数型言語を普段から使われている方で、その人が書いたコードは「読み込んだ文字列をnバイトずつ取り出して改行を加える。それが空リストになるまで繰り返す」というものでした。

PLAIN TEXT
RUBY:
  1. main = do cs <- getContents
  2.       putStr $ unlines $ map fold $ lines cs
  3.  
  4. fold line = case splitAt 6 line of
  5.         (x,[]) -> x
  6.         (x,xs) -> x ++ "\n" ++ fold xs

リストを操作して、それが空になるまでなにかを繰り返す。うーん！美しい！
これが関数型言語脳かぁぁ！と感動しました。

そしてさらにうれしいのは、僕はそんな方法はまったく思いつかなかったものの、教えてもらえばすごく当然で美しい方法だと簡単に理解できたことです。そんな関数型言語に片足をつっこんでいる今の状態はすごく愉快です。プログラマーの人ならこの感覚わかってもらえるんじゃないでしょうか。

やっぱりプログラミングは楽しい

さっきまでまったく分からなかったことが、今になってみると「なぜ分からなかったのか」すらわからなくなるぐらいの勢いで理解するというような、脳みそのミソが一瞬で上質でマイルドな感じに変わる超体験がプログラミングの学習のときにはよく起こる。僕はまだヘッポコプログラマとはいえ、ヘッポコゆえにそういう理解の壁を越える体験を何度もしてきたので「ああ、またこの感覚か～」と理解の神様の降臨の予兆を感じると楽しくてしょうがなかったりします。
いつかはわからないし、まだ何ヶ月もかかるかもしれないけど、あるとき突然脳みそに新しい考え方がすっかりインストールされる時がくるってのを確信する。そんな時僕はいつもアバッキオの同僚の言葉を思い出します。

「 『結果』だけを求めていると、人は近道をしたがるものだ…近道した時、真実を見失うかもしれない。やる気も次第に失せていく。大切なのは『真実に向かおうとする意志』だと思っている。向かおうとする“意志さえあれば”いつかはたどり着くだろう？向かっているわけだからな…違うかい？」

まぁちょっとポジティブすぎるし、「Haskellごときで幸せになれていいね～」という先輩方の声も聞こえてきそうですが、最近はそんな感じで楽しくてしかたない勉強会なので「PHPerにもできる！Haskell勉強会」是非ご参加ください。という勧誘で本エントリーを締めさせていただきます。

Posted in CSNAGOYA, 今日のコード, 勉強会 | 1 Comment »

キュー

5月 8th, 2008 admin

今日も「アルゴリズムとデータ構造シリーズ」です。本日は「キュー」について。本当はスタックで逆ポーランド記法の式の計算をする予定でしたが面白くないのでスキップします。（逆ポーランド変換ならトライしますが）

キューとは

キューとは最初に入れたデータを最初に取り出すと言う特徴を持つデータ構造。行列などに例えられる。
「先入れ先出し」「First in first out(FIFO)」などと呼ばれる

キューではデータを入力することを「エンキュー」「push」などと表現し、出力させることを「デキュー」「pop」と表現する。
スタックに比べるとキューはWi○MXのあれとかプリンタのあれとか、そもそもqueueの直訳が待ち行列ですって感じで説明しやすい。

キューのデータ構造を配列で表現しようとするととても大きな配列が必要になるため、適当な大きさの配列の頭とお尻をくっつけて使う「リングバッファ」という方法がよくとられます。
リストを使ってキューを実現すればこの問題は発生しないのですが、今回は勉強なのでリングバッファを使ったキューを実装しました。

コード

PLAIN TEXT
RUBY:
  1. #Queue
  2. $KCODE = "SJIS"
  3. QUEUE_EMPTY = -1
  4.  
  5. class Queue
  6.   def initialize(max)
  7.     @queue = Array.new()
  8.     @max = max
  9.     @first = 0
  10.     @last = 0
  11.   end
  12.  
  13.   def enqueue(val)
  14.     if((@last + 1)%@max == @first)
  15.       p "ジョブが満杯です"
  16.     else
  17.       @queue[@last] = val
  18.       @last = (@last+1)%@max
  19.     end
  20.   end
  21.  
  22.   def dequeue()
  23.     ret = nil
  24.     if @first == @last
  25.       return QUEUE_EMPTY
  26.     else
  27.       ret = @queue[@first]
  28.       @first = (@first+1)%@max
  29.       return ret
  30.     end
  31.   end
  32.  
  33.   def print_all()
  34.     i = @first
  35.     while i != @last
  36.       print @queue[i].to_s + " "
  37.       i = (i+1)%@max
  38.     end
  39.     print "\n"
  40.   end
  41. end
  42.  
  43. queue = Queue.new(5)
  44. i = nil
  45. while i != 0 do
  46.   print "現在のキュー\n"
  47.   queue.print_all
  48.   print "コマンドを入力して下さい\n0:終了 1:ジョブをためる 2:ジョブを実行\n"
  49.   i = gets.chomp.to_i
  50.  
  51.   case i
  52.     when 1
  53.       print "ジョブの識別番号（1~1000）を適当に入力してください："
  54.       j = gets.chomp.to_i
  55.       queue.enqueue(j) if (j>= 1 && j <= 1000)
  56.  
  57.     when 2
  58.       j = queue.dequeue
  59.       if j == QUEUE_EMPTY
  60.         print "ジョブがありません\n"
  61.       else
  62.         print "識別番号" + j.to_s + "のジョブを実行\n"
  63.       end
  64.   end
  65. end

実行画面
queue.gif

まとめ

キューを使うようなプログラムを書いてみたいと思った。キューかっこいい！
あと、BASICみたいなプログラムが書けておもしろかった。

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

Posted in Ruby, アルゴリズムとデータ構造, 今日のコード | 1 Comment »

スタックを使ってHTMLの括弧の対応を調べる

5月 7th, 2008 admin

昨日学んだスタックの応用でHTMLなどの括弧の対応が正しく取れているかどうかを判定するスクリプトを書きました。
"< "と">"が正しい順番で同じ数になっているかどうかを判定します。

前回リストを使ったスタックを作りましたが今回はRubyの配列Stackを使います。

コード

#>ruby stack.rb < example.html
って感じで使います。

PLAIN TEXT
RUBY:
  1. $KCODE = "SJIS"
  2. str = STDIN.read
  3.  
  4. stack = Array.new
  5. str.scan(/./) do |c|
  6.   stack.push(c) if c == "<"
  7.   if c == ">" && stack.pop.nil?
  8.       p "括弧の対応が正しくありません。"
  9.       break
  10.   end
  11. end
  12.  
  13. p "括弧の対応が正しくありません。" if stack.size> 0

まとめ

与えられた入力を1文字ずつ処理し、開き括弧（＜）が来たらスタックにプッシュし、閉じ括弧（＞）が来たらポップします。そうすると正しいHTMLの場合は最後にスタックが空になります。
なのでスタックアンダーフローの時と、最後にスタックにデータが残った場合はHTMLにエラーがあるということになるというアルゴリズムです。

括弧の対応を調べるスクリプトを書けと言われるとなんだか複雑なものを考えてしまいますがスタックを使うとこんなに簡単に書けるんだということですね。スタック便利。

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

Posted in Ruby, 今日のコード | 1 Comment »

スタック

5月 6th, 2008 admin

まだまだ続く「アルゴリズムとデータ構造シリーズ」です。今回からスタック＆キューについてです。

スタックとは

スタックとは最後に入れたデータが最初に取り出される特徴をもつデータ構造の一つ。
「後入れ先出し」「Last in first out(LIFO)」などと呼ばれる。
スタックではデータを入力することを「積む」「Push」などと表現し、出力させることを「取り出す」「Pop」と表現する。
スタックが空なのにデータを取り出そうとしてしまうことをスタックアンダーフロー、逆にスタックが一杯になっているのにデータを積もうとしてしまうことをスタックオーバーフローと言う。

Rubyの場合は配列にpopとpushメソッドが標準であるため配列をスタックとして簡単に使うことができる。
さらにRubyの場合には配列のサイズも動的に変更できるため、いつも以上に無駄な感じがするので前回作ったリストを使って（まじめに？）スタックを書いた。

コード

PLAIN TEXT
RUBY:
  1. #Stack
  2. class Node
  3.   attr_accessor :prev,:next,:data
  4.   def initialize(data)
  5.     @data = data
  6.   end
  7. end
  8.  
  9. class Stack
  10.   def initialize()
  11.     @current_node = Node.new(nil);
  12.     @current_node.prev = nil
  13.   end
  14.  
  15.   def pop
  16.     #スタックのサイズが０ならnil
  17.     if @current_node.prev.nil?
  18.       nil
  19.     else
  20.       @current_node = @current_node.prev
  21.       @current_node.data
  22.     end
  23.   end
  24.  
  25.   def push(x)
  26.     #スタックにデータを積む
  27.     @current_node.data = x
  28.     #次のノードを用意しリンクする
  29.     new_node = Node.new(x)
  30.     @current_node.next = new_node
  31.     new_node.prev = @current_node
  32.    
  33.     #新しいノードをセットする
  34.     @current_node = new_node
  35.   end
  36. end
  37.  
  38. stack = Stack.new()
  39. stack.push(1)
  40. stack.push(2)
  41. stack.push(3)
  42. p stack.pop() # 3 <-最後に入れたのが最初にでてきている
  43. p stack.pop() # 2
  44. p stack.pop() # 1 <-最初に入れたのが最後にでてきている
  45. p stack.pop() # nil <-スタックアンダーフロー

応用

スタックに配列を使い、データの出し入れに配列のpopとpushメソッドを使用した場合と比較しました。
それぞれ１から10000までのデータをpushしてpopするというものです。以下Ruby配列版のコードです。

PLAIN TEXT
RUBY:
  1. #Stack
  2. stack = Array.new()
  3.  
  4. 10000.times do |i|
  5.   stack.push(i)
  6. end
  7.  
  8. until stack.pop == nil do
  9. end

私の環境でRuby配列版が4.79秒、リスト版が1.79秒と2倍以上の差が開く結果になりました。
配列のサイズをガンガン広げるより早いんじゃないかと期待したんですが・・・Rubyのコードを読めばわかるのかな？

まとめ

スタックはとても単純で「だからなんなの？」という感じもしなくもないんですが、すごい便利な使い方があったりして驚かされます。
次回はこの応用として、括弧の対応調べとか逆ポーランド電卓にチャレンジしてみます。

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

Posted in Ruby, 今日のコード | 2 Comments »

PHPで画像の縮小＋キャッシュ

4月 29th, 2008 admin

いつもはphpThumbというのを使っていて、これは十分に強力で便利なんですけど重厚すぎる感じがするのでライトな感じのものをいろいろ組み合わせて作ってみました。

やりたいこと

  • 縮小画像をPHPで自動生成したい
  • 毎回自動生成するのは嫌だからキャッシュしたい

手順

便利なライブラリを入手

Gen-X-Design | Ian Selby » PHP Thumbnailer Class v2.0
これは画像縮小用のライブラリ。ファイルを１つインクルードするだけで使える。しかもサンプルコードが超簡単。

ファイルの配置＋ファイル作成

PHP Thumbnailerをダウンロードしたら下図のように配置します。.htaccessとcacheフォルダも作ります。cacheは書き込み可能にしておいてください。これらはPHP THumbnailerにキャッシュ機能を追加するために使います。
tree2.jpg

使ってみます。

./img/csnagoya.jpgってファイルを400x300に縮小して表示したいと仮定して、こんな感じでHTMLを書きます。（cacheにはこんなファイルはありませんが気にしなくて大丈夫です）

index.html

PLAIN TEXT
HTML:
  1. <img src="./img/thumb/cache/400x300_csnagoya.jpg" alt="" />

.htaccess

PLAIN TEXT
CODE:
  1. <ifmodule mod_rewrite.c>
  2. RewriteEngine on
  3. RewriteCond %{REQUEST_FILENAME} ^.*$
  4. RewriteCond %{REQUEST_FILENAME} !-f
  5. RewriteRule ^.*/([0-9]+)x([0-9]+)_(.*)(jpg|gif|pnd)$ /img/thumb/show_image.php?width=$1&height=$2&filename=../img/$3$4 [R]
  6. </ifmodule>

.htaccessをこんな感じにします。んで、次が最後です

show_image.php

PLAIN TEXT
PHP:
  1. $filename = 'cache/'.$_GET['width']."x".$_GET['height']."_".basename($_GET['filename']);
  2.  
  3. include_once('thumbnail.inc.php');
  4. $thumb = new Thumbnail($_GET['filename']);
  5. $thumb->resize($_GET['width'],$_GET['height']);
  6. $thumb->save($filename,100);
  7. $thumb->show();
  8. $thumb->destruct();

以上で終わりです。これで一回目のアクセスのときにcache以下に400x300_csnagoya.jpgというファイルが作られて、二回目以降のアクセスにはキャッシュを読みに行くという構成になりました。phpThumbではキャッシュを読むときもphpを読み込む必要があったりしますが、この方法ならphpを読み込まずしてキャッシュを表示できるので高速です。

注意

  • ファイル数が多いときには注意（cache内をディレクトリで分けたり）
  • cacheが勝手に消えない

参考サイト

画像もDBに格納して管理する ―扱いがめんどうなLOB(ラージオブジェクト)は使わない方法

Posted in PHP, 今日のコード | 2 Comments »

« Previous Entries