Split 函数用 lisp 实现的方法与效率[2020-7-1更新]

yxp

在字符串处理中，split 函数基本功能是用一个短字符串去分割一个长字符串，并返回分割后的数组。 这是最常用的一个函数，各种高级语言均支持 split，比如 vb、C#、Python、java 等，
例如： 用空格切割字符串  
(split "I Love You" " ")
返回 ("I" "Love" "You")
但遗憾的是在 Lisp 中并未包括该基础函数，本文将讨论 split 在 lisp 语言中的实现方法与效率，欢迎大家测试。


VL函数实现的 SPLIT

以下两个函数分别是明经和小东论坛里，大师们用 Lisp 函数实现的 split 方法，
其中参数为： str — 待处理的长字符串； p — 为分割关键词

函数1

1. ;;来自明经，该函数使用频率较高，互相引用频繁，原作者不详
   
2. (defun vl-split1 (str p / pa sl xn)
   
3. (setq xn (1+ (strlen p)))
   
4. (while (setq pa (vl-string-search p str))
   
5.     (setq sl (cons (substr str 1 pa) sl)
   
6.         str (substr str (+ pa xn)))
   
7. )(reverse (cons str sl))
   
8. )
   

;;来自明经，该函数使用频率较高，互相引用频繁，原作者不详<br /> (defun vl-split1 (str p / pa sl xn)<br /> (setq xn (1+ (strlen p)))<br /> (while (setq pa (vl-string-search p str))<br />     (setq sl (cons (substr str 1 pa) sl)<br />         str (substr str (+ pa xn)))<br /> )(reverse (cons str sl))<br /> )<br />

函数2

1. ;;来自小东空间， Gu_xl 的 vlstring->list
   
