Heap Überlauf in Haskell

Question

Ich bekomme Heap exhausted Nachricht, wenn Sie das folgende kurze Haskell-Programm auf einem ausreichend großen Dataset ausführen. Beispielsweise schlägt das Programm (mit Heap-Überlauf) auf 20 MB-Eingabedatei mit etwa 900 KB-Zeilen fehl. Die Größe des Heapspeichers wurde (über -with-rtsopts) auf 1 GB festgelegt. Es läuft in Ordnung, wenn longestCommonSubstrB als etwas einfacher definiert ist, z.B. commonPrefix. Ich muss Dateien in der Größenordnung von 100 MB verarbeiten.

ich das Programm mit der folgenden Befehlszeile (GHC 7.8.3) zusammengestellt:

ghc -Wall -O2 -prof -fprof-auto "-with-rtsopts=-M512M -p -s -h -i0.1" SampleB.hs 

ich Hilfe bei der Herstellung dieses Dings in einer angemessenen Menge an Speicherplatz (in der Reihenfolge des Eingangs ausgeführt schätzen würde Dateigröße), aber ich würde besonders den Gedankenprozess schätzen zu finden, wo der Engpass ist und wo und wie man die Strenge erzwingt.

Meine Vermutung ist, dass die longestCommonSubstrB Funktion zwingt, streng auszuwerten, würde das Problem lösen, aber ich weiß nicht, wie man das macht.

