2

Haskell でトライ実装を書いたところ、パフォーマンスの問題が発生しました。それに応じてコードをhttp://book.realworldhaskell.org/read/profiling-and-optimization.htmlにプロファイリングし、問題を突き止めることができました。それはinsertWith私の試みの方法です：

import qualified Data.Map.Strict as M
-- i have also tried Data.Map.Lazy

data Trie k a = Trie { value  :: !(Maybe a)
                     , childs :: !(Map.Map k (Trie k a))
                     }

empty :: Trie a k
empty = Trie Nothing Map.empty

insertWith :: Ord k => (a -> a -> a) -> [k] -> a -> Trie k a -> Trie k a
insertWith f [] a t@(Trie Nothing  _) = t { value = Just a }
insertWith f [] a t@(Trie (Just b) _) = t { value = Just $ f a b }
insertWith f (k:ks) a t = t { childs = m }
    where
        recurse = insertWith f ks a
        m = Map.insertWith (\_ child -> recurse child) k (recurse empty) (childs t)

私のプロファイリング コード:

import qualified MyTrie as T
main = do
    let nums = zipWith (\a b -> (show a, b)) [0..100000] [0..]
        trie = foldl' (flip $ uncurry $ T.insertWith (+)) T.empty nums
    putStrLn $ show $ T.lookup "100" trie

プロファイリングの結果:

 CAF:main4                Main                    113           0    0.0    0.0    55.2   38.3
  main                    Main                    126           0    2.6    0.0    55.2   38.3
   main.trie              Main                    127           0   12.6    2.7    52.6   38.3
    childs                Text.NGram.Trie         137     1000001    0.0    0.0     0.0    0.0
    insertWith            Text.NGram.Trie         135     1123337    3.2    6.2    40.1   35.6
     insertWith.recurse   Text.NGram.Trie         140      123336    0.4    0.0     0.4    0.0
     insertWith.m         Text.NGram.Trie         138     1123334   31.4   29.1    36.4   29.4
      insertWith.recurse  Text.NGram.Trie         142           0    0.0    0.0     0.0    0.0
      insertWith.m.\      Text.NGram.Trie         139      123333    1.5    0.0     5.0    0.3
       insertWith.recurse Text.NGram.Trie         141           0    3.5    0.3     3.5    0.3
        childs            Text.NGram.Trie         143      123333    0.0    0.0     0.0    0.0

と

   1,403,625,328 bytes allocated in the heap
   1,699,102,256 bytes copied during GC
     393,716,888 bytes maximum residency (11 sample(s))
       4,565,856 bytes maximum slop
             771 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0      2673 colls,     0 par    0.97s    0.98s     0.0004s    0.0027s
  Gen  1        11 colls,     0 par    1.41s    1.41s     0.1285s    0.6767s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.69s  (  0.70s elapsed)
  GC      time    2.38s  (  2.39s elapsed)
  RP      time    0.00s  (  0.00s elapsed)
  PROF    time    0.00s  (  0.00s elapsed)
  EXIT    time    0.06s  (  0.06s elapsed)
  Total   time    3.14s  (  3.15s elapsed)

  %GC     time      75.8%  (75.9% elapsed)

  Alloc rate    2,021,450,981 bytes per MUT second

  Productivity  24.2% of total user, 24.2% of total elapsed

ghc バージョン: 7.6.2

insertWith メソッドのパフォーマンスを少し向上させる方法を知っている人はいますか?

ありがとう

4

1 に答える 1

3

の

insertWith f [] a t@(Trie Nothing  _) = t { value = Just a }
insertWith f [] a t@(Trie (Just b) _) = t { value = Just $ f a b }

af a b未評価のまま保管されています。試す

insertWith f [] a t@(Trie Nothing  _) = a `seq` t { value = Just a }
insertWith f [] a t@(Trie (Just b) _) = t { value = Just $! f a b }
于 2013-04-23T18:55:16.297 に答える