2

我想在 emacs中实现vim commandT 插件。这段代码主要是从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")))
4

1 回答 1

3

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

  • 使用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（这会将行为更改为始终区分大小写，tho）。这产生了相当大的差异。
  • 使用aref而不是elt.
  • 我不明白你为什么要传递last-found你的递归调用，所以我显然不完全理解你的算法在做什么。但是假设这是一个错误，您可以将其转换为局部变量，而不是将其作为参数传递。这可以节省您的时间。
  • 我不明白为什么你对search-char你找到的每一个都进行递归调用，而不仅仅是第一个。另一种看待这个问题的方法是，您max将“单字符分数”与“整个搜索字符串分数”进行比较，这似乎很奇怪。如果您将代码更改为使用递归调用 onmax执行两个 s 的外部，那么在我的测试用例中它会加快 4 倍。loop(1+ first-found)
  • 乘法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)))
于 2012-10-26T15:01:24.907 回答