Come migliorare le prestazioni di elaborazione del testo in Clojure?

Question

Sto scrivendo un semplice motore di ricerca desktop in Clojure come un modo per imparare di più sulla lingua. Fino ad ora, le prestazioni durante la fase di elaborazione del testo del mio programma sono davvero pessime.

Durante l'elaborazione del testo ho a:

• Clean up caratteri indesiderati;
• Converti la stringa in minuscolo;
• Dividere il documento per ottenere un elenco di parole;
• Costruisci una mappa che associa ogni parola alle sue occorrenze nel documento.

Ecco il codice:

(ns txt-processing.core 
    (:require [clojure.java.io :as cjio]) 
    (:require [clojure.string :as cjstr]) 
    (:gen-class)) 

(defn all-files [path] 
    (let [entries (file-seq (cjio/file path))] 
    (filter (memfn isFile) entries))) 

(def char-val 
    (let [value #(Character/getNumericValue %)] 
    {:a (value \a) :z (value \z) 
    :A (value \A) :Z (value \Z) 
    :0 (value \0) :9 (value \9)})) 

(defn is-ascii-alpha-num [c] 
    (let [n (Character/getNumericValue c)] 
    (or (and (>= n (char-val :a)) (<= n (char-val :z))) 
     (and (>= n (char-val :A)) (<= n (char-val :Z))) 
     (and (>= n (char-val :0)) (<= n (char-val :9)))))) 

(defn is-valid [c] 
    (or (is-ascii-alpha-num c) 
     (Character/isSpaceChar c) 
     (.equals (str \newline) (str c)))) 

(defn lower-and-replace [c] 
    (if (.equals (str \newline) (str c)) \space (Character/toLowerCase c))) 

(defn tokenize [content] 
    (let [filtered (filter is-valid content) 
     lowered (map lower-and-replace filtered)] 
    (cjstr/split (apply str lowered) #"\s+"))) 

(defn process-content [content] 
    (let [words (tokenize content)] 
    (loop [ws words i 0 hmap (hash-map)] 
     (if (empty? ws) 
     hmap 
     (recur (rest ws) (+ i 1) (update-in hmap [(first ws)] #(conj % i))))))) 

(defn -main [& args] 
    (doseq [file (all-files (first args))] 
    (let [content (slurp file) 
      oc-list (process-content content)] 
     (println "File:" (.getPath file) 
       "| Words to be indexed:" (count oc-list))))) 

Come ho another implementation di questo problema in Haskell, ho confrontato sia come si può vedere nelle seguenti uscite.

versione Clojure:

$ lein uberjar 
Compiling txt-processing.core 
Created /home/luisgabriel/projects/txt-processing/clojure/target/txt-processing-0.1.0-SNAPSHOT.jar 
Including txt-processing-0.1.0-SNAPSHOT.jar 
Including clojure-1.5.1.jar 
Created /home/luisgabriel/projects/txt-processing/clojure/target/txt-processing-0.1.0-SNAPSHOT-standalone.jar 
$ time java -jar target/txt-processing-0.1.0-SNAPSHOT-standalone.jar ../data 
File: ../data/The.Rat.Racket.by.David.Henry.Keller.txt | Words to be indexed: 2033 
File: ../data/Beyond.Pandora.by.Robert.J.Martin.txt | Words to be indexed: 1028 
File: ../data/Bat.Wing.by.Sax.Rohmer.txt | Words to be indexed: 7562 
File: ../data/Operation.Outer.Space.by.Murray.Leinster.txt | Words to be indexed: 7754 
File: ../data/The.Reign.of.Mary.Tudor.by.James.Anthony.Froude.txt | Words to be indexed: 15418 
File: ../data/.directory | Words to be indexed: 3 
File: ../data/Home.Life.in.Colonial.Days.by.Alice.Morse.Earle.txt | Words to be indexed: 12191 
File: ../data/The.Dark.Door.by.Alan.Edward.Nourse.txt | Words to be indexed: 2378 
File: ../data/Storm.Over.Warlock.by.Andre.Norton.txt | Words to be indexed: 7451 
File: ../data/A.Brief.History.of.the.United.States.by.John.Bach.McMaster.txt | Words to be indexed: 11049 
File: ../data/The.Jesuits.in.North.America.in.the.Seventeenth.Century.by.Francis.Parkman.txt | Words to be indexed: 14721 
File: ../data/Queen.Victoria.by.Lytton.Strachey.txt | Words to be indexed: 10494 
File: ../data/Crime.and.Punishment.by.Fyodor.Dostoyevsky.txt | Words to be indexed: 10642 

real 2m2.164s 
user 2m3.868s 
sys  0m0.978s 

versione Haskell:

$ ghc -rtsopts --make txt-processing.hs 
[1 of 1] Compiling Main    (txt-processing.hs, txt-processing.o) 
Linking txt-processing ... 
$ time ./txt-processing ../data/ +RTS -K12m 
File: ../data/The.Rat.Racket.by.David.Henry.Keller.txt | Words to be indexed: 2033 
File: ../data/Beyond.Pandora.by.Robert.J.Martin.txt | Words to be indexed: 1028 
File: ../data/Bat.Wing.by.Sax.Rohmer.txt | Words to be indexed: 7562 
File: ../data/Operation.Outer.Space.by.Murray.Leinster.txt | Words to be indexed: 7754 
File: ../data/The.Reign.of.Mary.Tudor.by.James.Anthony.Froude.txt | Words to be indexed: 15418 
File: ../data/.directory | Words to be indexed: 3 
File: ../data/Home.Life.in.Colonial.Days.by.Alice.Morse.Earle.txt | Words to be indexed: 12191 
File: ../data/The.Dark.Door.by.Alan.Edward.Nourse.txt | Words to be indexed: 2378 
File: ../data/Storm.Over.Warlock.by.Andre.Norton.txt | Words to be indexed: 7451 
File: ../data/A.Brief.History.of.the.United.States.by.John.Bach.McMaster.txt | Words to be indexed: 11049 
File: ../data/The.Jesuits.in.North.America.in.the.Seventeenth.Century.by.Francis.Parkman.txt | Words to be indexed: 14721 
File: ../data/Queen.Victoria.by.Lytton.Strachey.txt | Words to be indexed: 10494 
File: ../data/Crime.and.Punishment.by.Fyodor.Dostoyevsky.txt | Words to be indexed: 10642 

real 0m9.086s 
user 0m8.591s 
sys  0m0.463s 

Credo che il (stringa ->sequenza pigro) di conversione per l'attuazione Clojure sta uccidendo le prestazioni. Come posso migliorarlo?

P.S: tutti i codici e i dati utilizzati in questi test possono essere scaricati here.

Answer 1

Alcune cose che potreste fare che probabilmente accelerare questo codice su:

1) Invece di mappare i tuoi chars a char-val, basta fare il confronto valore diretto tra i personaggi. Questo è più veloce per la stessa ragione per cui sarebbe più veloce in Java.

2) Si utilizza ripetutamente lo str per convertire valori a carattere singolo in stringhe a pieno titolo. Ancora una volta, considera di usare direttamente i valori dei caratteri. Di nuovo, la creazione di oggetti è lenta, come in Java.

3) È necessario sostituire process-content con clojure.core/frequencies. Forse controlla la fonte frequencies per vedere come è più veloce.

4) Se è necessario aggiornare un (hash-map) in un ciclo, utilizzare transient. Vedere: http://clojuredocs.org/clojure_core/clojure.core/transient

Si noti inoltre che (hash-map) restituisce un PersistentArrayMap, in modo che si sta creando nuove istanze con ogni chiamata a update-in - da qui lento e perché si dovrebbe usare transitori.

5) Questo è tuo amico: (set! *warn-on-reflection* true) - Hai un po 'di riflessione che potrebbero beneficiare di type hints

Reflection warning, scratch.clj:10:13 - call to isFile can't be resolved. 
Reflection warning, scratch.clj:13:16 - call to getNumericValue can't be resolved. 
Reflection warning, scratch.clj:19:11 - call to getNumericValue can't be resolved. 
Reflection warning, scratch.clj:26:9 - call to isSpaceChar can't be resolved. 
Reflection warning, scratch.clj:30:47 - call to toLowerCase can't be resolved. 
Reflection warning, scratch.clj:48:24 - reference to field getPath can't be resolved. 
Reflection warning, scratch.clj:48:24 - reference to field getPath can't be resolved. 

Answer 2

Solo per la causa di paragone, ecco una regexp versione basata su Clojure

(defn re-index 
    "Returns lazy sequence of vectors of regexp matches and their start index" 
    [^java.util.regex.Pattern re s] 
    (let [m (re-matcher re s)] 
     ((fn step [] 
      (when (. m (find)) 
      (cons (vector (re-groups m)(.start m)) (lazy-seq (step)))))))) 

(defn group-by-keep 
    "Returns a map of the elements of coll keyed by the result of 
    f on each element. The value at each key will be a vector of the 
    results of r on the corresponding elements." 
    [f r coll] 
    (persistent! 
    (reduce 
     (fn [ret x] 
     (let [k (f x)] 
      (assoc! ret k (conj (get ret k []) (r x))))) 
     (transient {}) coll))) 

(defn word-indexed 
    [s] 
    (group-by-keep 
    (comp clojure.string/lower-case first) 
    second 
    (re-index #"\w+" s)))