Bạn thực sự có thể truy cập bảng băm ba lần. Tại sao? Vì macro push có thể mở rộng thành mã thực hiện gethash để lấy danh sách và sau đó một số hoạt động system::sethash để lưu trữ giá trị.
Trong vấn đề này, bạn đang kiểm tra giá trị của một địa điểm, đó là danh sách. Nếu danh sách đó thỏa mãn một số thử nghiệm vị ngữ, thì bạn đẩy thứ gì đó vào vị trí đó.
Vấn đề này có thể bị tấn công bằng cách tạo điều hành chuyên dùng mà chụp ngữ nghĩa này:
(push-if <new-value> <predicate> <place>)
Ví dụ:
(push-if i #'may-add (gethash complex-list table))
push-if này được định nghĩa là một macro trong đó sử dụng các get-setf-expansion chức năng trên đối số biểu mẫu <place> để nhận các phần cần thiết để tạo mã để truy cập địa điểm đó chỉ một lần.
Mã được tạo sẽ đánh giá biểu mẫu tải để lấy giá trị cũ từ vị trí, sau đó áp dụng điều kiện cho giá trị cũ và nếu nó thành công, thì nó sẽ chuẩn bị giá trị mới trong biến lưu trữ tạm thời thích hợp thu được từ get-setf-expansion và đánh giá biểu mẫu lưu trữ.
Đây là cách tốt nhất bạn có thể thực hiện trong Lisp di động và bạn có thể thấy rằng điều này vẫn thực hiện hai thao tác băm, như đã đề cập ở trên. (Trong trường hợp này, bạn hy vọng có tối ưu hóa bộ nhớ đệm khá tốt trong bảng băm. Nhưng ít nhất nó là hai phần mềm.)
Cách tiếp cận sẽ được tối ưu hóa như được xây dựng ở dạng biến đổi: incf, push , rotatef, v.v. push-if của chúng tôi sẽ ngang hàng với các bản dựng sẵn.
Nếu nó vẫn hút (thực hiện hai băm để cập nhật vị trí băm, không có tối ưu hóa bộ nhớ đệm), thì cách duy nhất để khắc phục điều đó ở cấp độ triển khai.
push-if đang sau: mở rộng
(defmacro push-if (new-value predicate-fun list-place &environment env)
(multiple-value-bind (temp-syms val-forms
store-vars store-form access-form)
(get-setf-expansion list-place env)
(let ((old-val (gensym)))
(when (rest store-vars)
(error "PUSH-IF: cannot take ref of multiple-value place"))
`(multiple-value-bind (,@temp-syms) (values ,@val-forms)
(let ((,old-val ,access-form))
(when (funcall ,predicate-fun ,old-val)
(setf ,(first store-vars) (cons ,new-value ,old-val))
,store-form))))))
mẫu:
> (macroexpand '(push-if new test place))
(LET* ((#:VALUES-12731 (MULTIPLE-VALUE-LIST (VALUES))))
(LET ((#:G12730 PLACE))
(WHEN (FUNCALL TEST #:G12730) (SETF #:NEW-12729 (CONS NEW #:G12730))
(SETQ PLACE #:NEW-12729)))) ;
Trông lành mạnh đối với trường hợp đơn giản khi nơi này là một biến. Chỉ có một vấn đề nhỏ mà tôi sẽ không sửa chữa: các hình thức new, test và place được đánh giá chỉ một lần, nhưng không phải theo thứ tự từ trái sang phải!
Thử nghiệm với một nơi bảng băm (CLISP):
> (macroexpand '(push-if new test (gethash a b)))
(LET*
((#:VALUES-12736 (MULTIPLE-VALUE-LIST (VALUES A B)))
(#:G12732 (POP #:VALUES-12736)) (#:G12733 (POP #:VALUES-12736)))
(LET ((#:G12735 (GETHASH #:G12732 #:G12733)))
(WHEN (FUNCALL TEST #:G12735) (SETF #:G12734 (CONS NEW #:G12735))
(SYSTEM::PUTHASH #:G12732 #:G12733 #:G12734)))) ;
Aha; bây giờ có một số mã thú vị hơn được tạo ra để tránh đánh giá a và b hai lần. Hàm gethash được gọi một lần, nhưng đối số của nó là các biến gensym. Giá trị cũ được chụp là #:G12735. Các thử nghiệm được áp dụng cho nó, và nếu nó vượt qua, các cửa hàng variabel #:G12734 được cập nhật với một giá trị danh sách cũ với new consed ở phía trước của nó. Sau đó, giá trị đó được đưa vào bảng băm với system::puthash.
Vì vậy, trong triển khai Lisp này, không có cách nào để tránh hai thao tác bảng băm để thực hiện cập nhật: gethash và system::puthash. Đây là điều tốt nhất chúng ta có thể làm và hy vọng rằng hai người làm việc như một cặp được tối ưu hóa.
Tuyệt vời - cảm ơn :) –
Có vẻ như chúng ta có thể cảm ơn Paul F. Dietz: http://git.boinkor.net/gitweb/sbcl.git/commitdiff/bc1783335d78be988465e4fc7cf9c5fdb88a3fa4 –