2. (Defun vl-split2 (str p / lst e)
   
3. (setq str (strcat str p))
   
4. (while (vl-string-search p str)
   
5.     (setq lst (append lst (list (substr str 1 (vl-string-search p str)))))
   
6.     (setq str (substr str (+ (1+ (strlen p)) (vl-string-search p str))))
   
7. )
   
8. (if lst (mapcar '(lambda (e) (vl-string-trim " " e)) lst))
   
9. )

;;来自小东空间， Gu_xl 的 vlstring->list<br /> (Defun vl-split2 (str p / lst e)<br /> (setq str (strcat str p))<br /> (while (vl-string-search p str)<br />     (setq lst (append lst (list (substr str 1 (vl-string-search p str)))))<br />     (setq str (substr str (+ (1+ (strlen p)) (vl-string-search p str))))<br /> )<br /> (if lst (mapcar '(lambda (e) (vl-string-trim " " e)) lst))<br /> )

以上函数算法基本相同：即用 vl-string-search 函数搜索字符 p 在 str 中出现的位置，再用 substr 按位置切割 str 字符串，将分割后的返回值重新组合为一个 list 表。

测试如下：

命令: (vl-split1 “I Love You” ” “) 返回 (“I” “Love” “You”)

命令: (vl-split2 “I Love You” ” “) 返回 (“I” “Love” “You”)

继续测试中文分割：

命令: (vl-plit1 “粃糠abczyx” “z”) 返回 (“? “糠abc” “yx”)

命令: (vl-plit2 “笨賏\shit” “\”) 返回 (“笨? “a” “shit”)

返回值出现了乱码，说明这两个函数对字符的处理都有 bug，需要修正。

修正后的 VL-SPLIT

经过分析，上面函数 bug 出现原因是 vl-string-search 函数造成的。该函数在处理英文字符时，按一个字节 ascii 码搜索，这是没有问题的 ，因为英文字符加上特殊字符不超过128个，这样一个字节（8bit）就可以表示完毕。但是汉字太多，需要用两个字节表示（16bit），但是 lisp 字符处理函数还是按单字节返回。例如：

命令: (vl-string->list “z”) 返回 (122)
命令: (vl-string->list “粃”) 返回 (187 122)

这并不是 lisp 的错，而是我们的代码设计不周全，没有考虑对汉字的判断。汉字GB2312编码特点是首字节 ASCII 大于 128 ，判断后如果是汉字则让分割指针跳过两个字节，修正后的 split 函数如下：

1. ;;修正后的 split
   
2. (defun vl-split3 (str p / pa sl xn f)
   
3. (setq xn (1+ (strlen p)) f 0)
   
4. (while (setq pa (vl-string-search p str f))
   
5.     (if (< (vl-string-elt str (1- pa)) 128)
   
6.         (setq sl (cons (substr str 1 pa) sl)
   
7.             str (substr str (+ pa xn)) f 0)
   
8.         (setq f (1+ pa))
   
9.     )
   
10. )(reverse (cons str sl))
    
11. )

;;修正后的 split<br /> (defun vl-split3 (str p / pa sl xn f)<br /> (setq xn (1+ (strlen p)) f 0)<br /> (while (setq pa (vl-string-search p str f))<br />     (if (< (vl-string-elt str (1- pa)) 128)<br />         (setq sl (cons (substr str 1 pa) sl)<br />             str (substr str (+ pa xn)) f 0)<br />         (setq f (1+ pa))<br />     )<br /> )(reverse (cons str sl))<br /> )

正则表达式实现的 SPLIT
提到字符处理，那是正则表达式的天下，大部分的程序设计语言都有这个字符处理的引擎。它是怎么工作的我们不管，我们只需要按照一定的规则，让它为我们服务即可。用 lisp 语言设计一个 split 函数代码如下：

1. ;;正则表达式的 split 函数   by: yxp
   
2. (defun rg-split (s p)
   
3.   (setq r (vlax-create-object "vbscript.regexp"))
   
4.   (vlax-put-property r 'Global 1)
   
5.   (vlax-put-property r 'Pattern p)
   
6.   (read (strcat "(\"" (vlax-invoke r 'Replace s "\" \"") "\")"))
   
7. )

;;正则表达式的 split 函数   by: yxp<br /> (defun rg-split (s p) <br />   (setq r (vlax-create-object "vbscript.regexp"))<br />   (vlax-put-property r 'Global 1)<br />   (vlax-put-property r 'Pattern p)<br />   (read (strcat "(\"" (vlax-invoke r 'Replace s "\" \"") "\")"))<br /> )

示例：
命令: (rg-split "粃糠abczyx" "z") 返回 ("粃糠abc" "yx") 另外，这个函数还隐含了一个强大的功能，就是支持多字符分割，用管道符将字符分开即可，例如：
命令: (rg-split "abcfarecadefge" "c|f") 返回 ("ab" "" "are" "ade" "ge")
相当于同时用 c 和 f 去分割。

SPLIT 效率测试对比
虽然计算机的运算处理能力在不断进步，但是 lisp 的低效率有时候让人无法忍受。我们用以下程序来对比测试一下自定义 split 和 正则 split 函数的分割效率。

1. ;; split 分割效率测试
   
2. (defun c:test( / i AA)
   
3. (setq i 0 AA "")
   
4. (while (< i 100000) (setq AA (strcat AA (itoa (setq i (1+ i))) ",")))
   
5. (setq time0 (getvar "date"))
   
6. (vl-split3 AA ",") ;;调用 VL 函数
   
7. (setq time1 (getvar "date"))
   
8. (rg-split AA ",")  ;;调用正则函数
   
9. (setq time2 (getvar "date"))
   
10. (princ (strcat "\nvl-split 函数耗时: " (rtos (* 86400 (- time1 time0)) 2 4) " 秒"))
    
11. (princ (strcat "\nrg-split 函数耗时: " (rtos (* 86400 (- time2 time1)) 2 4) " 秒"))
    
12. (princ)
    
13. )

;; split 分割效率测试<br /> (defun c:test( / i AA)<br /> (setq i 0 AA "")<br /> (while (< i 100000) (setq AA (strcat AA (itoa (setq i (1+ i))) ",")))<br /> (setq time0 (getvar "date"))<br /> (vl-split3 AA ",") ;;调用 VL 函数<br /> (setq time1 (getvar "date"))<br /> (rg-split AA ",")  ;;调用正则函数<br /> (setq time2 (getvar "date"))<br /> (princ (strcat "\nvl-split 函数耗时: " (rtos (* 86400 (- time1 time0)) 2 4) " 秒"))<br /> (princ (strcat "\nrg-split 函数耗时: " (rtos (* 86400 (- time2 time1)) 2 4) " 秒"))<br /> (princ)<br /> )

运行结果：
vl-split 函数耗时: 28.615 秒 ， 二楼 vectra 兄的 p-string-tokenize-m 程序我测试为 0.468 秒
rg-split 函数耗时: 0.047 秒

唯一需要注意的是，在 AutoLisp 和 正则表达式中，不约而同的定义 “\” 为转义字符，所以如果要以单字符“\” 为切割字符，应该用四个 “\\” 来表示，第一次转义为 CAD 字符，第二次转义为正则字符。
例如下面表示是错误的：
命令: (Split "笨贼\\shit" "\")
分割字符为单个斜杠是不行的，需要用四个斜杠表示，这样才是正确的：
命令: (Split "笨贼\\shit" "\\\\")

本文为作者原创，转载请注明出处。 https://blog.csdn.net/yxp_xa/article/details/72636232

pengfei2010

楼主你好：
首先 我想说的是，正则表达式是用来出来复杂问题的，你这样用有点杀鸡用牛刀了！
第二 您的测试方法不对的，没有人会有这么长度字符串(100000长度)需要解析，你应该调用正则表达式100000次测试才对，单次测试正则表达式有一点优势很正常的，就比如你调用command删除10万的对象就比lisp删除10万个对象快一些，但是你要是调用10万次command的erase命令来删除对象，你慢慢等半小时吧！
第三 我的测试结果，分解(setq str "Hello 2World 12 5456.1568" va " ") 这个参数，调用lisp函数一万次需要0.11秒，调用您的正则表达式1万次需要4秒，相差30多倍！

vectra

EASY!

1. (defun p-string-tokenize-m (str delim / buff l2)
   
2.   (setq        str   (vl-string->list str)
   
3.         delim (vl-string->list delim)
   
4.   )
   
5.   (while str
   
6.     (if        (member (car str) delim)
   
7.       (setq l2         (cons (vl-list->string (reverse buff)) l2)
   
8.             buff nil
   
9.       )
   
10.       (setq buff (cons (car str) buff))
    
11.     )
    
12.     (setq str (cdr str))
    
13.   )
    
14.   (setq l2 (cons (vl-list->string (reverse buff)) l2))
    
15.   (reverse l2)
    
16. )

(defun p-string-tokenize-m (str delim / buff l2)<br />   (setq        str   (vl-string->list str)<br />         delim (vl-string->list delim)<br />   )<br />   (while str<br />     (if        (member (car str) delim)<br />       (setq l2         (cons (vl-list->string (reverse buff)) l2)<br />             buff nil<br />       )<br />       (setq buff (cons (car str) buff))<br />     )<br />     (setq str (cdr str))<br />   )<br />   (setq l2 (cons (vl-list->string (reverse buff)) l2))<br />   (reverse l2)<br /> )

(setq i         0
      AA ""
)
(while (< i 40000)
  (setq AA (strcat AA (itoa (setq i (1+ i))) ","))
  (setq AA (strcat AA (itoa (setq i (1+ i))) " "))
)

_$ (p-benchmark '(p-string-tokenize-m aa ", ") 1)
"Benchmark loops = 1, in 219 ms, 5 invoke / s"

效率依旧是最高的 专用的代码快过正则应无悬念

yxp

vectra 发表于 2018-4-13 21:51
EASY!

奇怪了，我测试的结果，还是正则最快，大约快十倍。

自定义 VL 函数耗时: 0.464 秒
正则 split 函数耗时: 0.049 秒

哪位同学也来测试一下， 运行下面 test 即可。（创建10万长度的 list 测试表需要十秒左右）

1. ;;by: vectra
   
2. (defun p-string-tokenize-m (str delim / buff l2)
   
3. (setq str (vl-string->list str)
   
4.         delim (vl-string->list delim))
   
5. (while str
   
6.         (if (member (car str) delim)
   
7.                 (setq l2 (cons (vl-list->string (reverse buff)) l2) buff nil)
   
8.                 (setq buff (cons (car str) buff))
   
9.     )
   
10.         (setq str (cdr str))
    
11. )
    
12.         (setq l2 (cons (vl-list->string (reverse buff)) l2))
    
13.         (reverse l2)
    
14. )
    
15. 
    
16. ;;by: yxp
    
17. (defun Split (s p / L r)
    
18.   (setq r (vlax-create-object "vbscript.regexp"))
    
19.   (vlax-put-property r 'Global 1)
    
20.   (vlax-put-property r 'Pattern p)
    
21.   (read (strcat "(\"" (vlax-invoke r 'Replace s "\" \"") "\")"))
    
22. )
    
23. 
    
24. (defun c:test( / i AA)
    
25. (setq i 0 AA "")
    
26. (while (< i 100000) (setq AA (strcat AA (itoa (setq i (1+ i))) "-,")))
    
27. (setq time0 (getvar "date"))  ;;开始计时
    
28. (p-string-tokenize-m AA "-,") ;;调用 lisp-split 函数
    
29. (setq time1 (getvar "date"))
    
30. (Split AA "-,")  ;;调用正则 split 函数
    
31. (setq time2 (getvar "date"))
    
32. (princ (strcat "\nLisp-split 函数耗时: " (rtos (* 86400 (- time1 time0)) 2 4) " 秒"))
    
33. (princ (strcat "\n正则 split 函数耗时: " (rtos (* 86400 (- time2 time1)) 2 4) " 秒"))
    
34. (princ)
    
35. )
    

;;by: vectra<br /> (defun p-string-tokenize-m (str delim / buff l2)<br /> (setq str (vl-string->list str)<br />         delim (vl-string->list delim))<br /> (while str<br />         (if (member (car str) delim)<br />                 (setq l2 (cons (vl-list->string (reverse buff)) l2) buff nil)<br />                 (setq buff (cons (car str) buff))<br />     )<br />         (setq str (cdr str))<br /> )<br />         (setq l2 (cons (vl-list->string (reverse buff)) l2))<br />         (reverse l2)<br /> )<br /> <br /> ;;by: yxp<br /> (defun Split (s p / L r) <br />   (setq r (vlax-create-object "vbscript.regexp"))<br />   (vlax-put-property r 'Global 1)<br />   (vlax-put-property r 'Pattern p)<br />   (read (strcat "(\"" (vlax-invoke r 'Replace s "\" \"") "\")"))<br /> )<br /> <br /> (defun c:test( / i AA)<br /> (setq i 0 AA "")<br /> (while (< i 100000) (setq AA (strcat AA (itoa (setq i (1+ i))) "-,")))<br /> (setq time0 (getvar "date"))  ;;开始计时<br /> (p-string-tokenize-m AA "-,") ;;调用 lisp-split 函数<br /> (setq time1 (getvar "date"))<br /> (Split AA "-,")  ;;调用正则 split 函数<br /> (setq time2 (getvar "date"))<br /> (princ (strcat "\nLisp-split 函数耗时: " (rtos (* 86400 (- time1 time0)) 2 4) " 秒"))<br /> (princ (strcat "\n正则 split 函数耗时: " (rtos (* 86400 (- time2 time1)) 2 4) " 秒"))<br /> (princ)<br /> )<br />

vectra

借楼主的话题 顺便测试了一下我自己写的split代码 ，发现还是list操作的效率最高

1. (defun p-string-tokenize (str delim / buff l2)
   
2.   (setq        str   (vl-string->list str)
   
3.         delim (ascii delim)
   
4.   )
   
5.   (while str
   
6.     (if        (= (car str) delim)
   
7. ;;;      (if buff
   
8.       (setq l2         (cons (vl-list->string (reverse buff)) l2)
   
9.             buff nil
   
10.       )
    
11. ;;;      )
    
12.       (setq buff (cons (car str) buff))
    
13.     )
    
14.     (setq str (cdr str))
    
15.   )
    
16. ;;;  (if buff
    
17.   (setq l2 (cons (vl-list->string (reverse buff)) l2))
    
18. ;;;  )
    
19.   (reverse l2)
    
20. )

(defun p-string-tokenize (str delim / buff l2)<br />   (setq        str   (vl-string->list str)<br />         delim (ascii delim)<br />   )<br />   (while str<br />     (if        (= (car str) delim)<br /> ;;;      (if buff<br />       (setq l2         (cons (vl-list->string (reverse buff)) l2)<br />             buff nil<br />       )<br /> ;;;      )<br />       (setq buff (cons (car str) buff))<br />     )<br />     (setq str (cdr str))<br />   )<br /> ;;;  (if buff<br />   (setq l2 (cons (vl-list->string (reverse buff)) l2))<br /> ;;;  )<br />   (reverse l2)<br /> )

下面是测试结果

_$ (p-benchmark '(p-string-tokenize aa ",") 1)
"Benchmark loops = 1, in 326 ms, 3 invoke / s"
_$ (p-benchmark '(Split AA ",") 1)
"Benchmark loops = 1, in 1500 ms, 1 invoke / s"
_$ (p-benchmark '(Split3 AA ",") 1)
"Benchmark loops = 1, in 17969 ms, 0 invoke / s"

vectra

顺便说一下测试用的字符串大概是46K字节
_$ (strlen aa)
461196

vectra

欢迎大家来评测 需要指出的是两个函数返回的结果是有差异的，如下
_$ (p-string-tokenize-m AA "-,")
("1" "" "2" "" "3" "" "4" "" "5" ""...
_$ (Split AA "-,")
("1" "2" "3" "4" "5" "6" "7" "8" ...

按道理 连续分隔符之间的空白字符应该需要返回

stoyer

这是个高质量的帖子哦，学习了。。

pengfei2010

(Split "Hello,a,2World,a,12,a,5456. 1568" "a,") => '("Hello" "2World" "12" "5456. 1568")
(Str2StrL* "Hello,a,2World,a,12,a,5456. 1568" "a,") => '("Hello," "2World," "12," "5456. 1568")

第一个是您的正则来解析，第二个是我的子函数，显然，用你的正则表达式结果还不对的

zixuan203344

小蜜蜂这是把博客里面的都搬过来了啊