3年近くもほったらかしだったけど、衝動的にレンタルサーバを借りてブログを立ち上げた。
過去記事も一通り移行済みだけど、ここも残しておきます。
本屋で見かけたのでついうっかりと。Scalaの本は迷った挙句にやめたのに……大きさが手頃だからかも。
で,第1章 Getting Started と第2章 Clojureひとめぐり だけ読んでみた。以下メモ。
user=> #{} #{}
user=> (def visitors (ref #{})) #'user/visitors user=> (dosync (alter visitors conj "Stu")) #{"Stu"}
user=> {:Lisp "McCarty", :Clojure "Hickey"} {:Lisp "McCarty", :Clojure "Hickey"}
user=> ({:Lisp "McCarty", :Clojure "Hickey"} :Clojure) "Hickey"
user=> (:Clojure {:Lisp "McCarty", :Clojure "Hickey"}) "Hickey"
user=> (defn is-small? [number] (if (< number 100) "yes" (do (println "Saw a big number" number) "no"))) #'user/is-small? user=> (is-small? 101) Saw a big number 101 "no"
こないだのを参考にしてくれたらしい。
なんだか俺のコードよりもHaskellらしく見えるよ。
ところで,リンク先のコードだと検索するたびに suffix array というか suffix のリストを作っているように見える。俺の理解では,suffix array を利用するメリットというのは,suffix array を作るときには大量にメモリを必要とするけど検索するときには必要ない,ってことだと思うんだけど。
それはそれとして forever という関数を初めて知った。今度使ってみよう。
気がつけば12月も中旬だよ……。
少し前になるけど,「あとで試す」タグをつけといたやつをやってみる。これ↓:
具体的な手順はこっちのページで公開されている。
さて,順にやってみよう。
与えられた文字列のsuffix arrayを作成するプログラムを作成せよ.
import Data.List suffixArray :: String -> [Int] suffixArray xs = map fst $ sort' $ zip [1..] $ init $ tails xs where sort' = sortBy (\a b -> compare (snd a) (snd b))
実行例:
*Main> suffixArray "abcbccab" [7,1,8,2,4,6,3,5]
与えられた文字列に対し,その部分文字列を入力し,部分文字列が出現する全位置を列挙する検索プログラムを作成せよ.(ヒント: suffix array上の2分探索を行う)
二分探索とはいうものの,検索対象の部分文字列の出現箇所すべてを列挙するには,中央の値(suffix)の右か左を単純に無視してしまうわけには行かない。場合によっては左右両方にあるかもしれないから。なので,まずは整理してみる。
これをコードにするとこうだ:
import Data.List suffixArray :: String -> [Int] suffixArray xs = map fst $ sort' $ zip [1..] $ init $ tails xs where sort' = sortBy (\a b -> compare (snd a) (snd b)) suffixOf :: String -> Int -> String suffixOf s n = drop (n-1) s search :: String -> [Int] -> String -> [Int] search _ [] _ = [] search s ary sb = let n = (length ary) `div` 2 sfx = suffixOf s (ary !! n) in if sfx < sb then search s (drop (n+1) ary) sb else if sfx == sb then (ary !! n) : search s (drop (n+1) ary) sb else if isPrefixOf sb sfx then (search s (take n ary) sb) ++ [ary !! n] ++ (search s (drop (n+1) ary) sb) else search s (take n ary) sb
実行例:
*Main> search "abcbccab" (suffixArray "abcbccab") "ab" [7,1]
指定された1個のHTMLテキストファイルをメモリ中に読み込んで1個の文字列とし,それに対する suffix array をメモリ中に作成し,ユーザから入力された文字列を検索して,入力文字列が出現する全位置を列挙するプログラムを作成せよ.
ファイルを読み込んで,searchを適用して,あとは適当にフォーマットして出力すればいいだけだ。ファイルは課題のページからリンクしてるこのページをダウンロードして使った(ファイル名決めうち)。
module Main where import Data.List import System.Environment ( getArgs ) ------------------------------------------------------------------------------- filename = "CodeConvTOC.doc.html" main :: IO () main = do argv <- getArgs contents <- readFile filename substring <- return $ head argv mapM_ (putStrLn . format contents) $ search contents (suffixArray contents) substring format :: String -> Int -> String format str pos = show pos ++ ": " ++ take 10 (suffixOf str pos) ------------------------------------------------------------------------------- suffixArray :: String -> [Int] suffixArray xs = map fst $ sort' $ zip [1..] $ init $ tails xs where sort' = sortBy (\a b -> compare (snd a) (snd b)) suffixOf :: String -> Int -> String suffixOf s n = drop (n-1) s search :: String -> [Int] -> String -> [Int] search _ [] _ = [] search s ary sb = let n = (length ary) `div` 2 sfx = suffixOf s (ary !! n) in if sfx < sb then search s (drop (n+1) ary) sb else if sfx == sb then (ary !! n) : search s (drop (n+1) ary) sb else if isPrefixOf sb sfx then (search s (take n ary) sb) ++ [ary !! n] ++ (search s (drop (n+1) ary) sb) else search s (take n ary) sb -------------------------------------------------------------------------------
実行例:
^o^ >runhaskell suffixArray.hs File 10208: File Examp 1959: File Names 1664: File Names 2250: File Organ 1815: File Suffi 2422: Files</a>
ちょっと時間があいたけど続き。
以下の手順で,複数ファイルに対して全文検索を行うプログラムを作成せよ.
1. 指定された1個以上のm個のファイルをメモリ内で連結した長い文字列を作る.そのときにファイルの境 界に,テキストファイル中には通常は現れない文字(例えばヌル文字'\0'等)を入れ,検索時に複数ファイルを またいだ文字列にマッチしないようにしておく.
2. 1.で作った作った長い文字列中の文字位置から元のファイル名を得られるようにするための表を作る. 例えば,file1.html, file2.html, file3.htmlがそれぞれ100, 200, 300のファイルサイズをもつとき,[("file 1.html", 100), ("file2.html", 200), ("file3.html", 300)]というような表を作る(効率的な方法,プログ ラムしやすい方法を各自工夫せよ).
3. 課題1-3で作成したプログラムと,1.および2.で作ったデータを用いて,ユーザから入力された文字列を 検索し,入力文字列が出現するファイル名とファイル内の位置(ファイルの先頭から数えた文字数)を全て列 挙するプログラムを作成せよ.
課題1-3から変えたとこだけ:
main :: IO () main = do argv <- getArgs files <- mapM readFile $ tail argv let contents = concat $ intersperse "\0" files let table = makeFileTable (tail argv) $ map length files let substring = head argv mapM_ (putStrLn . format table contents) $ search contents (suffixArray contents) substri ng ------------------------------------------------------------------------------- format :: [(String, Int)] -> String -> Int -> String format t str pos = let (f, p) = filePos t pos in f ++ ": " ++ show p ++ ": " ++ take 15 (suffixOf str pos) ------------------------------------------------------------------------------- makeFileTable :: [String] -> [Int] -> [(String, Int)] makeFileTable fs ls = zip fs $ snd $ mapAccumL (\a x -> (a+x+1, a)) 1 ls filePos :: [(String, Int)] -> Int -> (String, Int) filePos (f:[]) n = (fst f, n - snd f + 1) filePos (f1:f2:fs) n | snd f2 < n = filePos (f2:fs) n | otherwise = (fst f1, n - snd f1 + 1) -------------------------------------------------------------------------------
元ファイルの表はファイル名とその開始位置をタプルにした。
実行例:
^o^ >runhaskell suffixArray.hs Intro CodeConvTOC.doc.html CodeCOnventions.doc.html CodeConvTOC.doc.html: 1063: Introduction</a CodeCOnventions.doc.html: 517: Introduction</h
今日はここまで。続きは明日……やれるといいなぁ。
ISBNを扱うのに ISBN Tools というライブラリを使っている。
なんでかっていうと ISBN_Tools.hyphenate_isbn13 っていうメソッドがあって,数字だけのISBNをハイフンの入ったISBNに変換してくれるのが使えると思ったからだ。
こんな感じ:
irb(main):006:0> ISBN_Tools.hyphenate_isbn13('9780672328848') => "978-0-6723-2884-8"
ところがこのメソッド,肝心の日本(グループ番号4)に対応してくれてない。
ソースを見たところ,data/ranges.dat にグループ番号と出版者記号の定義を追加すればいいみたいだ。
というわけでちょっと調べてみた。
日本国内のことなんだから日本のISBNを管理しているところへいけばいいんだろう,と思ったんだけど,その日本図書コード管理センターのサイトの中を探してみても規則で割り当ててるのか,どうもどこにも載ってない。
同じ不満をもっる人がネットのあちこちにいるみたいだな。どうなってんだ。
で,結局 ISBN の本家 International ISBN Agency のサイトでPDFを見つけた。これでいいんだよな。
これによると日本の出版者記号は下のような規則になっているようだ。
2ケタ | 00〜19 | ||
3ケタ | 200〜699 | ||
4ケタ | 7000〜8499 | ||
5ケタ | 85000〜89999 | ||
6ケタ | 900000〜949999 | ||
7ケタ | 9500000〜9999999 |
さて,ISBN Tools に戻ろう。
調べた成果を反映するには前述の data/ranges.dat に次の1行を追加すればいい。
4,00..19,200..699,7000..8499,85000..89999,900000..949999,9500000..9999999
カンマ区切りになってて,はじめの値がグループ番号,2つめ以降に出版者記号の連続する範囲を列挙している。これで日本の出版者にも対応するようになった。
irb(main):007:0> ISBN_Tools.hyphenate_isbn13('9784863540224') => "978-4-8635-4022-4"
10ケタのISBNでもできる。
irb(main):008:0> ISBN_Tools.hyphenate_isbn10('4873110238') => "4-87311-023-8"
id:edvakfさんがやってるのを見かけたので久しぶりに。
どう書く?org にはこれをポストしたんだけど:
import List steep xs = and $ zipWith (>) xs $ map sum $ tail $ tails xs
$ が多くてうっとうしいからがんばって無くしてみた。ついでに引数もなくなった。
import List steep2 = and . s (zipWith (>)) sums where s f g x = f x (g x) sums = map sum . tail . tails
なんかかえって解りにくいかも。
実行結果:
*Main> steep2 [32,16,8,4,2,1] True *Main> steep2 [31,16,8,4,2,1] False
自分用のメモ。
cf. Windows + Apache + FastCGI - h4yの日記
cf. WindowsでRuby on Rails その4 Ruby on RailsをFastCGIで動かす - 色々な事を忘れないよう忘備録と日記
FastCGIのダウンロードは公式サイトのダウンロードコーナーから。Apache のバージョンが 2.0.63 なので mod_fastcgi-2.4.2-AP20.dll をダウンロードした。これを mod_fastcgi.dll にリネームして,Apache の modules ディレクトリにコピー。
つぎは Ruby 側の準備。gem で fcgi をインストールしようとしたけど ruby のヘッダファイルがないって怒られる:
^o^ >gem install fcgi --remote Building native extensions. This could take a while... ERROR: Error installing fcgi: ERROR: Failed to build gem native extension. C:/usr/ruby/bin/ruby.exe extconf.rb install fcgi --remote can't find header files for ruby. Gem files will remain installed in C:/usr/ruby/lib/ruby/gems/1.8/gems/fcgi-0.8.7 for inspection. Results logged to C:/usr/ruby/lib/ruby/gems/1.8/gems/fcgi-0.8.7/ext/fcgi/gem_mak e.out
ググってみると,RubyForApache というのが見つかったので version 1.3.1 をダウンロード。なんか2005年って古いんだけど。
ファイルはインストーラなのでダブルクリックしてインストール。途中でインストールするコンポーネントを聞かれるので,mod_fastcgi 以外のコンポーネントのチェックをはずす。mod_rubyとmysql.soは今回はパス。
あと C:\Windows\System32\msvcp71.dll に書き込めないというメッセージが出るけど,これは無視して進める。
最後に Apache の設定。httpd.conf につぎの行を追加する。
LoadModule fastcgi_module modules/mod_fastcgi.dll AddHandler fastcgi-script .fcgi
Apache を再起動して終了。
テスト用のスクリプトはこんなの。
#! C:/usr/ruby/bin/ruby.exe require 'fcgi' FCGI.each_cgi do |cgi| print "Content-Type: text/plain\n\n" print "Hello world. This is FastCGI.\n" end
それと ExcecCGI を有効にしておく必要があるみたいなので .htaccess で設定する。
Options +ExecCGI
Ruby 1.9.1 もリリースされたことだし,新機能(Fiber と Array#cycle)を使ってFizzBuzz を書いてみたよ。d:id:takatoh:20070509:fizzbuzz のRuby版。
cf. Ruby 1.9.1 の歩き方 - るびま 0025号
# -*- encoding: utf-8 -*- fizzbuzz = Fiber.new do fizz = ["", "", "Fizz"].cycle buzz = ["", "", "", "", "Buzz"].cycle n = 1 while s = fizz.next + buzz.next Fiber.yield(s == "" ? n.to_s : s) n += 1 end end 100.times{ puts fizzbuzz.resume }
実行結果は省略。
Fiber ってスレッドに似た云々とかいうより,途中で評価を中断出来る(&途中の値を返せる)クロージャだと考えた方がわかりやすいんじゃないかと思った。
MXML は,ウィンドウの構成を記述する。こんな感じ。
<?xml version="1.0" encoding="utf-8"?> <mx:WindowedApplication xmlns:mx="http://www.adobe.com/2006/mxml" layout="absolute" title="Hello AIR"> <mx:Script> <![CDATA[ private function hello():void { myLabel.text = "Hello AIR!"; } ]]> </mx:Script> <mx:Label id="myLabel" horizontalCenter="0" verticalCenter="0"/> <mx:Button id="myButton" label="click" horizontalCenter="0" verticalCenter="20" c lick="hello();"/> </mx:WindowedApplication>
ルートエレメントは WindowedApplication で,これがウィンドウ全体を表す。この例では,他に Label と Button が配置されている。
配置できるのはコントロールとかコンテナとか呼ばれるもの。実体は ActionScript のクラスで,パッケージにまとまっている。わかりやすい一覧表みたいなものは見つからないんだけど,リファレンスのこのあたりに情報がある。
ここまで Adobe のページ。ここからは参考にした記事など。