Verarbeitung einer sehr großen Textdatei mit faulen Texten und ByteStrings

Question

Ich versuche eine sehr große Unicode-Textdatei (6GB +) zu verarbeiten. Ich möchte die Häufigkeit jedes einzelnen Wortes zählen. Ich verwende eine strikte Data.Map, um die Zählungen jedes Wortes zu verfolgen, während ich die Datei durchquere. Der Prozess dauert zu viel Zeit und zu viel Speicher (20 GB +). Ich vermute, dass die Map riesig ist, aber ich bin mir nicht sicher, dass sie die 5-fache Größe der Datei erreichen sollte! Der Code ist unten gezeigt. Bitte beachten Sie, dass ich versuchte, die folgenden:

• Mit Data.HashMap.Strict statt Data.Map.Strict. Data.Map scheint im Hinblick auf eine langsamere Erhöhung des Speicherverbrauchs besser zu funktionieren.

• Lesen der Dateien mit Lazy ByteString statt Lazy Text. Und dann kodiere ich es zu Text, mache etwas Verarbeitung und kodiere es dann wieder zurück zu ByteString für IO.

  import Data.Text.Lazy (Text(..), cons, pack, append) 
  import qualified Data.Text.Lazy as T 
  import qualified Data.Text.Lazy.IO as TI 
  import Data.Map.Strict hiding (foldr, map, foldl') 
  import System.Environment 
  import System.IO 
  import Data.Word 
  
  dictionate :: [Text] -> Map Text Word16 
  dictionate = fromListWith (+) . (`zip` [1,1..]) 
  
  main = do 
      [file,out] <- getArgs 
      h <- openFile file ReadMode 
      hO <- openFile out WriteMode 
      mapM_ (flip hSetEncoding utf8) [h,hO] 
      txt <- TI.hGetContents h 
      TI.hPutStr hO . T.unlines . 
       map (uncurry ((. cons '\t' . pack . show) . append)) . 
       toList . dictionate . T.words $ txt 
      hFlush hO 
      mapM_ hClose [h,hO] 
      print "success" 
  

Was mit meinem Ansatz falsch? Was ist der beste Weg, um das zu erreichen, was ich in Bezug auf Zeit und Speicherleistung versuche?

Answer 1

Diese Speicherbelegung wird erwartet. Data.Map.Map verbraucht ca. 6N Wörter des Speichers + Größe der Schlüssel & Werte (Daten aus this excellent post by Johan Tibell entnommen). A faulText Wert takes up 7 words + 2*N bytes (auf das Vielfache der Maschine Wortgröße gerundet), und eine Word16takes up two words (Header + Nutzlast). Wir werden eine 64-Bit-Maschine annehmen, also wird die Wortgröße 8 Bytes betragen. Wir nehmen auch an, dass die durchschnittliche Zeichenfolge in der Eingabe 8 Zeichen lang ist.

Wenn Sie all dies berücksichtigen, lautet die letzte Formel für die Speichernutzung 6*N + 7*N + 2*N + 2*N Wörter.

Im schlimmsten Fall werden alle Wörter unterschiedlich sein und es wird etwa (6 * 1024^3)/8 ~= 800 * 10^6 von ihnen geben. Wenn wir das in die obige Formel einfügen, erhalten wir die Worst-Case-Kartengröße von ca. 102 GiB, was mit den experimentellen Ergebnissen zu übereinstimmen scheint. Das Lösen dieser Gleichung in der umgekehrten Richtung sagt uns, dass Ihre Datei ungefähr 200*10^6 verschiedene Wörter enthält.

Als alternative Ansätze für dieses Problem, verwenden Sie einen Trie (wie von J.Abrahamson in den Kommentaren vorgeschlagen) oder eine ungefähre Methode, z. B. count-min sketch.

Answer 2

In der Welt der traditionellen Datenverarbeitung wäre dieses Problem durch Sortieren (extern auf Platte oder Magtape, falls erforderlich), dann Scannen der sortierten Datei, um die gruppierten Zusammenfassungen von Wörtern zu zählen. Natürlich könnten Sie während der frühen Phasen der Sortierung teilweise reduzieren, um Platz und Zeit zu sparen.