Hatena::ブログ(Diary)

しんちゃんの日記

2013-02-09

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

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

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

これは、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
||<

import System.Environment
import qualified Data.ByteString.Char8 as B

countString :: B.ByteString -> (Int, Int, Int)
countString str = (cs, ws, ls)
 where
  ww = B.words str
  ws = length ww
  cs = ws - 1 + (sum $ map B.length ww)
  ls = length $ B.lines str

main :: IO ()
main = do
 fileNames <- getArgs
 mapM_ dispCount fileNames
  where
   dispCount fn = do
    str <- B.readFile fn
    let (cs, ws, ls) = countString str
    mapM_ putStr [fn, "\n",
           "chars = " , show cs,
           " words = ", show ws,
           " lines = ", show ls, "\n\n"]

Python

import sys
from functools import reduce

for arg in sys.argv[1:]:
	print(str(arg))
	content = open(arg).read()
	words = content.split()
	chars = reduce(lambda x,y: x + len(y),words,0) + len(words) - 1
	lines = content.split("\n")
	print("chars =",str(chars)," words =",str(len(words))," lines =",str(len(lines)))
	print()


Ruby

ARGV.each do |arg|
	puts arg
	content = open(arg).read
	words = content.split()
	chars = words.inject(0) { |m, word| m + word.size } + words.size - 1
	lines = content.split("\n")
	print "chars = ", chars , " words = ", words.size ," lines = ", lines.size
	puts "\n" * 2
end


次に、ベンチマーク結果

Haskell

>difftime count pi.dat
pi.dat
chars = 36909881 words = 3355445 lines = 704645



1.1280142s


Python

>difftime python count.py pi.dat
pi.dat
chars = 36909881 words = 3355445 lines = 704646



2.1459239s


Ruby

>difftime ruby count.rb pi.dat
pi.dat
chars = 36909881 words = 3355445 lines = 704645



1.7365545s


所で、Haskellはメモ化すると一度計算されたものは2度目からは計算結果を使いまわすはずなのですが、私の認識では、手続き型言語が計算結果を変数に保存して使いまわすのと同じ事の様に思ってて、上記のHaskellコードを下記の様に書き換えたら速くなるのでは?と思ったのですが、かえって遅くなってしまいました。…何故?

メモ化(勘違いしてるかも)したHaskellのコード

import System.Environment

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

一応、ベンチマーク結果も

>difftime count2 pi.dat
pi.dat
chars = 36909881 words = 3355445 lines = 704645



10.0560143s

自分が何か、根本的な勘違いしてるんだろうとは思うんだけど、メモ化(と、自分が勝手に思ってる事)したら、10秒切れない子になっちゃった…。



2013年2月15日追記

ツムジさんのHaskellコードを反映させた結果、Haskellが1位に返り咲きました。
一々length関数でカウントしてるのは変わらないはずなのに、データ構造が変わるだけで随分と変わる物なのですね・・・

もっと大きいテキストファイルがあれば、いつかは抜かれる日も来るんでしょうけど、ここまで大きいテキストファイルはそうは無いです。
(悔し紛れと言われても良いですが、普通のString使ったHaskellでも、常識的なサイズではLLより速いんですよ?)

上記のHaskellコードが長い!と言う方は、ツムジさんが私のコードをByteStringに書き直したものを、さらにメモ化すると、辛うじて前回1位だったRubyの速度を上回ります。

こんなコードです。
(でも、ツムジさんのコードの方が速度もコードの読みやすさも上であることは了承下さい)

import System.Environment
import qualified Data.ByteString.Char8 as B

main = getArgs >>= \fnames ->
	mapM B.readFile fnames >>=
	mapM_ (\(x,y) -> let (cs,ws,ls) = ((sum.map B.length $ ww) + (length $ ww) - 1,
									length $ ww,
									length $ B.lines y) 
					where
						ww = B.words y in
		putStrLn $ concat [x,
					"\nchars = ", show cs,
					" words = ", show ws,
					" lines = ", show ls, "\n"]).zip fnames

ベンチマーク結果

>difftime count pi.dat
pi.dat
chars = 36909881 words = 3355445 lines = 704645



1.442263s

2013-01-26

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

