加速涉及字符串搜索的函数

Question

我有一个功能，分析显示它消耗了大部分运行时间。是否有一种方法可以重新考虑这一点以实现大幅加速？ （在 SBCL 中运行 Common Lisp）

(defun compatible-words (option1 option2)
  ;Determines if two field+word fillings are compatible.
  (destructuring-bind (field1 word1) option1
    (destructuring-bind (field2 word2) option2
      (destructuring-bind (index1 index2) (or (gethash (list field1 field2) *crosscuts-ht*)
                                              '(nil nil))
        (or (null index1) (char= (schar word1 index1) (schar word2 index2)))))))

（ps：添加声明似乎效果很小。）

Answer 1

(defun compatible-words (option1 option2)
  (destructuring-bind (index1 index2) (gethash (list (car option1) (car option2)) *crosscuts-ht* '(nil nil))
    (or (null index1) (char= (schar (cadr option1) index1) 
                             (schar (cadr option2) index2)))))

我通过使用

car

和

cadr

来消除 2 个解构绑定。 无需测试，很明显

car

和

cadr

会更快，因为超级便宜。 我通过将

or

默认为

'(nil nil)

来消除一个

gethash

。

此外，您可以键入

index

和

word

变量来提高速度：

(defun compatible-words (option1 option2)
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type (cons string) option1 option2))
  (multiple-value-bind (index1 index2) (gethash (list (char option1 0) (char option2 0)) *crosscuts-ht* '(nil nil))
    (and index1
         (char= (schar option1 index1)
                (schar option2 index2))))))