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ラムダ式の代わりに使用してください。sort時間は ではなくで費やされるため、これは目に見える効果はありませんcommandT-fuzzy-score。
  • defunの代わりに使用defun*: nil 以外のデフォルトを持つオプションの引数には、無視できない隠れたコストがあります。これにより、GC コストがほぼ半分に削減されます (そして、GC に費やされる時間の 10% 以上から開始しました)。
  • (* 0.75 (/ 1.0 XXX)) は (/ 0.75 XXX) に等しくなります。
  • eq代わりに使用しますchar-equal（これにより、常に大文字と小文字が区別されるように動作が変更されます）。これはかなり大きな違いになります。
  • arefの代わりに使用しeltます。
  • 再帰呼び出しを渡す理由がわからないlast-foundので、アルゴリズムが何をしているのか完全にはわかりません。ただし、それがエラーであると仮定すると、引数として渡す代わりにローカル変数に変換できます。これにより、時間を節約できます。
  • search-char最初のものだけではなく、見つけたものすべてに対して再帰呼び出しを行う理由がわかりません。これを見る別の方法はmax、「単一文字スコア」を「検索文字列全体のスコア」と比較することです。これはかなり奇妙に思えます。再帰呼び出し onでmax2 つの s の外側を実行するようにコードを変更すると、私のテスト ケースでは 4 倍高速化されます。loop(1+ first-found)
  • 乗算 byscore-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 に答える