optimization - 加快 emacs 中的字符串匹配速度

Question

我想实现vim commandT plugin在 emacs 中。这段代码主要是从 matcher 翻译过来的.

我这里有一些 elisp，但在我的上网本上使用仍然太慢 - 我怎样才能加快速度？

(eval-when-compile (require 'cl))
(defun commandT-fuzzy-match (choices search-string)
  (sort (loop for choice in choices
              for score = (commandT-fuzzy-score choice search-string (commandT-max-score-per-char choice search-string))
              if (> score 0.0) collect (list score choice))
        #'(lambda (a b) (> (first a) (first b)))
        ))

(defun* commandT-fuzzy-score (choice search-string &optional (score-per-char (commandT-max-score-per-char choice search-string)) (choice-pointer 0) (last-found nil))
  (condition-case error
      (loop for search-char across search-string
            sum (loop until (char-equal search-char (elt choice choice-pointer))
                      do (incf choice-pointer)
                      finally return (let ((factor (cond (last-found (* 0.75 (/ 1.0 (- choice-pointer last-found))))
                                                         (t 1.0))))
                                       (setq last-found choice-pointer)
                                       (max (commandT-fuzzy-score choice search-string score-per-char (1+ choice-pointer) last-found)
                                            (* factor score-per-char)))))
    (args-out-of-range 0.0)   ; end of string hit without match found.
    ))

(defun commandT-max-score-per-char (choice search-string)
  (/ (+ (/ 1.0 (length choice)) (/ 1.0 (length search-string))) 2))

一定要编译该部分，因为这已经有很大帮助了。 和一个基准:

(let ((choices (split-string (shell-command-to-string "curl http://sprunge.us/FcEL") "\n")))
  (benchmark-run-compiled 10
      (commandT-fuzzy-match choices "az")))

Answer 1

以下是您可以尝试的一些微观优化:

• 使用 car-less-than-car 代替 lambda 表达式。这没有明显的效果，因为时间不是花在 sort 上，而是花在 commandT-fuzzy-score 上。
• 使用 defun 而不是 defun*:那些默认值非零的可选参数具有不可忽略的隐藏成本。这将 GC 成本降低了近一半(并且您开始时花费了超过 10% 的时间在 GC 上)。
• (* 0.75 (/1.0 XXX)) 等于 (/0.75 XXX)。
• 使用 eq 而不是 char-equal (这会将行为更改为始终区分大小写)。这造成了相当大的差异。
• 使用aref而不是elt。
• 我不明白为什么你在递归调用中传递last-found，所以我显然不完全理解你的算法在做什么。但假设这是一个错误，您可以将其转换为局部变量，而不是将其作为参数传递。这可以节省您的时间。
• 我不明白为什么您要对找到的每个 search-char 进行递归调用，而不是仅对第一个进行递归调用。另一种看待这个问题的方法是，您的 max 将“单字符分数”与“整个搜索字符串分数”进行比较，这看起来相当奇怪。如果您更改代码以在两个循环之外执行max，并在(1+first-found)上进行递归调用，那么在我的测试用例中，速度提高了 4 倍。
• 与score-per-char 的乘法可以移到循环之外(这对于您的原始算法来说似乎并非如此)。

此外，Emacs 中实现的 Elisp 速度相当慢，因此您通常最好使用“大原语”，以便花更少的时间解释 Elisp(字节)代码，而花更多的时间运行 C 代码。例如，这是一种替代实现(不是您的原始算法，而是我将 max 移出循环后得到的算法)，使用正则表达式模式处理来执行内部循环:

(defun commandT-fuzzy-match-re (choices search-string)
  (let ((search-re (regexp-quote (substring search-string 0 1)))
        (i 1))
    (while (< i (length search-string))
      (setq search-re (concat search-re
                              (let ((c (aref search-string i)))
                                (format "[^%c]*\\(%s\\)"
                                        c (regexp-quote (string c))))))
      (setq i (1+ i)))

    (sort
     (delq nil
           (mapcar (lambda (choice)
                     (let ((start 0)
                           (best 0.0))
                       (while (string-match search-re choice start)
                         (let ((last-found (match-beginning 0)))
                           (setq start (1+ last-found))
                           (let ((score 1.0)
                                 (i 1)
                                 (choice-pointer nil))
                             (while (setq choice-pointer (match-beginning i))
                               (setq i (1+ i))
                               (setq score (+ score (/ 0.75 (- choice-pointer last-found))))
                               (setq last-found choice-pointer))
                             (setq best (max best score)))))
                       (when (> best 0.0)
                         (list (* (commandT-max-score-per-char
                                   choice search-string)
                                  best)
                               choice))))
                   choices))
     #'car-less-than-car)))