이맥스에서 문자열 일치 속도를 높입니다.

Question

이멕스에서 vim commandT plugin을 구현하고 싶습니다. 이 코드는 대부분 matcher의 번역입니다.

여기에 내 netbook에서 사용하기에는 너무 느린 이유가 있습니다. 어떻게 속도를 높일 수 있습니까?

(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. sort에 시간이 소비되지 않고 commandT-fuzzy-score에 있기 때문에 눈에 띄는 효과가 없습니다.
• defun* 대신 defun을 사용하십시오. 0이 아닌 기본값이있는 선택적 인수는 무시할 수없는 숨겨진 비용이 있습니다. 이렇게하면 GC 비용이 거의 절반으로 줄어 듭니다 (GC에서 소비 한 시간의 10 % 이상에서 시작).
• (* 0.75 (/ 1.0 XXX))은 (/ 0.75 XXX)와 같습니다.
• char-equal 대신 eq을 사용하십시오 (동작이 항상 대소 문자를 구분하도록 변경됩니다.). 이것은 상당히 큰 차이를 만듭니다.
• elt 대신 aref을 사용하십시오.
• 재귀 호출에서 last-found을 전달하는 이유를 모르겠으므로 분명히 알고리즘이 무엇을하는지 완전히 이해하지 못했습니다. 그러나 오류라고 가정하면 인수로 전달하는 대신 로컬 변수로 변환 할 수 있습니다. 이렇게하면 시간을 절약 할 수 있습니다.
• 이유가 무엇인지 찾아내는 모든 search-char에 대해 재귀 호출을 만드는 이유를 이해할 수 없습니다. 이것을 보는 또 다른 방법은 max이 "단일 문자 점수"를 "전체 검색 문자열 점수"와 비교하여 다소 이상하게 보일 수 있다는 것입니다. 을 loop 두 개가 아닌 코드를 변경하여 (1+ first-found)에 대한 재귀 호출로 변경하면 테스트 케이스에서 속도가 4 배 빨라집니다.
• score-per-char의 곱셈은 루프 바깥으로 이동할 수 있습니다 (원래 알고리즘에서는 그렇지 않습니다).

또한 Emacs에서 구현 된 Elisp는 매우 느리기 때문에 Elisp (바이트) 코드를 해석하고 C 코드를 실행하는 데 더 적은 시간을 소비하는 데 "큰 프리미티브"를 사용하는 것이 더 나을 때가 많습니다. 여기에 또 다른 구현 예를위한 내부 루프 할 정규 표현식 패턴 maching를 사용하여, (아니 원래 알고리즘하지만 내가 루프의 외부 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)))