Проблемы производительности Haskell Data.Memocombinators?

Question

_

Привет, там,

Часть my program to compute differences between files использует стандартный алгоритм DP для вычисления наибольшего общего несмежный подпоследовательности между двумя списками. Я бегу в проблемы производительности с некоторыми из этих функций, поэтому я побежал ГПЦ в профиль, и нашел следующий результат:

           individual  inherited 
COST CENTRE      no. entries %time %alloc %time %alloc 
(ommitted lines above) 
longestCommonSubsequence    1   0.0 0.0 99.9 100.0 
longestCommonSubsequence'   8855742 94.5 98.4 99.9 100.0 
    longestCommonSubsequence''   8855742 4.2 0.8  5.4 1.6 
    longestCommonSubsequence''.caseY 3707851 0.6 0.6  0.6 0.6 
    longestCommonSubsequence''.caseX 3707851 0.6 0.2  0.6 0.2 
(ommitted lines below) 

Вот код обижая:

longestCommonSubsequence' :: forall a. (Eq a) => [a] -> [a] -> Int -> Int -> [a] 
longestCommonSubsequence' xs ys i j = 
     (Memo.memo2 Memo.integral Memo.integral (longestCommonSubsequence'' xs ys)) i j 

longestCommonSubsequence'' :: forall a. (Eq a) => [a] -> [a] -> Int -> Int -> [a] 
longestCommonSubsequence'' [] _ _ _ = [] 
longestCommonSubsequence'' _ [] _ _ = [] 
longestCommonSubsequence'' (x:xs) (y:ys) i j = 
    if x == y 
     then x : (longestCommonSubsequence' xs ys (i + 1) (j + 1)) -- WLOG 
     else if (length caseX) > (length caseY) 
      then caseX 
      else caseY 
    where 
     caseX :: [a] 
     caseX = longestCommonSubsequence' xs (y:ys) (i + 1) j 

     caseY :: [a] 
     caseY = longestCommonSubsequence' (x:xs) ys i (j + 1) 

Я нахожу примечателен что все время и использование памяти происходит в longestCommonSubsequence', memoising wrapper. Следовательно, я бы пришел к выводу, что поражение производительности происходит от всех поисков и сборок, сделанных Data.Memocombinators, несмотря на то, что он всегда выполняется превосходно во многих других случаях, когда я его использовал.

Я думаю, мой вопрос ... этот вывод кажется разумным; это? Если да, то есть ли у кого-нибудь рекомендации по другим способам достижения ДП?

Для справки, это занимает 12 секунд - что абсурдно долго - для сравнения два 14-линейные длинных файлов с соответствующими содержимым "a\nb\nc\n...m" и "*a\nb\nc\n...m*" (тем же содержанием, но с '*' предварительно затрачиваемые и пост-затрачиваемый).

Заранее благодарен! :)

EDIT: попробуйте ghc-core вещи сейчас; опубликует обновление, если я смогу заставить его хорошо играть с проектом Cabal и получить любую полезную информацию!

Answer 1

Когда вы вызываете Memo.memo2 Memo.integral Memo.integral (longestCommonSubsequence'' xs ys), он создает memoizer для функции longestCommonSubsequence'' xs ys. Это означает, что есть один memoizer для каждого разного значения xs и ys. Я предполагаю, что большая часть времени выполнения тратится на создание всех этих структур данных для всех этих memoizers.

Вы имели в виду memoize на 4 аргументах longestCommonSubsequence''?