切分字符串的方法

By yanying at 2018-03-15 • 0人收藏 • 955人看过

想问下大家,chez scheme的库里面,是不是没有切分字符串的函数?我试了好像都不行的。比如以空格为分割切分,`"aa bc e f".split(" ")`。


https://stackoverflow.com/questions/7691769/string-split-function


另想请问一下, 除了

https://www.scheme.com/tspl4/objects.html#./objects:h8

https://cisco.github.io/ChezScheme/csug9.5/objects.html#./objects:h4

http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_sec_11.12

还有什么chez scheme内置的库函数完整api文档可用,方便索引查找的网站,

就像http://ruby-doc.org/core-2.5.0/String.html一样的。

42 个回复 | 最后更新于 9 小时前
2018-03-15   #1
(define split
    (lambda (s c)
        (let loop ((s s))
            (define str-index
                (lambda (s c)
                    (let ((n (string-length s)))
                        (let loop ((i 0))
                            (cond 
                                ((>= i n) #f)
                                ((char=? (string-ref s i) c) i)
                                (else (loop (+ i 1))))))))
            (if (string=? s "")
                '()
                (let ((i (str-index s c)))
                    (if i
                        (cons (substring s 0 i) (loop (substring s (+ i 1) (string-length s))))
                        (list s)))))))

自己写就行了啊

2018-03-15   #2

srfi 或者slib ,用 irrregex 也行


2018-03-20   #3

回复#2 @chui :


已经养成什么轮子都自己造的坏习惯了

2018-03-20   #4

回复#3 @theschemer :

scheme程序员的坎

2018-03-21   #5

这样的话,我觉得我们可以开始去建立一些第三方的扩展库了,仅仅作为社区而言,这好像也很有必要的。


@chui @theschemer

2018-03-21   #6

回复#5 @yanying :

很好的想法,可以开个新的帖子探讨下

2018-03-31   #7

这个split比起上面的更加高效。

(define (split s c)
  (letrec ((walk (lambda (str)
                   (cond ((string=? str "")  (values "" '()))
                         ((char=? (string-ref str 0) c) (let-values (((a b) (walk (substring str 1))))
                                                          (values ""
                                                                  (cons a b))))
                         (else (let-values (((a b) (walk (substring str 1))))
                                 (values (string-append (substring str 0 1)
                                                        a)
                                         b)))))))
    (let-values (((a b)
                  (walk s)))
      (cons a b))))


2018-03-31   #8

回复#7 @fold :

我看一下


(社区这样的探讨氛围真的很好)

2018-03-31   #9

回复#7 @fold :

你这个是racket吧?chez 中要指明substring 的end

(walk (substring str 1 (string-length str))


2018-03-31   #10

回复#7 @fold :

(define (split s c)
  (letrec* ([len (string-length s)]
            [walk (lambda (str begin end rst)
                    (cond ((= begin len) rst)
                          ((char=? (string-ref str end) c)
                            (walk
                              str 
                              (+ end 1)
                              (+ end 1)
                              (if (= begin end) 
                                rst
                                (cons (substring str begin end) rst))))
                          (else
                            (walk str begin (+ end 1) rst))))])
    (reverse (walk s 0 0 '()))))

这样看起来会好看点

2018-03-31   #11

回复#7 @fold :

你这个思路没问题 但是写法有问题 


速度比我那个慢了4倍


楼上 Chui用你的思路重写了一个 比我的快一倍

2018-03-31   #12

回复#7 @fold :

3种写法速度评测

1是chui的写法,2是fold的,3是theschemer的

Chez Scheme Version 9.5
Copyright 1984-2017 Cisco Systems, Inc.

> (load "test.ss")
> (time (test split1))
(time (test split1))
    323 collections
    1.468750000s elapsed cpu time, including 0.000000000s collecting
    1.471482220s elapsed real time, including 0.011332840s collecting
    2720206784 bytes allocated, including 2719567136 bytes reclaimed
> (time (test split2))
(time (test split2))
    1862 collections
    10.953125000s elapsed cpu time, including 0.140625000s collecting
    11.194385885s elapsed real time, including 0.067666447s collecting
    15681191680 bytes allocated, including 15677479840 bytes reclaimed
> (time (test split3))
(time (test split3))
    514 collections
    2.718750000s elapsed cpu time, including 0.000000000s collecting
    2.769565483s elapsed real time, including 0.017467315s collecting
    4320328960 bytes allocated, including 4326452800 bytes reclaimed

测试方法为运行10000000次函数

(define (test fun)
    (let loop ([end 10000000])
        (when (> end 0)
        (fun "1abcd1efg1hij1klmn1" #\1)
        (loop (- end 1))
        )
    )
)


2018-04-01   #13

@chui


你这个不能通过Igropyr的测试

Chez Scheme Version 9.5
Copyright 1984-2017 Cisco Systems, Inc.

> (define (split s c)
    (letrec* ([len (string-length s)]
              [walk (lambda (str begin end rst)
                      (cond ((= begin len) rst)
                            ((char=? (string-ref str end) c)
                              (walk
                                str 
                                (+ end 1)
                                (+ end 1)
                                (if (= begin end) 
                                  rst
                                  (cons (substring str begin end) rst))))
                            (else
                              (walk str begin (+ end 1) rst))))])
      (reverse (walk s 0 0 '()))))
> (split "user=igropyr&psw=catapult" #\&)
Exception in string-ref: 25 is not a valid index for "user=igropyr&psw=catapult"
Type (debug) to enter the debugger.
>


2018-04-01   #14

回复#13 @theschemer :

少加一个边界判断

(define (split1 s c)
  (letrec* ([len (string-length s)]
            [walk (lambda (str begin end rst)
                    (cond ((>= begin len) rst)
                          ((or (= end len) (char=? (string-ref str end) c))
                            (walk
                              str 
                              (+ end 1)
                              (+ end 1)
                              (if (= begin end) 
                                rst
                                (cons (substring str begin end) rst))))
                          (else
                            (walk str begin (+ end 1) rst))))])
    (reverse (walk s 0 0 '()))))


2018-04-01   #15

(define (split2 s c)
  (letrec ((walk (lambda (begin end)
                   (cond ((= begin end)  (values 0 '()))
                         ((char=? (string-ref s begin) c) (let-values (((a b) (walk (+ begin 1) end)))
                                                            (values 0
                                                                    (cons (substring s (+ begin 1) (+ 1 a begin)) b))))
                         (else (let-values (((a b) (walk (+ begin 1) end)))
                                 (values (+ a 1)
                                         b)))))))
    (let-values (((a b)
                  (walk 0 (string-length s))))
      (cons (substring s 0 a) b))))


我认为之前造成效率低下的原因是因为substring和string-append的滥用,新的split2拥有与split1相近的速度,另外当字符串很长的时候,我发现split3的速度变得很慢。

2018-04-01   #16

回复#15 @fold :

split3 慢在于遍历多次


split2 慢在于重复分配空间

2018-04-15   #17
 (define (string-split str separator)
                (let f ((i 0) (n (string-length str)))
                  (cond
                    ((= i n) (list (substring str 0 n) ))
                    ((char=? (string-ref str i) separator)
                       (cons (substring str 0 i)
                             (string-split (substring str (+ i 1) n) separator)))
                    (else (f (+ i 1) n)))))
2018-04-23   #18

其实,我想发散这个问题来探讨。


我觉得,如果我们要实现切分字符串的话,从实现库上来说,切分符参数是字符串的意义比较大。我是说,比如支持`(string-split str "for:")`这样形式的切分。虽然明显,这样处理起来逻辑会复杂一些。这样的话,就要取切分符的第一个字符进行比较,如果匹配到的话,继续比较匹配到的字符之后的几位字符,确认其是否和匹配符的之后几位相匹配。

2018-09-10   #19

回复#17 @evilbinary :

来来来 测一下


2018-10-12   #20
(define (string-split str sep)
  (let f ([res '()]
          [j (string-length str)]
          [i (sub1 (string-length str))])
    (if (= i -1)
        (cons (substring str 0 j) res)
        (if (char=? (string-ref str i) sep)
            (f (cons (substring str (add1 i) j) res)
               i
               (- i 1))
            (f res j (- i 1))))))

使用尾递归。

27 天前   #21

回复#18 @yanying :

Core 里 已经有了


https://github.com/guenchi/Core/blob/master/core/string.sc

27 天前   #22

速度评测来了


split1:1楼 guenchi (书上抄来的)

split2:7楼 fold

split3:10楼 chui (改写的fold版)

split4:15楼 fold (重写版)

split5:17楼 evelbinairy

split6:20楼 qzivil (尾递归版)

split7:24楼 xaengceilbiths (变态版)

split8:30楼 fold (超长版)


以下是测试结果


(time (loop split1 ...))

    571 collections

    2.607045201s elapsed cpu time, including 0.012222077s collecting

    2.608161000s elapsed real time, including 0.013427000s collecting

    4804845840 bytes allocated, including 4810955296 bytes reclaimed

(time (loop split2 ...))

    1621 collections

    7.689033621s elapsed cpu time, including 0.134644397s collecting

    7.691425000s elapsed real time, including 0.138589000s collecting

    13663043504 bytes allocated, including 13656144768 bytes reclaimed

(time (loop split3 ...))

    18 collections

    0.072333043s elapsed cpu time, including 0.000503266s collecting

    0.072353000s elapsed real time, including 0.000551000s collecting

    150426560 bytes allocated, including 153078176 bytes reclaimed

(time (loop split4 ...))

    12 collections

    0.083133952s elapsed cpu time, including 0.000340520s collecting

    0.083135000s elapsed real time, including 0.000377000s collecting

    104178096 bytes allocated, including 102046496 bytes reclaimed

(time (loop split5 ...))

    571 collections

    2.586030931s elapsed cpu time, including 0.012812409s collecting

    2.587383000s elapsed real time, including 0.014040000s collecting

    4805005856 bytes allocated, including 4813108032 bytes reclaimed

(time (loop split6 ...))

    12 collections

    0.055051141s elapsed cpu time, including 0.000407468s collecting

    0.055067000s elapsed real time, including 0.000449000s collecting

    104018080 bytes allocated, including 101073936 bytes reclaimed

(time (loop split7 ...))

    34 collections

    0.122367700s elapsed cpu time, including 0.000850015s collecting

    0.122398000s elapsed real time, including 0.000948000s collecting

    281329888 bytes allocated, including 286530384 bytes reclaimed

(time (loop split8 ...))

    13 collections

    0.056775109s elapsed cpu time, including 0.000328636s collecting

    0.056864000s elapsed real time, including 0.000374000s collecting

    104338752 bytes allocated, including 109542640 bytes reclaimed




速度排名 (与第一名的耗时倍数)


split6 (1)

split8 (1.03)

split3 (1.3)

split4 (1.5)

split7 (2.2)

split5 (47) 

split1(47)

split2(139)



@qzivil: 恭喜获得第一!

@evelbinairy:鸭子你装逼被打脸了吧...


27 天前   #23
(define split
    (lambda (s c)
        (define x (string-length s))
        (let l ((x x)(y (- x 1))(r '()))
            (if (= y -1)
                (cons (substring s 0 x) r)
                (if (char=? (string-ref s y) c)
                    (l y (- y 1)(cons (substring s (+ y 1) x) r))
                    (l x (- y 1) r))))))


split6的改进版 比split6稍微快那么一丢丢

26 天前   #24

回复#23 @guenchi :

变态多线程版

(define (split s c)
  (let* ([l (string-length s)]
         [f (lambda (b a) (substring s (+ 1 a) b))]
         [il (filter (lambda (i) (char=? (string-ref s i) c)) (iota l))])
    (set-cdr! (last-pair il) (list l))
    (cons (substring s 0 (car il)) (#3%map f (cdr il) il))))


登录后方可回帖

登 录
信息栏

Scheme中文社区

推荐实现 ChezScheme / r6rs / r7rs large
theschemer.org
Q群: 724577239

精华导览

社区项目

包管理器:Raven
HTTP服务器:Igropyr (希腊火)
官方插件:vscode-chez

社区目标:

完善足以使Scheme工程化和商业化的库,特别是开发极致速度的Web服务器和ANN模块。

一直以来Scheme缺少一个活跃的中文社区,同时中文资料的稀少,导致大多数因为黑客与画家和SICP而接触Scheme的朋友,在学完SICP后无事可做,不能将Scheme转换为实际的生产力。最后渐渐的放弃。
同时Chicken等实现,却因效率问题无法与其他语言竞争。本社区只有一个目的,传播Scheme的文明之火,在最快的编译器实现上,集众人之力发展出足够与其他语言竞争的社区和库。


友情链接:

Clojure 中文论坛
函数式·China


Loading...