Trong Clojure, làm thế nào tôi có thể làm một phiên bản hiệu suất của `tần số` với bộ chuyển đổi?

Question

(Tín dụng câu hỏi: Fernando Abrao.)

Tôi nghe về lợi ích hiệu suất của bộ chuyển đổi ở Clojure, nhưng tôi không biết cách sử dụng chúng.

Nói rằng tôi có một hàm qos/device-qos-range trả về chuỗi các bản đồ, một số trong đó chứa một số thập phân :samplevalue, như vậy:

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

tôi muốn xem có bao nhiêu :samplevalue s rơi vào mỗi bin số nguyên, như vậy:

(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} 

làm thế nào tôi có thể tắt chức năng này vào một phiên bản nhanh chóng với đầu dò rằng loại bỏ cấu trúc dữ liệu trung gian (chẳng hạn như một trả về bởi reduce)? Điểm thưởng cho mã có thể tận dụng nhiều lõi để thực hiện xử lý song song.

Answer 1

(trả lời tín dụng:. Renzo Borgatti (@reborg))

Trước tiên, hãy thiết lập một số dữ liệu mẫu, mà chúng tôi sẽ sử dụng cho các bài kiểm tra hiệu suất sau này. Vector này chứa 500k bản đồ có cùng khóa. Các giá trị được chồng chéo 1/5 thời gian.

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

Bây giờ, hãy chuyển đổi của bạn bằng bộ chuyển đổi. Lưu ý rằng giải pháp này là không phải là song song. Tôi đã rút ngắn .intValue của bạn thành chỉ int, cũng giống như vậy. Ngoài ra, tìm nạp có điều kiện :samplevalue từ mỗi bản đồ có thể được rút ngắn thành chỉ (keep :samplevalue sequence), tương đương với (remove nil? (map :samplevalue sequence)). Chúng tôi sẽ sử dụng Criterium để chuẩn.

(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 

Lưu ý rằng chúng tôi không gọi frequencies làm bước bên ngoài lần này. Thay vào đó, chúng tôi đã dệt nó vào hoạt động. Và giống như những gì frequencies làm, chúng tôi đã thực hiện các hoạt động trên một hashmap thoáng qua cho hiệu suất thêm. Chúng tôi thực hiện việc này bằng cách sử dụng băm chéo thoáng qua làm hạt giống và completing giá trị cuối cùng bằng cách gọi persistent! trên đó.

Chúng tôi có thể thực hiện việc này song song. Để có hiệu suất tối đa, chúng tôi sử dụng Java ConcurrentHashMap có thể thay đổi thay vì cấu trúc dữ liệu Clojure không thay đổi.

(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 

Ở đây chúng ta sử dụng fold từ thư viện clojure.core.reducers để đạt được xử lý song song. Lưu ý rằng trong một bối cảnh song song, bất kỳ đầu dò nào mà một người sử dụng cần phải là không trạng thái. Cũng lưu ý rằng ConcurrentHashMap không hỗ trợ sử dụng nil làm khóa hoặc giá trị; may mắn thay, chúng ta không cần phải làm điều đó ở đây.

Đầu ra được chuyển đổi thành một băm không đổi Clojure ở cuối. Bạn có thể loại bỏ bước đó và chỉ sử dụng bản sao ConcurrentHashMap để tăng tốc bổ sung — trên máy của tôi, xóa bước into khiến toàn bộ fold mất khoảng 26ms.

Sửa 2017/11/20: tài @clojuremostly một cách chính xác chỉ ra rằng một phiên bản trước của câu trả lời này có cuộc gọi đến quick-bench bên trong khối let mà khởi tạo các trường hợp bản đồ băm đồng thời, điều này có nghĩa rằng các chuẩn mực sử dụng cùng một ví dụ cho tất cả các lần chạy của nó. Tôi đã chuyển cuộc gọi đến quick-bench để ở ngoài khối let. Nó không ảnh hưởng đáng kể đến kết quả.