HaskellのnubとRubyのuniq
HaskellのData.List#nub
と、
RubyのArray#uniq
は、どちらもリスト/配列内の重複要素を取り除いた新しい配列を返す関数です。
どうもHaskellのnub
はRubyに比べてだいぶ遅いなあと感じます。
リストと配列のデータ構造の違いに起因するのだろうと想像はできますが、いまいち腑に落ちない*1のでまずは計測を行いました。
まずは、重複の全くない長いリスト/配列についてです。 具体的には、1から100,000までの数値を突っ込んだリスト/配列の重複を取り除きます。
nub.hs
module Main where import Data.List main = print $ length $ nub $ [1..100000]
uniq.rb
puts (1..100000).to_a.uniq.length
計測結果
$ time ./nub 100000 real 0m59.538s user 0m59.229s sys 0m0.121s $ time ruby uniq.rb 100000 real 0m0.097s user 0m0.068s sys 0m0.027s
Rubyのほうが600倍以上速いですね。
では、要素数は変えずに、重複の多いリスト/配列について確認します。 具体的には、1から1000までの数値を100回繰り返したリスト/配列の重複を取り除きます。
nub2.hs
module Main where import Data.List main = print $ length $ nub $ concat $ replicate 100 [1..1000]
uniq2.rb
puts (1..1000).to_a.*(100).uniq.length
計測結果
$ time ./nub2 1000 real 0m0.593s user 0m0.589s sys 0m0.003s $ time ./uniq2.rb 1000 real 0m0.062s user 0m0.037s sys 0m0.025s
だいぶ差が縮まりましたが、Rubyのほうが10倍近く速いです。
Rubyは対して変わっていませんが、Haskellについては、ちょうど100倍くらい速くなっています。
ここらへんで、実装を見てみることにします。
まずはHaskell
Haskell (Data.List.hs)
-- | /O(n^2)/. The 'nub' function removes duplicate elements from a list. -- In particular, it keeps only the first occurrence of each element. -- (The name 'nub' means \`essence\'.) -- It is a special case of 'nubBy', which allows the programmer to supply -- their own equality test. nub :: (Eq a) => [a] -> [a] #ifdef USE_REPORT_PRELUDE nub = nubBy (==) #else -- stolen from HBC nub l = nub' l [] -- ' where nub' [] _ = [] -- ' nub' (x:xs) ls -- ' | x `elem` ls = nub' xs ls -- ' | otherwise = x : nub' xs (x:ls) -- ' #endif
計算するまでもなく、O(n^2)
って書いていますね。ひい。
これはHaskellが悪いわけではなく、Ord
のインスタンスでない型に対しても使えることから来ています。
逆に言えば、(Ord a) => [a] -> [a]
であればオーダーの少ないアルゴリズムを使用できます。
Ord
のインスタンスの場合、O(n * log n)
となるnubOrd
をがこちらで提示されています。
unique elements in a haskell list - Stack Overflow
import qualified Data.Set as Set nubOrd :: Ord e => [a] -> [a] nubOrd xs = go Set.empty xs where go s (x:xs) | x `Set.member` s = go s xs | otherwise = x : go (Set.insert x s) xs go _ _ = []
ちなみにこれを使うと、Rubyとほぼ同じ速度になります。
-- main = print $ length $ nubOrd $ [1..100000] $ time ./nub3 100000 real 0m0.082s user 0m0.076s sys 0m0.005s
Ruby (array.c)
static VALUE rb_ary_uniq(VALUE ary) { VALUE hash, uniq; if (RARRAY_LEN(ary) <= 1) return rb_ary_dup(ary); if (rb_block_given_p()) { hash = ary_make_hash_by(ary); uniq = rb_hash_values(hash); } else { hash = ary_make_hash(ary); uniq = rb_hash_values(hash); } RBASIC_SET_CLASS(uniq, rb_obj_class(ary)); ary_recycle_hash(hash); return uniq; }
Rubyは、というと、Hashをうまく使っています。
重要なのはここですね。
hash = ary_make_hash(ary); uniq = rb_hash_values(hash);
ary_make_hash(ary)
は、配列をハッシュにします。Rubyで書くとこんなかんじ。
p [1,2,3].inject({}){ |h,elt| h[elt] = elt;h; } #=> {1=>1, 2=>2, 3=>3} p ['a','a','a','b','b','c'].inject({}){ |h,elt| h[elt] = elt;h; } #=> {"a"=>"a", "b"=>"b", "c"=>"c"}
ハッシュは同一のキーを持たないので、この時点で重複がなくなるんですね。うまいもんだ。
あとは、rb_hash_values(hash)
でvalueのみを取り出してオシマイ。
ハッシュのキー探索は速い(ほぼO(1)
)ので、高速に動くわけですね。
そこで「Haskellでもハッシュ使って実装してみよう」と思ったんですが、Data.HashTable
はIOモナドってたのでやめました。
*1:連結リストであれ、配列であれ、重複しているかのチェックは配列を走査する必要があり、シーケンシャルアクセスでもランダムアクセスでも大きな差が出るとは思えない。。という素人考えのせい