W Clojure, w jaki sposób mogę wykonać wydajną wersję "częstotliwości" z przetwornikami?

Question

(Pytanie: Fernando Abrao.)

Słyszę o zaletach przetworników w Clojure, ale nie jestem pewien, jak z nich korzystać.

Say mam qos/device-qos-range funkcję, która zwraca ciąg map, z których niektóre zawierają dziesiętną :samplevalue, tak:

[ 
    { :samplevalue 1.3, ... }, 
    { :othervalue -27.7, ... }, 
    { :samplevalue 7.5, ... }, 
    { :samplevalue 1.9, ... }, 
] 

Chciałbym zobaczyć ile :samplevalue s spadek do każdego kosza całkowitą, tak:

(frequencies 
    (reduce #(if (not (nil? (:samplevalue %2))) 
      (conj %1 (.intValue (:samplevalue %2)))) 
      [] 
      (qos/device-qos-range origem device qos alvo inicio fim))) 

;; => {1 2, 7 1} 

Jak mogę przekształcić szybkiej wersji z przetwornikami, który eliminuje pośrednich struktur danych (takich jak ten zwrócony przez reduce)? Punkty premiowe za kod, który może wykorzystać wiele rdzeni do przetwarzania równoległego.

Answer 1

(kredyt Odpowiedź:. Renzo Borgatti (@reborg))

Najpierw skonfigurować niektóre przykładowe dane, których użyjemy do testów wydajności później. Ten wektor zawiera 500k map z tym samym kluczem. Wartości pokrywają się 1/5 tego czasu.

(def data 
(mapv hash-map 
     (repeat :samplevalue) 
     (concat (range 1e5) 
       (range 1e5) 
       (range 1e5) 
       (range 1e5) 
       (range 1e5)))) 

Teraz zróbmy transformację za pomocą przetworników. Zauważ, że to rozwiązanie jest równe , a nie. Skróciłem twój .intValue do tylko int, co robi to samo. Ponadto warunkowe pobieranie :samplevalue z każdej mapy można skrócić do zaledwie (keep :samplevalue sequence), co jest równoważne z (remove nil? (map :samplevalue sequence)). Do testowania użyjemy Criterium.

(require '[criterium.core :refer [quick-bench]]) 
(quick-bench 
    (transduce 
    (comp 
     (keep :samplevalue) 
     (map int)) 
    (completing #(assoc! %1 %2 (inc (get %1 %2 0))) persistent!) 
    (transient {}) 
    data)) 
;; My execution time mean: 405 ms 

pamiętać, że nie dzwonisz frequencies jako kroku zewnętrznym tym czasie. Zamiast tego wpleciliśmy go w operację. I tak jak robimy to, co robimy frequencies, wykonaliśmy operacje na przejściowej mieszance, aby uzyskać dodatkową wydajność. Robimy to za pomocą przejściowej mapy dźwiękowej jako materiału siewnego i końcowej wartości podając persistent!.

Możemy zrobić to równolegle. Aby uzyskać maksymalną wydajność, używamy zmiennego środowiska Java ConcurrentHashMap zamiast niezmiennej struktury danych Clojure.

(require '[clojure.core.reducers :as r]) 
(import '[java.util HashMap Collections Map] 
     'java.util.concurrent.atomic.AtomicInteger 
     'java.util.concurrent.ConcurrentHashMap) 

(quick-bench 
    (let [concurrency-level (.availableProcessors (Runtime/getRuntime)) 
     m (ConcurrentHashMap. (quot (count data) 2) 0.75 concurrency-level) 
     combinef (fn ([] m) ([_ _])) ; just return `m` from the combine step 
     rf (fn [^Map m k] 
      (let [^AtomicInteger v (or (.get m k) (.putIfAbsent m k (AtomicInteger. 1)))] 
       (when v (.incrementAndGet v)) 
       m)) 
     reducef ((comp (keep :samplevalue) (map int)) rf)] 
    (r/fold combinef reducef data) 
    (into {} m))) 
;; My execution time mean: 70 ms 

Tutaj używamy fold z biblioteki clojure.core.reducers osiągnąć równoległość. Należy zauważyć, że w kontekście równoległym każdy używany przetwornik musi być bezstanowy. Zauważ też, że ConcurrentHashMap nie obsługuje używania nil jako klucza lub wartości; na szczęście nie musimy tego robić tutaj.

Dane wyjściowe są konwertowane na niezmienną listę funkcji Clojure na końcu. Możesz usunąć ten krok i po prostu użyć instancji ConcurrentHashMap dla dodatkowego przyspieszenia - na moim komputerze, usunięcie kroku zajmuje około 26 ms.

Edycja 20.11.2017: użytkownika @clojuremostly prawidłowo wskazał, że wcześniejsza wersja tej odpowiedzi miał wezwanie do quick-bench wewnątrz bloku let że zainicjowany jednoczesne wystąpienie hash Mapa, co oznaczało, że punktem odniesienia używany to samo wystąpienie dla wszystkich jego przebiegów. Przeniosłem wywołanie na quick-bench, aby znaleźć się poza blokiem let. Nie wpłynęło to znacząco na wyniki.