V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
GDC
V2EX  ›  程序员

有人来讨论技术吗?如何高效的将字符串中的大小写互换?

  •  1
     
  •   GDC · 2020-01-29 21:13:18 +08:00 · 5171 次点击
    这是一个创建于 1520 天前的主题,其中的信息可能已经有所发展或是发生改变。
    例如,输入 abcXYZhello123 输出 ABCxyzHELLO123 ;

    就是把字符串中的大写全换成小写、小写全换成大写。

    除了逐个字符判断+替换,还有什么更快速高效的方法吗?

    不限语言,最好是 php 或 js 的,仅仅提供思路讨论也行。
    37 条回复    2020-01-31 13:19:47 +08:00
    Chingim
        1
    Chingim  
       2020-01-29 21:16:24 +08:00
    每个字符肯定都要处理一遍, 所以 O(n) 的时间复杂度少不了
    fengtons
        2
    fengtons  
       2020-01-29 21:16:25 +08:00 via Android
    通过 ascii 码判断并加减完成转换?
    rigortek
        3
    rigortek  
       2020-01-29 21:20:53 +08:00 via iPhone
    正则表达式
    ahhui
        4
    ahhui  
       2020-01-29 21:23:23 +08:00 via iPhone
    ascii 码,一遍循环,<x 的话+x,>x 的话-x,很容易。查下 ascii table 就知道 x 是几了
    GDC
        5
    GDC  
    OP
       2020-01-29 21:23:41 +08:00
    @rigortek 也想过正则,没想明白怎么整,能详细点吗
    Mithril
        6
    Mithril  
       2020-01-29 21:25:08 +08:00
    如果是兼容 ASCII 编码的字符串直接位运算就可以。
    KentY
        7
    KentY  
       2020-01-29 21:27:00 +08:00
    我会用 ascii code 的方法. 有兴趣可以看看 vim 实现的"~"
    GDC
        8
    GDC  
    OP
       2020-01-29 21:27:03 +08:00
    @Mithril 都是 ASCII 编码,就是 base64 后的字符
    ysc3839
        9
    ysc3839  
       2020-01-29 21:36:45 +08:00
    应该没有了,用普通的方法,编译器会优化好的。
    https://www.programmingsimplified.com/c/program/c-program-change-case

    不过刚刚在 https://godbolt.org/ 试了一下,用 ctype.h 的 isupper islower toupper tolower,编译出来并没有内联,而是 call 这几个函数。觉得 call 影响性能的话还是直接写判断和加减比较好。
    tonytonychopper
        10
    tonytonychopper  
       2020-01-29 21:42:36 +08:00
    用啥方法都是 O(n),而且像楼上说到,编译器会优化。
    52coder
        11
    52coder  
       2020-01-29 22:22:36 +08:00
    @ysc3839 赞同,使用 c 库里的 isupper 等函数没内联暂开的话,可以手写函数 inline,毕竟就判断个 ascii 码范围,应该可以实现内联。
    JerryCha
        12
    JerryCha  
       2020-01-29 22:24:44 +08:00
    那么有没有什么办法能保证每个字符都遍历到且时间复杂度小于 O(n)呢(比如说 O(logn))
    Mithril
        13
    Mithril  
       2020-01-29 22:25:34 +08:00   ❤️ 27
    大写字符是 65~90,小写是 97~112
    二进制是 0100 0001~0101 1010 和 0110 0001~0111 1010
    比如
    01010001A,变成
    01100001a

    你可以直接翻转第六位,就是异或个 0010 0000

    这个 0010 0000 在 ASCII 里面代表空格,所以你直接异或一个空格就可以。当然你得首先判断它是字符。

    ASCII 当初就是这么设计的,大小写基本都是对称的位置。
    另外虽然 ASCII 用来编码字符,但是对应数字那部分都是 0011 开头的。你把这部分 mask 掉剩下的就是字符所表示的实际数值。

    兼容的 UTF8 也是一样的。不过正常来说,你要做一个完美的大小写转换,需要先判断 culture 才行。不过简单的可以就这么直接做了。
    thedrwu
        14
    thedrwu  
       2020-01-29 23:08:04 +08:00 via Android
    希腊字母?
    带 accent/umlaut 的字母?
    不知道 tr 能不能做。至少 vim 里的~可以完美转换。
    wangyzj
        15
    wangyzj  
       2020-01-29 23:10:42 +08:00
    ascii 吧
    Believer
        16
    Believer  
       2020-01-29 23:13:40 +08:00
    ascii table
    Bromine0x23
        17
    Bromine0x23  
       2020-01-29 23:16:30 +08:00
    @JerryCha 每个字符都遍历到 ≡ 时间复杂度至少是 O(n)
    zhx1991
        18
    zhx1991  
       2020-01-29 23:27:53 +08:00
    ?

    需要遍历就是 O(n) 的
    msg7086
        19
    msg7086  
       2020-01-29 23:29:16 +08:00 via Android
    你都说了遍历了,比 O n 小的是跳着历。
    @JerryCha
    imn1
        20
    imn1  
       2020-01-29 23:45:07 +08:00
    位运算
    if (ch & 32)
    ch = ch & 223
    else
    ch = ch | 225
    demos
        21
    demos  
       2020-01-29 23:51:19 +08:00
    可以按 4 字节来遍历,就可以 O(n-4)了

    <img alt="" src="https://i.loli.net/2020/01/29/4lLg63t1eAhy7qT.png">
    crab
        22
    crab  
       2020-01-30 01:05:54 +08:00
    判断范围然后异或 0x20
    ericgui
        23
    ericgui  
       2020-01-30 06:00:15 +08:00 via Android
    hashmap ?提前搞好对应关系?
    augustheart
        24
    augustheart  
       2020-01-30 10:27:53 +08:00
    最快的方法就只有遍历字符判断这一种。如果要进一步优化,用查表应该比 if 快一丁点,但是不会有多显著
    icyalala
        25
    icyalala  
       2020-01-30 10:37:32 +08:00   ❤️ 2
    即使都是 O(n), 效率也会相差甚远。
    尤其是带分支的来判断范围的,在输入是混合符号的情况下,分支预测失败会导致效率会降低好几倍。

    查表+unrolling 是我能想到最快的。
    Windsooon
        26
    Windsooon  
       2020-01-30 10:55:40 +08:00
    1. 如果可以使用额外空间的话,先建立大小写字母的对应哈希表,然后遍历替换。空间复杂度是常量,时间复杂度是 O(n),n 为字符串长度。
    2. 如果不能使用额外空间的话,可以先实现两个辅助函数,一个将大写字母转成小写字母,一个将小写字母转成大写字母。然后遍历字符串,先判断是大写还是小写,然后调用对应的函数。

    不可能存在低于 O(n) 时间复杂度( n 为字符串长度)的方法。

    1. 假设存在这样的算法,不需要遍历所有字符串即可完成替换。
    2. 设立目标字符串 A,选定其中一个字符 a 为此算法无需遍历的。将 a 的大小写翻转,得到新字符串 A'
    3. 因为算法没有遍历 a,所以算法对 A 与 A'得到的结果应该是一样的,不符合实际情况。
    4. 所以不存在这样的算法。
    inhzus
        27
    inhzus  
       2020-01-30 11:58:19 +08:00 via Android
    @Windsooon 什么哈希函数能比 comp,add/min 的速度更快…
    Windsooon
        28
    Windsooon  
       2020-01-30 12:22:18 +08:00
    @inhzus 我表达得不够准确,在这个题目下方法 2 会比方法 1 快,因为只需要一次比较和一次加减。
    2exploring
        29
    2exploring  
       2020-01-30 12:43:25 +08:00   ❤️ 1
    自定义 ascii table,把其中大写和小写字母位置换一下,其余的和标准 ascii table 一样。转的时候直接用字符当下标访问自定义的 ascii table 就是转换后的值。

    这样不用比较,没有分支,也许会比较快,具体怎么样你要跑跑才知道。

    这个方法稍微改一下还可以用于 utf-8 编码的文本。这次自定义的表不是存 ascii 字符了,而是在大小写字母的位置放 0x20,其他位置放 0,操件由直接赋值改为异或后赋值(在许多机器上 a ^= b 和 a = b 的执行效率是一样的),原理上面有提到了。
    2exploring
        30
    2exploring  
       2020-01-30 12:44:45 +08:00
    @Windsooon 你确定一次比较就能知道是大小写?
    2exploring
        31
    2exploring  
       2020-01-30 12:56:06 +08:00
    @inhzus 你看我上面说的法子够快吗?不要把 hash 想复杂了,其实就是一个函数映射关系,这个问题里输入值是有限的,且连续的,且数量不大的,这种情况提前打个表,还要多简单。
    flyoungstudio
        32
    flyoungstudio  
       2020-01-30 13:19:00 +08:00
    Shell:
    echo abcXYZhello123 | tr [a-z] [A-Z]
    alphatoad
        33
    alphatoad  
       2020-01-30 13:25:02 +08:00 via iPhone
    遇事不决,fpga
    luozic
        34
    luozic  
       2020-01-30 13:53:39 +08:00 via iPhone
    全部是英文和数字,遍历一次需要 O(n)。有啥方法不用遍历再转换?
    nvkou
        35
    nvkou  
       2020-01-30 14:05:17 +08:00 via Android
    抛砖引玉。像这种上下文无关的任务可以显卡并行化处理。不过脱离 php 范畴了。
    msaionyc
        36
    msaionyc  
       2020-01-30 17:29:33 +08:00
    @JerryCha 遍历操作的时间复杂度是不可能小于 O(n)的
    ts8zs
        37
    ts8zs  
       2020-01-31 13:19:47 +08:00
    直接加个网页字体...
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5406 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 07:01 · PVG 15:01 · LAX 00:01 · JFK 03:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.