代码之家  ›  专栏  ›  技术社区  ›  matt

Haskell:使用幺半群和可折叠排序

  •  2
  • matt  · 技术社区  · 6 年前

    我正在尝试使用 Monoid Foldable .这就是我目前所拥有的。真的很慢。但是,当我编写相同的函数时 幺半群 可折叠的 ,速度相当快。任何关于我在这里做错了什么的指点都将不胜感激。

    newtype MergeL a = MergeL { getMergeL :: [a] } deriving (Eq, Show)
    
    instance Ord a => Monoid (MergeL a) where
      mempty      = MergeL []
      mappend l r = MergeL $ merge (getMergeL l) (getMergeL r)
    
    
    
    comp :: a -> MergeL a
    comp a = MergeL [a]
    
    instance Foldable MergeL where
      foldMap f xs =
        case divide xs of
          (MergeL [], MergeL []) -> mempty
          (MergeL l , MergeL []) -> foldMap f l
          (MergeL [], MergeL r)  -> foldMap f r
          (MergeL l , MergeL r)  -> foldMap f l <> foldMap f r
    
    divide :: MergeL a -> (MergeL a, MergeL a)
    -- now uses leftHalf and rightHalf
    divide xs = (MergeL $ leftHalf ls, MergeL $ rightHalf ls)
      where
        ls  = getMergeL  xs
    
    foldSort :: (Ord a, Foldable t) => t a -> [a]
    foldSort = getMergeL . foldMap comp
    
    
    mon :: Integer -> IO ()
    mon n = (print . last . getMergeL  . foldMap comp) $ MergeL [n,n - 1 ..0]
    

    共享助手功能:

    leftHalf :: [a] -> [a]
    leftHalf xs = take (length xs `div` 2) xs
    
    rightHalf :: [a] -> [a]
    rightHalf xs = drop (length xs `div` 2) xs
    
    merge :: Ord a => [a] -> [a] -> [a]
    merge xs [] = xs
    merge [] ys = ys
    merge (x:xs) (y:ys)
            | (x <= y)  = x:(merge xs (y:ys))
            | otherwise = y:(merge (x:xs) ys)
    

    下面是排序函数的实现 幺半群 .它使用相同的 leftHalf rightHalf 用于拆分列表和相同的 merge 要合并列表,请执行以下操作:

    mergesort :: Ord a => [a] -> [a]
    mergesort [] = []
    mergesort [x] = [x]
    mergesort xs = merge (mergesort (leftHalf xs)) (mergesort (rightHalf xs))
    
    plain :: Integer -> IO ()
    plain n = (print . last . mergesort)  [n,n - 1 ..0]
    

    性能上的差异是:

     λ> mon 4000
    4000
    (2.20 secs, 1,328,105,368 bytes)
     λ> plain 4000
    4000
    (0.03 secs, 11,130,816 bytes)
    
    1 回复  |  直到 6 年前
        1
  •  2
  •   duplode    6 年前

    这里的主要问题很容易忽略(事实上,我忽略了它,直到我投了一个 trace 在里面 divide ).您的 foldMap 案例为:

    (MergeL l , MergeL r)  -> foldMap f l <> foldMap f r
    

    那里 折叠贴图 正在调用 l r ,这是普通列表,与 MergeL -已包装的列表。既然如此, L R 不是 D相反,它们是逐元素合并的。因此,排序变为二次排序。

    除了使用 MergeL公司 折叠贴图 递归地,修复实例还需要为单个元素列表添加额外的案例,因为划分它们与划分空列表一样有问题:

    instance Foldable MergeL where
      foldMap f xs =
        case divide xs of
          (MergeL [], MergeL []) -> mempty
          (ml, MergeL [y]) -> foldMap f ml <> f y
          (MergeL [x], mr) -> f x <> foldMap f mr
          (ml, MergeL []) -> foldMap f ml
          (MergeL [], mr) -> foldMap f mr
          (ml, mr) -> foldMap f ml <> foldMap f mr
    

    这提供了可接受的性能——与没有优化的普通实现相比,具有相同的复杂性和数量级的计时,并且在优化的情况下,具有大致相同的性能。