ファイル名と検索したい文字列を与えると、そのファイルの中で検索文字列がヒットした位置のリスト(又は配列)を表示するプログラムを、HaskellPythonRubyで作り、ベンチマークを取ってみました。
こちら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
||<

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


Python
>|python|
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*1
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))
||<

import sys

def search(q,filename):
	for i,line in enumerate(open(filename)):
		found = line.find(q)
		while found != -1 :
			yield i+1,found+1
			found = line.find(q,found+1)

print(sys.argv[1])
print(list(search(sys.argv[2],sys.argv[1])))

Ruby
>|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)
||<

def search(s,f)
	list = []
	File.foreach(f).with_index(1) do |line, i|
		if n = line.index(s)
			list.push [i, n+1]
			list.push [i, n+1] while n = line.index(s, n+1)
		end
	end
	list
end

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

そして、各々の実行結果は、以下の通りです。

Haskell

>difftime search pi.dat 7777777
pi.dat
[(298906,35),(517833,1),(517833,2),(517833,3)]


1.5313435s

Python

>difftime python search.py pi.dat 7777777
pi.dat
[(298906, 35), (517833, 1), (517833, 2), (517833, 3)]


1.116003s

Ruby

>>difftime ruby search.rb pi.dat 7777777
pi.dat
298906, 35], [517833, 1], [517833, 2], [517833, 3?

1.1019912s

今回、Rubyだけタプルが無いので、配列で代用してます。

前回のHaskell vs Python vs Ruby(ファイルの中身の文字数、ワード数、行数を表示するコマンド) - しんちゃんの日記と違って、Haskellが断トツで速いですね!
と言うのも前回のベンチマークでは、Haskellのlength関数は、まさにリストを数える訳ですが、PythonRubyのlen関数、lengthメソッドは、どうもオブジェクトに格納されている文字数を保持している変数(フィールド)にアクセスして読んでるだけっぽいんですよ。
それでも、Linuxカーネルのソースファイル一つくらいなら、文字数・ワード数・行数を数える分にはHaskellの方が速かったりします。
一定のファイルサイズ以上になると、Haskellが要素を数えるより、LLのフィールド参照の方が速くなるようです。

それとは打って変わって、今回は検索文字列sと比較するために文字列全体から検索文字列の長さ分だけ、部分文字列を作り、比較する所で、上手く遅延評価が生きてます。
Python/Rubyは文字列全体を読み込んでから、部分文字列を作るために遅い)
多少コードが長くなることを覚悟で、行毎に処理をすれば、Python/Rubyはもっと高速化出来そうです。
(下手するとHaskell追い越せるかも?)

まあ、すでにHaskellに比べて大分面倒臭い思いをしたので、もうこれ以上の改良する気は無いですが(おい)

さて、前回の言い訳(負け惜しみ?)はこれくらいにして、現在の順位を示します。

1位 Haskell
2位 Python
3位 Ruby

HaskellPythonでは10倍近い差があり、PythonRubyでは2倍程度の差があります。
HaskellRubyでは、実に14倍の差です。

例によって、どの言語も私ごときが書くより、もっと上級者が書いた方が速くなる余地が有りますので、こう書くと速くなるよ!とか、こう書いた方が短く書けるよ!とか有りましたら、コメント欄にてお願いしますm(_ _)m

2013年1月27日更新

keyesberryさんのコードを反映した結果、Rubyが一位に躍り出ました。

現在の順位

1位 Ruby
2位 Haskell
3位 Python

Fileオブジェクトそのものはもちろん、そのメソッドも私は把握できておりませぬ・・・。


2013年1月28日更新

通りすがりさんのコードを反映した結果、2位がHaskellからPythonに変わりました。

現在の順位

1位 Ruby
2位 Python
3位 Haskell

通りすがりさんの環境ではPythonが一位だそうで・・・
OSによって、ランタイム最適化度合いが違うのかもしれません。

RubyWin環境では不便と聞いてたけど、ライブラリが揃ってないとか、不安定とか、そう言う事なのでしょうか?

ちなみに、私の環境(Win8 64bit Core i5 2.4GHz 6GB)では、(Win7 64bitの頃から)irbがすぐにフリーズするので、rubyコマンドしか使ってませんので、少なくとも、安定度ではPythonの方が安心感が有ったりします。

