SBCL "subst" 效率
SBCL "subst" efficiency
我刚刚编写了一个在循环内调用 subst 的程序，以及许多其他函数，到目前为止，subst 函数调用花费的时间最多。下面是一个概念性的代码片段，其中包含我编写的程序的精神。
(loop
with bindings = ((symbol1 . 1) (sybmol2 . 2) ... (sybmoln . n))
with x-copy
for x in xs
do
...
(setq x-copy (copy-cpd x))
(setf (cpd-identifiers1 x-copy) (subst-bindings bindings (cpd-identifiers1 x)))
(setf (cpd-identifiers2 x-copy) (subst-bindings bindings (cpd-identifiers2 x)))
...)
subst-bindings 在内部对 subst 进行递归调用：
(defun subst-bindings (bindings generic)
(cond ((null bindings) generic)
(t (subst-bindings (cdr bindings)
(subst (cdar bindings) (caar bindings) generic)))))
我 运行 我的实际代码启用了统计分析器，我得到了这些结果：
Self Total Cumul
Nr Count % Count % Count % Calls Function
------------------------------------------------------------------------
1 4585 45.8 6840 68.4 4585 45.8 - (LABELS SB-IMPL::S :IN SUBST)
2 2204 22.0 2205 22.1 6789 67.9 - EQL
3 489 4.9 489 4.9 7278 72.8 - SUBST
4 315 3.2 7537 75.4 7593 75.9 - SUBST-BINDINGS
5 150 1.5 235 2.3 7743 77.4 - PPRINT-DISPATCH
6 143 1.4 274 2.7 7886 78.9 - SB-IMPL::%FIND-SYMBOL
7 114 1.1 114 1.1 8000 80.0 - SB-IMPL::%MAKE-STRING-OUTPUT-STREAM
8 106 1.1 347 3.5 8106 81.1 - SB-KERNEL:OUTPUT-SYMBOL-NAME
9 94 0.9 113 1.1 8200 82.0 - SB-IMPL::STRING-SOUT
10 73 0.7 155 1.5 8273 82.7 - SB-KERNEL::VALUES-SPECIFIER-TYPE-R
11 70 0.7 70 0.7 8343 83.4 - SB-KERNEL:UB32-BASH-COPY
12 56 0.6 56 0.6 8399 84.0 - SB-KERNEL:%SXHASH-SIMPLE-SUBSTRING
13 51 0.5 51 0.5 8450 84.5 - MAKE-CPD
14 48 0.5 160 1.6 8498 85.0 - GET-OUTPUT-STREAM-STRING
15 48 0.5 48 0.5 8546 85.5 - WRITE-STRING
16 44 0.4 44 0.4 8590 85.9 - SB-KERNEL:%COERCE-CALLABLE-TO-FUN
17 43 0.4 741 7.4 8633 86.3 - PRINC
18 43 0.4 60 0.6 8676 86.8 - POSITION
19 39 0.4 151 1.5 8715 87.2 - SB-IMPL::%WRITE-STRING
20 39 0.4 46 0.5 8754 87.5 - SB-KERNEL:STRING=*
21 37 0.4 195 2.0 8791 87.9 - SB-KERNEL::SPECIFIER-TYPE-R
22 37 0.4 169 1.7 8828 88.3 - OPERATE-FACTOR
23 36 0.4 68 0.7 8864 88.6 - SB-VM::GENERIC-+
24 36 0.4 36 0.4 8900 89.0 - COPY-LIST
25 35 0.4 231 2.3 8935 89.4 - SB-KERNEL:SPECIFIER-TYPE
26 33 0.3 314 3.1 8968 89.7 - SB-INT:%INTERN
27 32 0.3 9146 91.5 9000 90.0 - CANDIDATE-NODES
28 31 0.3 31 0.3 9031 90.3 - SB-IMPL::SETUP-PRINTER-STATE
29 30 0.3 79 0.8 9061 90.6 - COPY-SEQ
30 30 0.3 45 0.4 9091 90.9 - GET-FULLY-QUALIFIED-CPD-VARS
31 30 0.3 30 0.3 9121 91.2 - SB-IMPL::OUTPUT-SYMBOL
32 28 0.3 1724 17.2 9149 91.5 - GENERATE-CPD-VARS
33 26 0.3 63 0.6 9175 91.8 - SB-INT:EQUAL-BUT-NO-CAR-RECURSION
34 25 0.3 25 0.3 9200 92.0 - SB-IMPL::VECTOR-SUBSEQ-DISPATCH/SIMPLE-VECTOR
35 24 0.2 24 0.2 9224 92.2 - (SB-IMPL::OPTIMIZED-DATA-VECTOR-REF T)
36 23 0.2 23 0.2 9247 92.5 - SB-KERNEL:HAIRY-DATA-VECTOR-REF/CHECK-BOUNDS
37 21 0.2 685 6.8 9268 92.7 - (LABELS SB-IMPL::HANDLE-IT :IN SB-KERNEL:OUTPUT-OBJECT)
38 20 0.2 70 0.7 9288 92.9 - SB-IMPL::COMPUTE-SYMBOL-HASH
39 19 0.2 1295 12.9 9307 93.1 - COMBINE-SYMBOLS
40 19 0.2 395 4.0 9326 93.3 - INTERN
41 19 0.2 104 1.0 9345 93.5 - (FLET SB-IMPL::REPLACE-ALL :IN GET-OUTPUT-STREAM-STRING)
42 19 0.2 19 0.2 9364 93.6 - SB-C:RETURN-MULTIPLE
43 19 0.2 19 0.2 9383 93.8 - SB-KERNEL:VECTOR-SUBSEQ*
44 18 0.2 133 1.3 9401 94.0 - COPY-CPD
SBCL 用户手册描述了如何解释这个 table:
For each function, the table will show three absolute and relative
sample counts. The Self column shows samples taken while directly
executing that function. The Total column shows samples taken while
executing that function or functions called from it (sampled to a
platform-specific depth). The Cumul column shows the sum of all Self
columns up to and including that line in the table.
如您所见，前三个条目中有两个是与 subst 相关的函数，并且在这些函数中获取的样本百分比比其余函数调用不成比例。这让我想知道，subst 是在 sbcl 中以有效的方式实现的吗？如果没有，我可以使用更有效的替代方法来执行替换吗？
感谢您的帮助
查看标准函数 sublis 和 nsublis。他们使用关联列表进行替换。
CL-USER > (sublis '((x . 10) (y . 20))
'(* x (+ x y) (* y y)))
(* 10 (+ 10 20) (* 20 20))
风格：
我不会以递归方式编写替换函数。
(defun subst-bindings (bindings generic)
(loop for (b v) in bindings
do (setf generic (subst v b generic)))
generic)
以上确保它实际上是一个循环，并且解构使得代码在这种情况下更短一些以供阅读。在可移植的 Common Lisp 中，尾递归函数并不总是转换为有效的循环。
我刚刚编写了一个在循环内调用 subst 的程序，以及许多其他函数，到目前为止，subst 函数调用花费的时间最多。下面是一个概念性的代码片段，其中包含我编写的程序的精神。
(loop
with bindings = ((symbol1 . 1) (sybmol2 . 2) ... (sybmoln . n))
with x-copy
for x in xs
do
...
(setq x-copy (copy-cpd x))
(setf (cpd-identifiers1 x-copy) (subst-bindings bindings (cpd-identifiers1 x)))
(setf (cpd-identifiers2 x-copy) (subst-bindings bindings (cpd-identifiers2 x)))
...)
subst-bindings 在内部对 subst 进行递归调用：
(defun subst-bindings (bindings generic)
(cond ((null bindings) generic)
(t (subst-bindings (cdr bindings)
(subst (cdar bindings) (caar bindings) generic)))))
我 运行 我的实际代码启用了统计分析器，我得到了这些结果：
Self Total Cumul
Nr Count % Count % Count % Calls Function
------------------------------------------------------------------------
1 4585 45.8 6840 68.4 4585 45.8 - (LABELS SB-IMPL::S :IN SUBST)
2 2204 22.0 2205 22.1 6789 67.9 - EQL
3 489 4.9 489 4.9 7278 72.8 - SUBST
4 315 3.2 7537 75.4 7593 75.9 - SUBST-BINDINGS
5 150 1.5 235 2.3 7743 77.4 - PPRINT-DISPATCH
6 143 1.4 274 2.7 7886 78.9 - SB-IMPL::%FIND-SYMBOL
7 114 1.1 114 1.1 8000 80.0 - SB-IMPL::%MAKE-STRING-OUTPUT-STREAM
8 106 1.1 347 3.5 8106 81.1 - SB-KERNEL:OUTPUT-SYMBOL-NAME
9 94 0.9 113 1.1 8200 82.0 - SB-IMPL::STRING-SOUT
10 73 0.7 155 1.5 8273 82.7 - SB-KERNEL::VALUES-SPECIFIER-TYPE-R
11 70 0.7 70 0.7 8343 83.4 - SB-KERNEL:UB32-BASH-COPY
12 56 0.6 56 0.6 8399 84.0 - SB-KERNEL:%SXHASH-SIMPLE-SUBSTRING
13 51 0.5 51 0.5 8450 84.5 - MAKE-CPD
14 48 0.5 160 1.6 8498 85.0 - GET-OUTPUT-STREAM-STRING
15 48 0.5 48 0.5 8546 85.5 - WRITE-STRING
16 44 0.4 44 0.4 8590 85.9 - SB-KERNEL:%COERCE-CALLABLE-TO-FUN
17 43 0.4 741 7.4 8633 86.3 - PRINC
18 43 0.4 60 0.6 8676 86.8 - POSITION
19 39 0.4 151 1.5 8715 87.2 - SB-IMPL::%WRITE-STRING
20 39 0.4 46 0.5 8754 87.5 - SB-KERNEL:STRING=*
21 37 0.4 195 2.0 8791 87.9 - SB-KERNEL::SPECIFIER-TYPE-R
22 37 0.4 169 1.7 8828 88.3 - OPERATE-FACTOR
23 36 0.4 68 0.7 8864 88.6 - SB-VM::GENERIC-+
24 36 0.4 36 0.4 8900 89.0 - COPY-LIST
25 35 0.4 231 2.3 8935 89.4 - SB-KERNEL:SPECIFIER-TYPE
26 33 0.3 314 3.1 8968 89.7 - SB-INT:%INTERN
27 32 0.3 9146 91.5 9000 90.0 - CANDIDATE-NODES
28 31 0.3 31 0.3 9031 90.3 - SB-IMPL::SETUP-PRINTER-STATE
29 30 0.3 79 0.8 9061 90.6 - COPY-SEQ
30 30 0.3 45 0.4 9091 90.9 - GET-FULLY-QUALIFIED-CPD-VARS
31 30 0.3 30 0.3 9121 91.2 - SB-IMPL::OUTPUT-SYMBOL
32 28 0.3 1724 17.2 9149 91.5 - GENERATE-CPD-VARS
33 26 0.3 63 0.6 9175 91.8 - SB-INT:EQUAL-BUT-NO-CAR-RECURSION
34 25 0.3 25 0.3 9200 92.0 - SB-IMPL::VECTOR-SUBSEQ-DISPATCH/SIMPLE-VECTOR
35 24 0.2 24 0.2 9224 92.2 - (SB-IMPL::OPTIMIZED-DATA-VECTOR-REF T)
36 23 0.2 23 0.2 9247 92.5 - SB-KERNEL:HAIRY-DATA-VECTOR-REF/CHECK-BOUNDS
37 21 0.2 685 6.8 9268 92.7 - (LABELS SB-IMPL::HANDLE-IT :IN SB-KERNEL:OUTPUT-OBJECT)
38 20 0.2 70 0.7 9288 92.9 - SB-IMPL::COMPUTE-SYMBOL-HASH
39 19 0.2 1295 12.9 9307 93.1 - COMBINE-SYMBOLS
40 19 0.2 395 4.0 9326 93.3 - INTERN
41 19 0.2 104 1.0 9345 93.5 - (FLET SB-IMPL::REPLACE-ALL :IN GET-OUTPUT-STREAM-STRING)
42 19 0.2 19 0.2 9364 93.6 - SB-C:RETURN-MULTIPLE
43 19 0.2 19 0.2 9383 93.8 - SB-KERNEL:VECTOR-SUBSEQ*
44 18 0.2 133 1.3 9401 94.0 - COPY-CPD
SBCL 用户手册描述了如何解释这个 table:
For each function, the table will show three absolute and relative sample counts. The Self column shows samples taken while directly executing that function. The Total column shows samples taken while executing that function or functions called from it (sampled to a platform-specific depth). The Cumul column shows the sum of all Self columns up to and including that line in the table.
如您所见，前三个条目中有两个是与 subst 相关的函数，并且在这些函数中获取的样本百分比比其余函数调用不成比例。这让我想知道，subst 是在 sbcl 中以有效的方式实现的吗？如果没有，我可以使用更有效的替代方法来执行替换吗？
感谢您的帮助
查看标准函数 sublis 和 nsublis。他们使用关联列表进行替换。
CL-USER > (sublis '((x . 10) (y . 20))
'(* x (+ x y) (* y y)))
(* 10 (+ 10 20) (* 20 20))
风格：
我不会以递归方式编写替换函数。
(defun subst-bindings (bindings generic)
(loop for (b v) in bindings
do (setf generic (subst v b generic)))
generic)
以上确保它实际上是一个循环，并且解构使得代码在这种情况下更短一些以供阅读。在可移植的 Common Lisp 中，尾递归函数并不总是转换为有效的循环。