tại sao chức năng lặp này quá chậm so với bản đồ?

Question

Tôi đã xem mã nguồn bản đồ mà về cơ bản vẫn tạo ra các chuỗi lười biếng. Tôi nghĩ rằng việc lặp lại trên một bộ sưu tập và thêm vào một vector tạm thời sẽ nhanh hơn, nhưng rõ ràng nó không phải là. Tôi không hiểu gì về hành vi của clojures?

;=> (time (do-with/(range 1 1000) (range 1 1000))) 
;"Elapsed time: 23.1808 msecs" 
; 
; vs 
;=> (time (doall (map #(/ %1 %2) (range 1 1000) (range 1 1000)))) 
;"Elapsed time: 2.604174 msecs" 
(defn do-with 
    [fn coll1 coll2] 
    (let [end (count coll1)] 
    (loop [i 0 
      res (transient [])] 
     (if 
      (= i end) 
      (persistent! res) 
      (let [x (nth coll1 i) 
        y (nth coll2 i) 
        r (fn x y)] 
       (recur (inc i) (conj! res r))) 
       )))) 

Answer 1

Theo thứ tự tác động Gauss phát biểu ngày kết quả tương đối:

1. chức năng do-with của bạn sử dụng nth để truy cập các mục riêng trong các bộ sưu tập đầu vào. nth hoạt động theo thời gian tuyến tính trên các phạm vi, làm cho do-with bậc hai. Không cần phải nói, điều này sẽ giết hiệu suất trên các bộ sưu tập lớn.

2. range tạo seqs chunked và map xử lý chúng cực kỳ hiệu quả. (Về cơ bản nó tạo ra các khối lên đến 32 phần tử - ở đây nó thực tế sẽ chính xác là 32 - bằng cách chạy một vòng lặp chặt chẽ trên mảng nội bộ của mỗi đoạn đầu vào lần lượt, đặt kết quả vào mảng nội bộ của khối đầu ra.)

3. Đo điểm chuẩn với time không cho bạn hiệu suất trạng thái ổn định. (Đó là lý do tại sao ai thực sự nên sử dụng một thư viện chuẩn thích hợp; trong trường hợp Clojure, Criterium sự là giải pháp tiêu chuẩn.)

Ngẫu nhiên, (map #(/ %1 %2) xs ys) chỉ đơn giản có thể được viết như (map/xs ys).

Cập nhật:

Tôi đã benchmarked phiên bản map, bản gốc do-with và do-with phiên bản mới với criterium, sử dụng (range 1 1000) như cả hai đầu vào trong từng trường hợp (như trong văn bản câu hỏi), có ý kiến ​​sau có nghĩa là thời gian thực hiện:

;;; (range 1 1000) 
new do-with   170.383334 µs 
(doall (map ...))  230.756753 µs 
original do-with  15.624444 ms 

Ngoài ra, tôi đã lặp đi lặp lại các tiêu chuẩn sử dụng một vector lưu trữ trong một Var như là đầu vào chứ không phải là dãy (có nghĩa là, với (def r (vec (range 1 1000))) tại bắt đầu một d sử dụng r làm cả hai đối số thu thập trong mỗi điểm chuẩn). Không ngạc nhiên, ban đầu do-with đến trước - nth là rất nhanh trên vectơ (cộng với việc sử dụng nth với một vectơ tránh tất cả các phân bổ trung gian tham gia vào quá trình tra cứu).

;;; (vec (range 1 1000)) 
original do-with  73.975419 µs 
new do-with   87.399952 µs 
(doall (map ...))  153.493128 µs 

Đây là mới do-with với độ phức tạp thời gian tuyến tính:

(defn do-with [f xs ys] 
    (loop [xs (seq xs) 
     ys (seq ys) 
     ret (transient [])] 
    (if (and xs ys) 
     (recur (next xs) 
      (next ys) 
      (conj! ret (f (first xs) (first ys)))) 
     (persistent! ret))))