実用的な速度の出るコードの中ではHaskellが一番単純だい!とか、強がってみる。

遅延評価のお蔭で、メモリ読み込みがボトルネックにはなってないはずですし、Haskellもlines関数で行単位に分割してから処理・・・しても、速度的に変わるとは思えませんしね・・・
(むしろ遅くなる予感すらします)



2013年2月20日追記

ツムジさん、tanakhさんの協力を得て、高速化したHaskellコードに差し替えた結果…を反映して、一から現在の環境でベンチマーク取り直してみました。
・・・が、肉薄はするものの順位は変わらず…orz

Ruby版も完成

Python版完成 - しんちゃんの日記に続き、Ruby版も完成しました。
これからベンチマーク取っていきます。
せっかく、pi.datがあるので、膨大な円周率の数列の中から、7777777(7が7つ!)がいくつ有るか検索する。と言うので、ベンチマーク取りたいと思います。
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)

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

*1:y,x

2013-01-03

Haskell vs Python vs Ruby(ファイルの中身の文字数、ワード数、行数を表示するコマンド)

ファイルの中身の文字数、ワード数、行数を表示するコマンド(他の言語の投稿求む) - しんちゃんの日記のコードをPython/Rubyでも作り、ベンチマーク取りました。
読み込ませたファイルは、スーパーπで生成できる一番大きなπ。3355万桁を収めたpi.datがテキストデータだったので、それを今回は食わせてみました。

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

Haskell

import System.Environment

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

Python

import sys
 
for arg in sys.argv[1:]:
	print(str(arg))
	content = open(arg).read()
	words = content.split()
	chars = ""
	for word in words:
		chars = chars + word + " "
	lines = content.split('\n')
	print("chars = ",str(len(chars)-1)," words = ",str(len(words))," lines = ",str(len(lines)))
	print()

Ruby
>|ruby|
ARGV.each do |arg|
puts arg
content = open(arg).read
words = content.split()
chars = ""
words.each {|word| chars = chars + word + " " }
lines = content.split("\n")
print "chars = ", chars.length - 1 , " words = ", words.size ," length = ", lines.size
puts "\n" * 2
end
||<


ARGV.each do |arg|
	puts arg
	content = open(arg).read
	words = content.split()

	chars = words.inject(0) { |m, word| m + word.size } + words.size - 1
	lines = content.split("\n")
	print "chars = ", chars , " words = ", words.size ," length = ", lines.size
	puts "\n" * 2
end

Haskell
C:\Users\nShinchan\Documents\MyHaskell>difftime count pi.dat
pi.dat
chars = 36909881 words = 3355445 lines = 704645



9.1462863s

Python
C:\Users\nShinchan\Documents\MyHaskell>difftime python count.py pi.dat
pi.dat
chars = 36909881 words = 3355445 lines = 704646



106.4871007s


Ruby
C:\Users\nShinchan\Documents\MyHaskell>difftime ruby count2.rb pi.dat
pi.dat
chars = 36909881 words = 3355445 length = 704645



1.7565871s

Rubvは-Ksオプション付けても終わらないので、何かフリーズしてる気がします・・・。

