countコマンドのRuby版アルゴリズムにHaskell/Pythonも合わせてみた＋メモ化に関する疑問

こちらのベンチマークで一位を取ったHaskell vs Python vs Ruby(ファイルの中身の文字数、ワード数、行数を表示するコマンド） - しんちゃんの日記Rubyのアルゴリズムに、Haskell/Pythonもコードを合わせて再度、ベンチマークを取り直してみました。

結論から言うと、Rubyが一位は変わらなかったですが、Pythonがかなり肉薄。Haskellは、０．５秒ほど高速化しました。

これは、Python/Rubyはファイルを読み込んだ時点で、長さもカウントしてオブジェクト内の変数に格納していると考えられるためで、純粋に文字数をカウントしてしまうHaskellのlength関数はどうしても不利になってしまいます。
（それでも、実用的な速度で収まっているのはさすがコンパイラ言語で、Linuxのソースコード程度なら、まだHaskellの方が速かったりします）

では、各言語のソースコードと、ベンチマーク結果です。（条件を限りなく同じにするため、Rubyもベンチ取り直してます）

まずは、コードから

Haskell

>|haskell|
import System.Environment

main = getArgs >>= \fnames ->
mapM readFile fnames >>=
mapM_ (\(x,y) ->
putStrLn $ concat [x,
"\nchars = ", show $ (sum.map length $ words y) + (length $ words y) - 1,
" words = ", show.length $ words y,
" lines = ", show.length $ lines y, "\n"]).zip fnames
|

Python vs Ruby vs Haskell（文字列検索deベンチマーク）

ファイル名と検索したい文字列を与えると、そのファイルの中で検索文字列がヒットした位置のリスト（又は配列）を表示するプログラムを、Haskell、Python、Rubyで作り、ベンチマークを取ってみました。
こちらMicrosoft OneDrive - Access files anywhere. Create docs with free Office Online.に置いてあるpi.datの中に、7777777(7が7つ）がどの位置に有るのかを検索して、その速度を比較します。

まずは、各言語のコードを見ていきましょう。

Haskell

>|haskell|
import System.Environment
import qualified Data.ByteString.Char8 as B

search _ _ ns | B.null ns = []
search (y,x) s ns | B.take (B.length s) ns == s = (y,x):search (y,x + 1) s (B.tail ns)
search (y,_) s ns | B.head ns == '\n' = search (y + 1,1) s (B.tail ns)
search (y,x) s ns = search (y,x + 1) s (B.tail ns)

main = getArgs >>= \args ->
B.readFile (args!!0) >>=
return.search (1,1) (B.pack (args!!1)) >>= \pos ->
putStrLn (args!!0) >>
print pos
|

Ruby版も完成

Python版完成 - しんちゃんの日記に続き、Ruby版も完成しました。
これからベンチマーク取っていきます。
せっかく、pi.datがあるので、膨大な円周率の数列の中から、7777777(７が７つ！）がいくつ有るか検索する。と言うので、ベンチマーク取りたいと思います。
pi.datはこちらMicrosoft OneDrive - Access files anywhere. Create docs with free Office Online.に置いてありますので、興味が有ったら、ご自身の環境にてベンチマークを取ったり、他の言語でベンチマークに挑戦してみて下さい。

そんな訳でRuby版

def search(s,str)
	list = []
	x = 0
	y = 1
	str.each_char.each_with_index do |ch, i|
		x += 1
		if s == str[i..(i + s.length - 1)]
			list.push [y,x]
		elsif "\n" == ch
			y += 1
			x = 0
		end
	end
	return list
end

content = open(ARGV[0]).read
puts ARGV[0]
print search(ARGV[1],content)

こちらも、もっと簡単に書ける！と言うをお待ちしてます。

Python版完成

ファイル中の文字列を検索して、ヒットした位置のリストを表示するコマンド - しんちゃんの日記のPython版、何とか完成。

Haskell版に比べると、大分複雑です。
もっと簡単に書けるぞ!!と言う人募集中。

import sys

def search(s,str):
	list = []
	x = 0
	y = 1
	for i,ch in enumerate(str):
		x += 1
		if s == str[i:i + len(s)]:
			list.append((y,x))
		elif '\n' == ch:
			y += 1
			x = 0
	return list

args = sys.argv[1:]
content = open(args[0]).read()
print(args[0])
print(search(args[1],content))

今日中にRuby版書くぞ！！(Python版を元に）

ファイル中の文字列を検索して、ヒットした位置のリストを表示するコマンド

取り敢えず、Haskell版は完成しました。
初めての検索関数でしたが、何とか作れました。
アルゴリズムに詳しくないので、力押し検索です。
一応、本には力押し検索は意外と有効なアルゴリズムと書いてありましたし、難しく考えなくても有効な手法と言うのは、良いですね。

Haskellでは、リストを返り値にする再帰の場合、スタックを消費しないので、こういう処理は再帰の単純さがフルに活かせて良い感じです。

import System.Environment

search _ _ [] = []
search (y,x) s (n:ns) | (take (length s) (n:ns)) == s = (y,x):search (y,x + 1) s ns
search (y,x) s (n:ns) | n == '\n' = search (y + 1,1) s ns
search (y,x) s (_:ns) = search (y,x + 1) s ns

main = getArgs >>= \com ->
		readFile (com!!0) >>=
		return.search (1,1) (com!!1) >>= \tlst ->
		putStrLn (com!!0) >>
		print tlst
		

使用例はこんな感じです。

>search search.hs search
search.hs
[(3,1),(4,1),(4,63),(5,1),(5,37),(6,1),(6,25),(10,10)]

所で、すでに他の言語で作る気力が無いです・・・
（と言うか、他の言語では作れる自信がちょっと無いです・・・）

来週は日曜日も忙しいですし・・・
26，27日ぐらいにはPython/Rubyで書く時間も作れそうですが、あまり期待はしないで下さい。

関数型言語のパターンマッチはifやswitch/case文の代わりではあるが、仕組み的にはオーバーロードに近い気がする

変な事を書いてすみません。

タイトルからして訳が分からないと思うのですが、私が最近思っている、パターンマッチに関する考察です。

単純に、よくパターンマッチはifやswitch/case文を書かなくて済む。と言う話があるのですが、使っていくうちに、パターンマッチは単純なifやswitch/case文の置き換えでは無いと思う時があるのです。

例えば、mergesortを自作すると、以下のようになるのですが、ifやswitch/caseで同じように再帰で書こうとすると、結構ごちゃごちゃすると思います。
（まあ、その辺はオブジェクト指向的な別のやり方があると思いますが）

mergesort [] = []
mergesort [z] = [z]
mergesort zs = merge (mergesort xs) (mergesort ys)
	where
		(xs,ys) = mysplitAt (mylength zs `div` 2) zs


merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys)
merge (x:xs) (y:ys) = y:merge (x:xs) ys

mytake 0 _ = []
mytake _ [] = []
mytake n (x:xs) = x:mytake (n - 1) xs

mydrop 0 xs = xs
mydrop _ [] = []
mydrop n (_:xs) = mydrop (n - 1) xs

mysplitAt n xs = (mytake n xs, mydrop n xs)

mylength = mylength' 0
	where
		mylength' v [] = v
		mylength' v (_:xs) = mylength' (v + 1) xs

オブジェクト指向のオーバーロードと全く使い道が違うのは承知なのですが、こう、同じ関数名がズラズラ並ぶと、オーバーロードを引数の数だけじゃなく、値でも同名の違う関数（メソッド）を呼べるようにしたのがパターンマッチなんじゃないか？と、思ってしまう時があります。

まあ、パターンマッチは、あくまで「同じ型の違う値」で機能するので（そして、引数の数は同じじゃないといけないので）、本当に、概念的には全く違うんですけど・・・

仕組み的には、ifやswitch/case文よりも、近いものを何故かオーバーロードに感じてしまう私です。

そう言えば、LLだと型が無いからなのか、オーバーロード使った事ないですね・・・。
そもそも、コンパイラばかり使ってたので、LLの経験自体が少ないですが。

はてなブログに移行する意味は？

最近、管理画面にはてなブログが正式なサービスとしてスタートした的なメッセージが表示されてるのですが、見た所、TwitterやFacebookとの連携と、画面のレイアウトの自由度以外に利点らしきものが感じられないのですが、TwitterやFacebookでつぶやかれたりしても、そこで書かれたコードの把握が大変そうで、どうなんだろう?と言う不安もあります。

しかし、話題になりたい気持ちも無きにしも非ず。

でもなぁ・・・

自分みたいなへっぽこな、しかも趣味グラマーのブログが話題になるのはあんまり良いとは思わないんですよね・・・

むしろ、今までが異常だったというか・・・
プロフィールにも書いた通り、技術も才能も無いんですよ。
飽きられて当然。
Haskellもマスターして無いのに、Haskellが気に入って、布教したい情熱だけで動いてるだけなんです。
他に、比較ブログを積極的に書いてる人が居れば、私はこんな事して無いんです。

それはともかく・・・

はてなブログに移行した方の、移行前と移行後の使い心地とか、聞いてみたいです。
単純に、使い心地が良いなら、移行してみたいです。