集合知プログラミング 5.1 5.2 5.3 最適化

集合知プログラミング

今回もサンプルコード(python)から、Rubyへの書き換えに挑戦しました。
目標は一応サンプルコードに忠実にです。
5章の5.1から5.3までの、コスト関数の所までを書いてみました。
出版社から配布されているサンプルコードに間違いがいくつかあり苦労しました。

サンプルコードの正誤

PCI_Code\PCI_Code Folder\chapter5\optimization.pyの32,33行目

　　# サンプルコードのコード
    out=flights[(origin,destination)][int(r[d])]
    ret=flights[(destination,origin)][int(r[d+1])]

    # 正しいコード
    # *2を忘れている
    out=flights[(origin,destination)][int(r[d*2])]
    ret=flights[(destination,origin)][int(r[d*2+1])]

この後も、同じような箇所がいくつかあり、すべて書き換えます。
その他には69行目の演算子が逆でした。
まだまだ、間違っている所はあると思います。

ちなみに、本には正しいコードで書かれています。
ですので、サンプルコードをそのまま実行せず、本の通りに修正すれば問題ないです。

今回作成したプログラム

今回もいつもの通り、"optimization.rb"と名付けました。
フライトデータファイルはここのものを利用します。

http://kiwitobes.com/optimize/schedule.txt

#!/usr/bin/ruby
require 'date'
require 'time'

$people = [
  ['Seymour', 'BOS'],
  ['Franny','DAL'],
  ['Zooey','CAK'],
  ['Walt','MIA'],
  ['Buddy','ORD'],
  ['Les','OMA']
]

# ニューヨークのラガーディア空港
$destination='LGA'

$flights=[]

# テキストファイルから配列に格納
ifh = open('schedule.txt', 'r')
lines = ifh.readlines
for line in lines do
  line_sp=line.strip().split(/\s*,\s*/)
    $flights << [
	line_sp[0],
	line_sp[1],
	line_sp[2],
	line_sp[3],
	line_sp[4].to_i
    ]
end	
	
module Optimization
　# 時刻を分に直す関数
  def self.getminutes(t)
    # 文字列から日付オブジェクトに変換
    x = Time.parse(t)
    return x.hour * 60 + x.min
  end

  def self.printschedule(r)
    # 人数を割り出す
    ran_r = r.length / 2
    d = 0
    ran_r.times {|d|
	# 名前を取り出す
	name = $people[d][0]
	#　出発地を取り出す
	origin = $people[d][1]
	#　配列から行きの便を取り出す
	out_list = $flights.select{ |f|
	  f[0] == origin && f[1] == $destination
	}
	out = out_list[r[d*2]]
	#　配列から帰りの便を取り出す
	ret_list = $flights.select{ |f|
	  f[0] == $destination && f[1] == origin
	}
	ret = ret_list[r[d*2+1]]
	print name, " ",
            origin, " ",
            out[2], "-", out[3], " ",
            "$", out[4], " ",
            ret[2], "-", ret[3], " ",
            "$", ret[4], "\n"
    }
  end
  
  #コスト関数
  def self.schedulecost(sol)
    totalprice=0
    latestarrival=0
    earliestdep=24*60
    
    sol_r = sol.length / 2
    sol_r.times {|d|
      #　行きと帰りのフライトを得る
      origin = $people[d][1]
      #　配列から行きの便を取り出す
      outbound_list = $flights.select{ |f|
        f[0] == origin && f[1] == $destination
      }
      outbound = outbound_list[sol[d*2]]
      #　配列から帰りの便を取り出す
      returnf_list = $flights.select{ |f|
	f[0] == $destination && f[1] == origin
      }
      returnf = returnf_list[sol[d*2+1]]
      
      # 運賃総額Total price は出立便と帰宅便すべての運賃
      totalprice+=outbound[4]
      totalprice+=returnf[4]
      
      # 最も遅い便と最も早い便を記録
      if latestarrival<getminutes(outbound[3])
        latestarrival=getminutes(outbound[3])
      end
      if earliestdep>getminutes(returnf[2])
        earliestdep=getminutes(returnf[2])
      end
    }  
    
    # 最後の人が到着するまで全員で待機
    # 帰りも空港にみんなで来て自分の便を待つ
    totalwait=0
    sol_r.times {|d|
      #　行きと帰りのフライトを得る
      origin = $people[d][1]
      #　配列から行きの便を取り出す
      outbound_list = $flights.select{ |f|
        f[0] == origin && f[1] == $destination
      }
      outbound = outbound_list[sol[d*2]]
      #　配列から帰りの便を取り出す
      returnf_list = $flights.select{ |f|
	f[0] == $destination && f[1] == origin
      }
      returnf = returnf_list[sol[d*2+1]]
      
      # それぞれ待ち時間を足し合わせて、総待ち時間を算出する
      totalwait+=latestarrival - getminutes(outbound[3])
      totalwait+=getminutes(returnf[2]) - earliestdep     
    }  
    
    # レンタカーの追加料金が必要なら50ドル追加
    if latestarrival<earliestdep
      totalprice+=50
    end
    
    return totalprice+totalwait
  end