終了したHaskellPythonでも、想像してたのと違い、結構な差が生まれました。
まあ、例によってPythonは詳しい人によって高速化しそうな気もします。
Rubyも、せめてちゃんと終了するコードが見たいので、詳しい人が居ると助かるんですが・・・。
(プログラムコードを食わす分には、ちゃんと終了するんですけどね…>Ruby

ベンチマーク用のデータとしてpi.datが適切ではなかった?
でも、どのコードも日本語を考慮してないので、英語で長い文章が理想なんですが、私は持ち合わせがない・・・。



2013年1月5日追記

pi.datが入ったskydriveのフォルダを公開します。
Microsoft OneDrive - Access files anywhere. Create docs with free Office Online.

そして、keyesberryさんから頂いたコードに差し替えました。
ちゃんとpi.datを読み込ませても動きます!そして、一気にRubyが一位です!
Haskellが負けたのは悔しいですが、まずはRubyでpi.datが読み込めたことで胸のつかえが取れました。

2013-01-02

ruby版完成

ほとんど何とかPython版完成 - しんちゃんの日記pythonのコードそのまんま。

ARGV.each do |arg|
	puts arg
	content = open(arg).read
	words = content.split()
	chars = ""
	words.each do |word|
		chars += word
		chars += " "
	end
	lines = content.split("\n")
	print "chars = ", chars.length - 1 , " words = ", words.size ," length = ", lines.size
	puts "\n" * 2
end

rubyのsplitは""で囲まないとまともに機能しないのね・・・
pythonでは文字だけど、rubyじゃ文字列なのね・・・
さあ、明日の昼までには各言語の比較ベンチマーク結果をアップします。

2012-11-24

「ふと、手続き型言語だとちょっと大変かな?と思ったプログラム」のプログラムをPythonとRubyで書いてみた

少し前にふと、手続き型言語だとちょっと大変かな?と思ったプログラム - しんちゃんの日記でファイルの内容を全部逆にしてナンバリングするのは関数型言語では簡単だったのだけど、手続き型言語ではちょっと大変なのでは?と書いたわけですが、本当かどうかPythonで検証してみた。
>|python|

import sys

for arg in sys.argv[1:]:
print(arg)
fin = open(arg, 'r')
a = 1
s = ""
for line in fin:
s += line
s = list(s)
s.reverse()
print('',a,end = '')
for i in s:
if i == '\n':
a += 1
print(i,a,end = '')
else:
print(i,end = '')
print("\n")
fin.close()
||<

import sys

for arg in sys.argv[1:]:
 print(arg)
 content = open(arg).read()[::-1]
 for no,line in enumerate(content.split('\n'),1):
  print(str(no)+line)
 print()

文字列から改行文字で分割して文字列のリストを作る関数なりメソッドなりが有ればもうちょっと簡単になるんだろうけど、私はPythonに詳しくないので知らない!(ドヤッ)
Rubyはもっと知らない!(ドヤドヤァッ)
仮に知ってても、やっぱり関数型言語よりは面倒臭い事には変わりない気がする。
そうは言っても、PythonRubyに詳しい人からすれば「そんな事あるか!関数型言語にだって負けないくらい簡単に書けるわ!!」と言う意見も有るかも知れない。


通りすがりさんから、コードを提供頂いたので、更新しておきました。
コメント欄に、Haskell風のPythonコードもあるので、そちらも見てもらうと、その柔軟さが見て取れます。
Haskellのコードも頂いたのですが、どちらの方が良いのか判断付きかねたので(いや、基本的に通りすがりさんのコードの方が良いと思うのですが)、一応そのままにしておきます。
興味がある方は、これもコメント欄の通りすがりさんのコードを参照願います。

何はともあれ、ここに再度Haskellのコードも掲載しておきます。

import System.Environment

numbering = unlines.(map (\(x,y) -> show x ++ y)).(zip [1..]).lines

main = getArgs >>= \args -> mapM readFile args >>=  return.map (numbering.reverse) >>= 
			(mapM_ (\(x,y) -> putStrLn $ x ++ "\n" ++ y)).zip args


C vs Python vs Ruby vs Haskell(ナンバリングdeベンチマーク) - しんちゃんの日記の普通のナンバリングのコードと比べて、Pythonは大分変っているのに、Haskellは少しの変更で機能を実現しているのにも注目です。

2012年11月24日22:02追記

Rubyでも書いてみました。
>|ruby|
ARGV.each do|fname|
puts fname
i = 0
s = ""
File.open(fname).each{|line|s += line }.close
s.reverse.split("\n").each{|line| print i += 1, line, "\n" }
puts "\n" * 2
end
||<

ARGV.each do |arg|
    puts arg
    content = File.read(arg).reverse
    content.each_line.with_index(1) do |line, no|
        puts no.to_s + line
    end
    puts
end

Pythonでは文字列型にreverseが付いてないのですが、Rubyには付いてますね・・・。
Pythonでは、一旦リスト型に変換して、また文字列型に戻すと同様な処理になりますが、行数では上のコードよりも長くなってしまいます。
それでも、RubyHaskellよりはコードの変更箇所が多いみたいですね。


2012年12月2日追記

TooさんよりRubyのコードを頂きましたので、置き換えました。