{-# LANGUAGE BangPatterns #-} 
module Main where 
import System.Environment (getArgs) 
import qualified Data.ByteString.Lazy.Char8 as B 
import Data.List (maximumBy, sort) 
import Data.Function (on) 
import Data.Char (isSpace) 

-- | Returns a list of lexicon items, i.e. [[w1,w2,w3]] 
readLexicon :: FilePath -> IO [[B.ByteString]] 
readLexicon filename = do 
    text <- B.readFile filename 
    return $ map (B.split '\t' . stripR) . B.lines $ text 
    where 
     stripR = B.reverse . B.dropWhile isSpace . B.reverse 

transformOne :: [B.ByteString] -> B.ByteString 
transformOne (w1:w2:w3:[]) = 
    B.intercalate (B.pack "|") [w1, longestCommonSubstrB w2 w1, w3] 
transformOne a = error $ "transformOne: unexpected tuple " ++ show a 

longestCommonSubstrB :: B.ByteString -> B.ByteString -> B.ByteString 
longestCommonSubstrB xs ys = maximumBy (compare `on` B.length) . concat $ 
    [f xs' ys | xs' <- B.tails xs] ++ 
    [f xs ys' | ys' <- tail $ B.tails ys] 
    where f xs' ys' = scanl g B.empty $ B.zip xs' ys' 
     g z (x, y) = if x == y 
       then z `B.snoc` x 
       else B.empty 

main :: IO() 
main = do 
    (input:output:_) <- getArgs 
    lexicon <- readLexicon input 
    let flattened = B.unlines . sort . map transformOne $ lexicon 
    B.writeFile output flattened 

Dies ist das Profil ouput für den Testdatensatz (100K Linien, Speichergröße zu 1 GB gesetzt, dh generateSample.exe 100000, ist die resultierende Dateigröße 2,38 MB):

Heap-Profil über die Zeit:

Execution Statistiken:

3,505,737,588 bytes allocated in the heap 
    785,283,180 bytes copied during GC 
     62,390,372 bytes maximum residency (44 sample(s)) 
     216,592 bytes maximum slop 
       96 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  6697 colls,  0 par 1.05s 1.03s  0.0002s 0.0013s 
    Gen 1  44 colls,  0 par 4.14s 3.99s  0.0906s 0.1935s 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT  time 7.80s ( 9.17s elapsed) 
    GC  time 3.75s ( 3.67s elapsed) 
    RP  time 0.00s ( 0.00s elapsed) 
    PROF time 1.44s ( 1.35s elapsed) 
    EXIT time 0.02s ( 0.00s elapsed) 
    Total time 13.02s (12.85s elapsed) 

    %GC  time  28.8% (28.6% elapsed) 

    Alloc rate 449,633,678 bytes per MUT second 

    Productivity 60.1% of total user, 60.9% of total elapsed 

Profilieren Bericht

Zeit und Allocation:

 SampleB.exe +RTS -M1G -p -s -h -i0.1 -RTS sample.txt sample_out.txt 

    total time =  3.97 secs (3967 ticks @ 1000 us, 1 processor) 
    total alloc = 2,321,595,564 bytes (excludes profiling overheads) 

COST CENTRE   MODULE %time %alloc 

longestCommonSubstrB Main  43.3 33.1 
longestCommonSubstrB.f Main  21.5 43.6 
main.flattened   Main  17.5 5.1 
main     Main  6.6 5.8 
longestCommonSubstrB.g Main  5.0 5.8 
readLexicon   Main  2.5 2.8 
transformOne   Main  1.8 1.7 
readLexicon.stripR  Main  1.8 1.9 


                      individual  inherited 
COST CENTRE     MODULE      no.  entries %time %alloc %time %alloc 

MAIN       MAIN       45   0 0.1 0.0 100.0 100.0 
main      Main       91   0 6.6 5.8 99.9 100.0 
    main.flattened    Main       93   1 17.5 5.1 89.1 89.4 
    transformOne    Main       95  100000 1.8 1.7 71.6 84.3 
    longestCommonSubstrB  Main       100  100000 43.3 33.1 69.8 82.5 
    longestCommonSubstrB.f Main       101  1400000 21.5 43.6 26.5 49.5 
     longestCommonSubstrB.g Main       104  4200000 5.0 5.8  5.0 5.8 
    readLexicon    Main       92   1 2.5 2.8  4.2 4.8 
    readLexicon.stripR  Main       98   0 1.8 1.9  1.8 1.9 
CAF       GHC.IO.Encoding.CodePage  80   0 0.0 0.0  0.0 0.0 
CAF       GHC.IO.Encoding    74   0 0.0 0.0  0.0 0.0 
CAF       GHC.IO.FD      70   0 0.0 0.0  0.0 0.0 
CAF       GHC.IO.Handle.FD    66   0 0.0 0.0  0.0 0.0 
CAF       System.Environment   65   0 0.0 0.0  0.0 0.0 
CAF       Data.ByteString.Lazy.Char8 54   0 0.0 0.0  0.0 0.0 
CAF       Main       52   0 0.0 0.0  0.0 0.0 
    transformOne    Main       99   0 0.0 0.0  0.0 0.0 
    readLexicon    Main       96   0 0.0 0.0  0.0 0.0 
    readLexicon.stripR  Main       97   1 0.0 0.0  0.0 0.0 
    main      Main       90   1 0.0 0.0  0.0 0.0 

UPDATE: Das folgende Programm verwendet werden kann, um Beispieldaten zu generieren. Es erwartet ein Argument, die Anzahl der Zeilen im generierten Dataset. Die generierten Daten werden in der Datei sample.txt gespeichert. Wenn ich ein 900k-Zeilen-Dataset damit erzeuge (durch Ausführen von generateSample.exe 900000), führt das erzeugte Dataset zum Ausfall des obigen Programms mit Heap-Überlauf (die Heap-Größe wurde auf 1 GB gesetzt). Der resultierende Datensatz ist ungefähr 20 MB groß.

module Main where 
import System.Environment (getArgs) 
import Data.List (intercalate, permutations) 

generate :: Int -> [(String,String,String)] 
generate n = take n $ zip3 (f "banana") (f "ruanaba") (f "kikiriki") 
    where 
     f = cycle . permutations 

main :: IO() 
main = do 
    (n:_) <- getArgs 
    let flattened = unlines . map f $ generate (read n :: Int) 
    writeFile "sample.txt" flattened 
    where 
     f (w1,w2,w3) = intercalate "\t" [w1, w2, w3] 

Answer 1

Es scheint mir, Sie haben einen naiven längsten gemeinsamen Teilstring implementiert, mit schrecklichen Raumkomplexität (mindestens O (n^2)). Strenge hat damit nichts zu tun.

Sie möchten eine dynamische Programmierung algo implementieren. Sie können Inspiration in der string-similarity Verpackung finden, oder in der lcs Funktion in den Eingeweiden des Diff Pakets.