end

確認

irbで確認

irb(main):001:0> load 'optimization.rb'
=> true
irb(main):002:0> s=[1,4,3,2,7,3,6,3,2,4,5,3]
=> [1, 4, 3, 2, 7, 3, 6, 3, 2, 4, 5, 3]
irb(main):003:0> Optimization.schedulecost(s)
=> 4585
irb(main):004:0> Optimization.printschedule(s)
Seymour BOS 8:04-10:11 $95 12:08-14:05 $142
Franny DAL 10:30-14:57 $290 9:49-13:51 $229
Zooey CAK 17:08-19:08 $262 10:32-13:16 $139
Walt MIA 15:34-18:11 $326 11:08-14:38 $262
Buddy ORD 9:42-11:32 $169 12:08-14:47 $231
Les OMA 13:37-15:08 $250 11:07-13:24 $171
=> 6

補足

getminutes関数

ある時刻が一日の中で何分目かを出す関数です。
時間計算をしたいので、引数で入ってきた文字列を日付オブジェクトに変換します。
strptimeがうまく使えず、今回はTime.parseを使いました。
しかし、もっといい方法がないかなと思っています。

メンバー毎のフライトの割り出し

Integerクラスのtimesメソッドを用いました。
これはブロック内を指定回数だけ実行します。
カウンタも使うことができます。

「初めてのRuby」では6.3.6イテレータで紹介されています。

初めてのRuby

この処理は同じような所が何回も出てくるので、関数でまとめてもよかったかもしれません。

結果の出力（printメソッド）

サンプルコードでは、文字列整形して出力していたのですが
自分ではうまくいかず不格好な感じになってしまいました。

フライト便の取り出し

メンバーの乗るフライト便は、テキストファイルから配列に格納し検索します。
サンプルコードでは、出発地・目的地をキーにその他の項目を格納していました。
Rubyで同じような方法が見つからず、とりあえず全部を配列に格納しました。
この配列の0番目には出発地が、1番目には目的地があるので
それをキーに検索しさらに配列にいれ、そこから解の表現のリストと照らしあわせました。
その配列要素の検索には、Array.selectを用いました。

とりあえず動くものができたという感じです。
pythonの配列やハッシュについて勉強する必要がありそうです。

Yahoo!ブリーフケースの有料化とYahoo!プレミアムの値上げ

Yahoo!ブリーフケース、Yahoo!プレミアム会員/Yahoo! BB会員 専用サービス化のお知らせ
http://info.photos.yahoo.co.jp/briefcase/index.html

12月1日より、Yahoo!プレミアム会員/Yahoo! BB会員専用サービスになるとのこと。

それに伴い、Yahoo!プレミアムの値段は294円から364円になるそうです。

特典も楽しみも大幅アップ　Yahoo!プレミアムが12月1日に生まれ変わります！ - Yahoo!プレミアム:
http://premium.yahoo.co.jp/info/powerup.html

いくつかサービスもリニューアルされるらしいので、それに期待するとしましょう。

Rubyのコーディングスタイルについて

あとからコードを見直す時、きれいに整形されていた方が、言うまでもなく理解が早いです。
前回の規約に続き、今回はさらにコーディングスタイルに絞って参考になったページを羅列します。

Ruby and Rails Style Guide
http://www.pathf.com/blogs/ruby-and-rails-style-guide/

ここが一番良かったです。
以下内容の抜粋紹介です。

if文の例

だいたいここに書いてある感じでコーディングしていましたが、if文ここまで短くかけるとは思いませんでした。
逆に驚きでした。

# 良い例
if active?
  x = 3
else
  x = 5
end

# 悪い例
# しかしこういう感じでも書ける
x = active? ? 3 : 5
x = if active? then 3 else 5 end

長いコードの場合

ついつい、悪い例のように書いてしまうことが多いです。
他にも長い命令のインデントとかは、結構我流でやってしまっていた所があったので参考になりました。

# 悪い例
x = if a_really_long_boolean_function
then a_long_true_value
else a_long_false_value
end

