string - Lisp performance optimal solution in string processing

Question

I have a string with underscores separating words (e.g. aaa_bbb_ccc)

I created a function to covert the string to camelCase (e.g. aaaBbbCcc).

I am wondering if there are some things that I am doing wrong which affect the performance. This is the code:

(defun underscore-to-camel (input)
        (defparameter input-clean-capitalized (remove #\_ (string-capitalize input)))
        (setf (aref input-clean-capitalized 0) (aref (string-downcase (aref input-clean-capitalized 0)) 0))
        input-clean-capitalized)

I also created a second variant but it is ~25% slower (measured 3 million executions using time):

(defun underscore-to-camel-v2 (input)
        (defparameter input-clean-capitalized (remove #\_ (string-capitalize input)))
        (concatenate 
            'string 
            (string-downcase (aref input-clean-capitalized 0)) 
            (subseq input-clean-capitalized 1)))

score 3 · Accepted Answer

首先，defparameter 不是您想要使用的。你真的应该像这样重构你的代码：

(defun underscore-to-camel (input)
  (let ((input-clean-capitalized (remove #\_ (string-capitalize input))))
    (setf (aref input-clean-capitalized 0)
          (aref (string-downcase (aref input-clean-capitalized 0)) 0))
    input-clean-capitalized))

第二：你可以这样处理问题：

(defun underscore-to-camel-eff (input)
  (declare (optimize (debug 1) (speed 3) (safety 1)))
  (loop :with length = (length input)
        :with i = 0
        :while (< i length)
        :for c = (aref input i)
        :if (or (= i (- length 1))
                (char/= c #\_))
        :collect (prog1 c (incf i)) :into result
        :else
        :collect (prog1
                   (char-upcase (aref input (+ i 1)))
                   (incf i 2))
        :into result
        :finally (return (concatenate 'string result))))

它在我的带有 SBCL 的 PC 上运行，只需您解决方案的一半时间。

这是一个使用正则表达式的解决方案，尽管比任何其他解决方案都慢：

(defun underscore-to-camel-ppcre (input)
  (declare (optimize (debug 1) (speed 3) (safety 1)))
  (ppcre:regex-replace-all "_([a-z])"
                           input
                           (lambda (target-string
                                    start
                                    end
                                    match-start
                                    match-end
                                    reg-starts
                                    reg-ends)
                             (declare (ignore start
                                              end
                                              match-end
                                              reg-starts
                                              reg-ends))
                             (string
                              (char-upcase
                               (aref target-string (+ 1 match-start)))))))

必要的包称为“ppcre”。你可以通过安装它

(ql:quickload "cl-ppcre")

一旦您访问http://www.quicklisp.org/beta/并安装了 quicklisp。

score 2 · Accepted Answer

我建议使用字符级函数。他们以char-. 然后你可以摆脱STRING-DOWNCASE和“CONCATENATE”。

DEFPARAMETER不用于局部变量。使用LET.

但一个简单的版本是这样的：

(defun underscore-to-camel (input)
  (string-downcase (remove #\_ (string-capitalize input))
                   :start 0
                   :end 1))

score 2 · Accepted Answer

在用 SBCL 试验了一段时间后，这是我发现的最快的版本

(defun camelcase (s)
  (do* ((n (length s))
        (i 0 (the fixnum (1+ i)))
        (wp 0)
        (target (make-array n :element-type 'character)))
      ((>= i n) (subseq target 0 wp))
    (declare (fixnum n i wp)
             (string s))
    (if (and (< i (the fixnum (1- n)))
             (char= (char s i) #\_)
             (char>= (char s (the fixnum (1+ i))) #\a)
             (char<= (char s (the fixnum (1+ i))) #\z))
        (setf (aref target (1- (the fixnum (incf wp))))
              (code-char (- (char-code (char s (the fixnum (incf i)))) 32)))
        (setf (aref target (1- (the fixnum (incf wp))))
              (char s i)))))

而不是调用#'char-upcase我只是减去 32，因为已知该字符在a-z范围内，我假设是 ASCII 编码。这减少了一些周期。

另外由于某种原因，我不明白显式数组填充比使用vector-push.

score 2 · Accepted Answer

另一种方法：

(defun underscore-to-camel (input)
  (with-output-to-string (s)
    (loop
       :for c :across input
       :for upcase := (char= c #\_) :then (or upcase (char= c #\_)) :do
       (cond
         ((char= c #\_))
         (upcase (write-char (char-upcase c) s) (setf upcase nil))
         (t (write-char c s))))))

string - Lisp performance optimal solution in string processing

4 回答 4

Related

Reference