Giữ chân ở Clojure

Question

Đọc đoạn về lưu giữ đầu trong "Lập trình Clojure" (trang 98), tôi không thể tìm ra điều gì xảy ra trong ví dụ split-with. Tôi đã cố thử nghiệm repl nhưng nó làm tôi bối rối hơn.

(time (let [r (range 1e7) 
      a (take-while #(< % 12) r) 
      b (drop-while #(< % 12) r)] 
     [(count a) (count b)])) 
"Elapsed time: 1910.401711 msecs" 
[12 9999988] 

(time (let [r (range 1e7) 
      a (take-while #(< % 12) r) 
      b (drop-while #(< % 12) r)] 
     [(count b) (count a)])) 
"Elapsed time: 3580.473787 msecs" 
[9999988 12] 

(time (let [r (range 1e7) 
      a (take-while #(< % 12) r) 
      b (drop-while #(< % 12) r)] 
     [(count b)])) 
"Elapsed time: 3516.70982 msecs" 
[9999988] 

Như bạn có thể nhìn thấy từ ví dụ cuối cùng, nếu tôi không tính toán a, tốn thời gian bằng cách nào đó phát triển. Tôi đoán, tôi đã bỏ lỡ một cái gì đó ở đây, nhưng những gì?

Answer 1

Count là O (1). Đó là lý do tại sao số đo của bạn không phụ thuộc vào nó.

Answer 2

Binding trong let biểu mẫu được thực hiện ngay cả khi chúng tôi không sử dụng giá trị này.

(let [x (println "Side effect")] 1) 

Mã trên bản in "Tác dụng phụ", và trở về 1.

Trong cả ba ví dụ của bạn sử dụng cùng một ràng buộc ở dạng let, vì vậy tôi không thấy bất kỳ sự khác biệt ở đây. Nhân tiện, trên máy của tôi, tất cả các đoạn trích của bạn mất khoảng thời gian bằng nhau.

Sự khác biệt thực sự khi bạn cố gắng một cái gì đó như thế này:

(time (let [r (range 2e7) 
     a (take 100 r) 
     b (drop 100 r)] 
    [(count a)])) 
"Elapsed time: 0.128304 msecs" 
[100] 

(time (let [r (range 2e7) 
     a (take 100 r) 
     b (drop 100 r)] 
    [(count b)])) 
"Elapsed time: 3807.591342 msecs" 
[19999900] 

Do thực tế là b và a là chuỗi lười biếng, count công trình trong thời gian O(n). Nhưng trong ví dụ đầu tiên, chúng tôi không tính số lượng cho b, vì vậy nó hoạt động gần như ngay lập tức.

Answer 3

Chức năng count là O (1) cho Counted bộ sưu tập, bao gồm vectơ và danh sách.

Trình tự, mặt khác, là not counted làm cho count O (n) cho chúng. Phần quan trọng ở đây là các hàm take-while và drop-while các chuỗi trả về. Thực tế là họ cũng lười biếng không phải là nhân tố chính ở đây.

Answer 4

Khi sử dụng thời gian một một chuẩn mực, chạy thử nghiệm nhiều lần để có được một kết quả chính xác

user> (defn example2 [] (let [r (range 1e7)            
       a (take-while #(< % 12) r)          
       b (drop-while #(< % 12) r)]       
      [(count a) (count b)])) 
#'user/example2 

user> (dorun (take 1000 (repeatedly example2))) 
nil 

user> (time (example2)) 
"Elapsed time: 614.4 msecs" 
[12 9999988] 

Tôi đổ lỗi sai trong thời gian chạy vì trình biên dịch hotspot chưa optomized đầy đủ các lớp học tạo ra. Tôi chạy các ví dụ đầu tiên và thứ hai vài lần và nhận được kết quả tương đối hỗn hợp:

chạy ví dụ một hai lần:

autotestbed.core> (time (let [r (range 1e7)                 
             a (take-while #(< % 12) r)          
                b (drop-while #(< % 12) r)]       
           [(count a) (count b)])) 
"Elapsed time: 929.681423 msecs"                   
[12 9999988] 
autotestbed.core> (time (let [r (range 1e7)                 
             a (take-while #(< % 12) r)          
                b (drop-while #(< % 12) r)]       
           [(count a) (count b)])) 
"Elapsed time: 887.81269 msecs"                    
[12 9999988] 

sau đó chạy ví dụ hai một vài lần:

core> (time (let [r (range 1e7)                 
        a (take-while #(< % 12) r)          
        b (drop-while #(< % 12) r)]       
      [(count a) (count b)])) 
"Elapsed time: 3838.751561 msecs"                   
[12 9999988] 
core> (time (let [r (range 1e7)                 
        a (take-while #(< % 12) r)          
        b (drop-while #(< % 12) r)]       
      [(count a) (count b)])) 
"Elapsed time: 970.397078 msecs"                   
[12 9999988] 

sometiems các ví dụ thứ hai chỉ nhanh như

Answer 5

thời gian hiển thị là hoàn toàn phụ thuộc vào hệ thống .... nếu bạn thực hiện lại, nó sẽ hiển thị một số thời gian trôi qua cho mỗi lần thực hiện