# 良い例
x = if a_really_long_boolean_function
      a_long_true_value
    else
      a_long_false_value
    end

あとは演算子の間はスペースの事や、Railsのコーディングスタイルについても書いてありました。

あとは日本語で参考になったところ。

Ruby のコーディングスタイル
http://i.loveruby.net/ja/ruby/codingstyle.html

Rubyの記事ではないですが。

コーディングスタイルの常識をぶち壊せ
http://codezine.jp/article/detail/3055

ここらを参考にして、今後は見やすいコードを書いていきたいと思います。

Ruby1.9のインストールとそのgemを動かすまで（Windows）

今回は、ruby1.9のWindowsへのインストールについてです。
約1年前に書いた記事（d:id:ky2009:20071016:1192542741）では、One-Click Installerを使いました。
1.9系では、gemが標準装備になったので、これを使う必要はありません。
また当たり前ですが、1.9系は配布されていません。

ruby本体のダウンロード

1.9はまだ開発版という位置づけらしいので、安定版（1.8系）を求められる方はOne-Click Installerでいいと思います。
この日記を書いた時点では、1.9.1はまだ不安定らしので1.9.0の最新版をダウンロードしました。

http://www.garbagecollect.jp/ruby/mswin32/ja/
http://www.garbagecollect.jp/ruby/mswin32/ja/download/develop.html

今回は「ruby-1.9.0-2-i386-mswin32.zip」をダウンロードしました。
これを解凍し、フォルダ名を「ruby」にします。
そして「C:\ruby」に置きました。
以後はこのフォルダ構造で説明します。

パスを通す

次にrubyをコマンドラインを使えるようにします。
わからない方は、ここを参照してみてください。

http://pub.cozmixng.org/~the-rwiki/rw-cgi.rb?cmd=view;name=Ruby+Install+Guide%3A%3AWindows%A4%C7%A4%CEPATH%A4%CE%C4%CC%A4%B7%CA%FD;num_links=all%23link

これでRubyを使うことができます。

gemを使うまで

次にgemの動作を確認してみます。

gem -v

これが動きませんでした。
「zlib.dll」がないと言われました。

zlibの入手

zlib.dllのダウンロード
http://www.rubylife.jp/railsinstall/rubygems/index3.html

このページによると、http://www.zlib.net/からダウンロードできました。
ダウンロードしたものは、「zlib1.dll」なので「zlib.dll」にリネームし、「C:\ruby\bin」に置きます。
これでコマンドが通りましたが、「gem update」をしてみると以下のようなエラーがでました。

libeay32.dll、ssleay32.dllの入手

これは、足りないと言われたものを順番に入れていくしかないようです。

OpenSSL for Windows
http://www.limber.jp/?Software%2FOpenSSL%20for%20Windows

ここによると、「ssleay32.dll」はwindowsでopensslをするのに必要なようです。

libeay32.dll、ssleay32.dllのダウンロード
http://d.hatena.ne.jp/troopergreen/20071109/1194586892

こちらで簡単な入手方法が説明されていました。
ここに書かれているように、一緒に「libeay32.dll」も入れておきます。

http://jarp.does.notwork.org/win32/

ここの「openssl-0.9.〜」のファイルをダウンロードして、同じようにbinに入れます。
これでやっとupdateもできました。

最初から入れて配布してくれないのでしょうか。
あと、One-Click Installerのgemの動作もなんとなくあやしい。
いつも環境作りは一筋縄ではいきません。

Rubyコーディング規約のまとめ

命名規則や演算子を忘れてしまった時に、よくこれらのページを見ます。
他にもインデントや条件規則の記述のしかたなど、簡潔にまとめられています。
カンニング以外にも、他言語習得者ならこういうのを見た方が便利かもしれません。

Rubyコーディング規約
http://shugo.net/ruby-codeconv/codeconv.html

まつもとさんも参照しているもの。
一番標準なのでしょうか。
最終更新が2007年です。

那由多屋版Rubyコーディング標準
http://labs.nayutaya.jp/?ruby-coding-standards

Stack Stock Booksなどのサービスを提供しているnayutayaで定義されたもの。
同じく2007年です。

RubyCodingStyle
http://www.loveruby.net/w/RubyCodingStyle.html

少し古めですが2005年に作成されたものです。

Ruby Language Coding Rule
http://lab.lowreal.net/trac/wiki/CodingRule/Ruby

こうしてみると、組織や団体によって微妙にちがうことがわかりました。
多人数で開発する場合は、しっかりとルールを決めておくべきなんですね。

追記11/26

VB,C,Javaなどのコメント規約

