优化涉及字符串检索的Common Lisp函数以提升运行速度

原函数性能瓶颈分析 #

原函数的主要性能消耗点集中在：

1. 每次调用创建新列表(list field1 field2)作为哈希键，频繁生成垃圾，且equal哈希表对列表的键比较开销较高
2. 多层destructuring-bind的绑定操作存在微小但累积的开销
3. 哈希表使用equal测试，比eq/eql的查找速度慢很多

重构优化方案 #

方案1：用Cons对替代列表作为哈希键，简化数据访问 #

将哈希表的键从(list f1 f2)改为(cons f1 f2)（需同步修改哈希表初始化逻辑），同时用直接的car/cadr访问替代destructuring-bind，减少绑定开销：

(defun compatible-words (option1 option2)
  (let ((field1 (car option1))
        (word1 (cadr option1))
        (field2 (car option2))
        (word2 (cadr option2)))
    (let* ((crosscut (gethash (cons field1 field2) *crosscuts-ht*))
           (index1 (car crosscut))
           (index2 (cadr crosscut)))
      (or (null index1)
          (char= (schar word1 index1) (schar word2 index2))))))

Cons对的创建开销比列表小，且equal对Cons对的比较逻辑更简洁，能小幅提升哈希查找速度。

方案2：改用eq测试的哈希表（大幅提升查找速度） #

如果可以预构建所有字段对的Cons实例，可将哈希表测试改为eq（指针比较，速度远快于equal）：

1. 先初始化辅助哈希表存储预构建的字段对Cons：

;; 假设原有哈希表为old-crosscuts-ht，转换为新结构
(defvar *field-pairs* (make-hash-table :test #'eq))
(defvar *crosscuts-ht* (make-hash-table :test #'eq))

(maphash (lambda (key value)
           (let* ((f1 (car key))
                  (f2 (cadr key))
                  (inner (or (gethash f1 *field-pairs*)
                             (setf (gethash f1 *field-pairs*) (make-hash-table :test #'eq))))
                  (pair (cons f1 f2)))
             (setf (gethash f2 inner) pair)
             (setf (gethash pair *crosscuts-ht*) value)))
         old-crosscuts-ht)

2. 修改函数，通过嵌套哈希表获取预构建的Cons键，避免临时对象创建：

(defun compatible-words (option1 option2)
  (let ((field1 (car option1))
        (word1 (cadr option1))
        (field2 (car option2))
        (word2 (cadr option2)))
    (let ((inner (gethash field1 *field-pairs*)))
      (if (null inner)
          t ; 无交叉规则，默认兼容
          (let ((pair (gethash field2 inner)))
            (if (null pair)
                t
                (let ((crosscut (gethash pair *crosscuts-ht*)))
                  (or (null (car crosscut))
                      (char= (schar word1 (car crosscut))
                             (schar word2 (cadr crosscut))))))))))

该方案彻底避免了临时列表/Cons的创建，且哈希查找用eq测试，性能提升最显著。

方案3：改用结构体存储option数据 #

将原有的二元列表option改为结构体，让字段访问更高效（SBCL会将结构体slot访问编译为直接内存操作）：

(defstruct word-option
  field
  word)

;; 转换原有option列表为结构体实例
;; (setf option1 (make-word-option :field field1 :word word1))

(defun compatible-words (option1 option2)
  (let ((field1 (word-option-field option1))
        (word1 (word-option-word option1))
        (field2 (word-option-field option2))
        (word2 (word-option-word option2)))
    (let ((inner (gethash field1 *field-pairs*)))
      (if (null inner)
          t
          (let ((pair (gethash field2 inner)))
            (if (null pair)
                t
                (let ((crosscut (gethash pair *crosscuts-ht*)))
                  (or (null (car crosscut))
                      (char= (schar word1 (car crosscut))
                             (schar word2 (cadr crosscut))))))))))

该方案可进一步降低数据访问的开销，适合高频调用场景。

优化核心总结 #

• 减少垃圾生成：避免每次调用创建临时列表/Cons对象
• 哈希表优化：优先使用eq测试，改用更紧凑的键类型
• 简化数据访问：用直接的car/cadr或结构体slot访问替代destructuring-bind
• 提前短路：尽早判断无交叉的情况，跳过后续不必要操作

内容的提问来源于stack exchange，提问作者davypough