定食屋おろポン

おろしポン酢と青ネギはかけ放題です

HaskellのnubとRubyのuniq

HaskellData.List#nubと、 RubyArray#uniqは、どちらもリスト/配列内の重複要素を取り除いた新しい配列を返す関数です。

どうもHaskellnubRubyに比べてだいぶ遅いなあと感じます。 リストと配列のデータ構造の違いに起因するのだろうと想像はできますが、いまいち腑に落ちない*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)

hackage

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

GitHub

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:連結リストであれ、配列であれ、重複しているかのチェックは配列を走査する必要があり、シーケンシャルアクセスでもランダムアクセスでも大きな差が出るとは思えない。。という素人考えのせい