lisp - SBCL "subst"效率

Question

我刚刚编写了一个程序，在循环内调用 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 用户手册描述了如何解释此表:

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 中以有效的方式实现的吗？如果没有，是否有更有效的替代方案可以用来执行替换？

感谢您的帮助

Answer 1

查看标准函数 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 中，尾递归函数并不总是转换为有效的循环。