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

yxp · 发表于 2018-4-13 19:32:49

本帖最后由 yxp 于 2020-7-1 21:19 编辑

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

VL函数实现的 SPLIT

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

函数1

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

函数2

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

以上函数算法基本相同：即用 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 函数如下：

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

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

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

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

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

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

运行结果：
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 · 发表于 2018-4-14 08:21:19

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

vectra · 发表于 2018-4-13 21:51:30

EASY!

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

(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 · 发表于 2018-4-13 22:05:55

本帖最后由 yxp 于 2020-7-1 05:14 编辑

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

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

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

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

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

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

vectra · 发表于 2018-4-13 20:13:34

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

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

下面是测试结果

_$ (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 · 发表于 2018-4-13 20:16:20

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

vectra · 发表于 2018-4-13 22:22:02

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

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

stoyer · 发表于 2018-4-13 22:49:17

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

pengfei2010 · 发表于 2018-4-14 08:28:38

(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 · 发表于 2018-4-14 08:46:57

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

账号		自动登录	找回密码
密码			注册

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

评分

本帖被以下淘专辑推荐:

评分

点评

评分

点评

点评

点评

评分

点评