コメントでいただいたものです。
いわゆるコメントアウトについての規約です。
他言語でも結構参考になりそうです。

〜 コメント規約(コーディング規約) 〜　
ドキュメント自動生成ツール【A HotDocument】
http://www.hotdocument.net/faq/man.html

restful_authenticationの導入

restful_authenticationとは、Rails用のユーザ認証プラグインのことです。
Rails2.0以降は、このプラグインが大勢のようです。
今後、少し使いそうだったので、試してみました。

Railsレシピブック 183の技

Railsレシピ本では、153項で紹介されています。
でも、正直そこでは中途半端にしか紹介されていなかったので、他に調べてみました。

プラグインのインストール

プラグインはアプリケーションごとに導入します。
導入したいアプリケーションのルートディレクトリで以下を実行

$ruby script/plugin install http://svn.techno-weenie.net/projects/plugins/restful_authentication/ 

認証用のコントローラやライブラリを生成

$ruby script/generate authenticated user sessions

テーブルの用意

ユーザ情報を格納するテーブルを作ります。

$ruby rake db:migrate

ルーティングの設定

ログイン・ログアウトなどを手軽に使えるよう、config/routes.rbを編集します。

ActionController::Routing::Routes.draw do |map|

  #以下5行を追加
  map.resources :users
  map.resource  :session
  map.signup '/signup', :controller => 'users', :action => 'new'
  map.login  '/login', :controller => 'sessions', :action => 'new'
  map.logout '/logout', :controller => 'sessions', :action => 'destroy'
end

ここまでは、レシピ本にも載っています。

ちなみに、このルーティングで、それぞれのURLは例えば以下のようになります。

ユーザ登録	http://localhost:3000/signup
ログイン	http://localhost:3000/login
ログアウト	http://localhost:3000/logout

コントローラの設定

次に、認証機能をコントローラ全体に適用させます。
まず、「app/controllers/session_controller.rb」と「app/controllers/users_controller.rb」にある「include AuthenticatedSystem」の行をカットまたはコメントアウトします。両方とも削らないとうまくいきませんでした。

class UsersController < ApplicationController
  # Be sure to include AuthenticationSystem in Application Controller instead
  include AuthenticatedSystem

class SessionsController < ApplicationController
  # Be sure to include AuthenticationSystem in Application Controller instead
  include AuthenticatedSystem

そして、そのコードを「app/controllers/application_controller.rb」に追加します。

class ApplicationController < ActionController::Base
  # include AuthenticatedSystemのコードを追加
  include AuthenticatedSystem

これで認証機能を、アプリケーション全体で使うことができます。
詳しくは下の所などで紹介されていました。

restful_authentication
http://rektunpe.sakura.ne.jp/diary/?date=20071222

restful_authenticationを触ってみた
http://d.hatena.ne.jp/idesaku/20080430/1209579996

restful_authenticationプラグイン
http://d.hatena.ne.jp/tsimo/20080323/1206277929#c

認証のフィルタの設定

最後に認証が必要なコントローラに、アクションにアクセスする前に認証するように設定します。
例として、app/controllers/hoge_controller.rbに設定をします。

class HogeController < ApplicationController
  # before_filter :login_requiredのコードを追加
  before_filter :login_required

これでこのアクションのページを見る前に認証が必要になります。
一応全部のコントローラに加えておくといいと思います。

このように認証機能の核はできましたが、実用にはもう少しカスタマイズする必要がありそうです。

発展的な使い方

自分のためにもここにメモしておきます。
余裕があれば、ここまで実装してみたいです。

railsforumのrestful_authenticationは素晴らしい！それを見てRESTfulの理解も深まる
http://d.hatena.ne.jp/zariganitosh/20080803/1217836912

以下のような機能が紹介されています。

• メールによるアクティベーション
• パスワード忘れの処理
• ユーザー情報の編集
• アクセス権による制限
• administrator権限によるユーザー管理
• OpenIDによるログイン

同じくメールによるアクティベーションについて

Restful Authentication with rails 2
http://www.avnetlabs.com/rails/restful-authentication-with-rails-2

restful authentication plugin
http://d.hatena.ne.jp/cuspos/20080725

結局RESTfulが何なのかわかりませんでした。聞いたことはあったのですが。
時間があれば、勉強してみたいです。

「はてなブックマーク」新バージョンが11月に公開

はてなブックマーク、新バージョンの公開日決定！
http://hatena.g.hatena.ne.jp/hatenamagazine/20081002

はてブが11月25日にリニューアルするそうです。
前の日記(d:id:ky2009:20080912:1221207741)に書いたように
ぜひインポート機能を実装していただきたいです。