[Haskell-cafe] Re: Slower with ByteStrings?

[Mirko Rahn]

[fixed some typos, mainly missing primes]

>   superset xs = superset' x . sort
>     where
>     x = sort xs
> 
>     _      `superset'`  []     = True
>     []     `superset'`  _      = False
>     (x:xs) `superset'` (y:ys)
>         | x == y    = xs `superset'` ys
>         | x <  y    = xs `superset'` (y:ys)
>         | otherwise = False

>>del y = del_acc []
>>    where del_acc _ []              = mzero
>>          del_acc v (x:xs) | x == y = return (v++xs)
>>          del_acc v (x:xs)          = del_acc (x:v) xs

> The algorithm is correct but it's not faster, xs `super` ys  takes
> O(n*m) time whereas superset takes O(n * log n + m * log m) time given a
> proper sorting algorithm. Here, n = length xs and m = length ys.

Of course, you are right. In worst case super is much slower than 
superset. In average case (for some assumptions about the inputs) it 
could perform quite well because of the chance to detect non-subset 
words early.

> 2) Put xs into a good data structure and achieve a O(m * log n) time for
> multiple ys.

You mean something along

supermap xs =
     let mx      = Map.fromListWith (+) [ (x,1) | x <- xs ]
         ins _ 1 = Nothing
         ins _ v = Just (v-1)
         upd m y = case Map.updateLookupWithKey ins y m of
                    (Nothing,_ ) -> mzero
                    (_      ,m') -> return m'
     in not . null . foldM upd mx

Thanks for your time,

BR,

-- 
-- Mirko Rahn -- Tel +49-721 608 7504 --
--- http://liinwww.ira.uka.de/~rahn/ ---