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

• 資深大佬 : Chingim

  每个字符肯定都要处理一遍, 所以 O(n) 的时间复杂度少不了

• 資深大佬 : fengtons

  通过 ascii 码判断并加减完成转换？

• 資深大佬 : rigortek

  正则表达式

• 資深大佬 : ahhui

  ascii 码，一遍循环，<x 的话+x，>x 的话-x，很容易。查下 ascii table 就知道 x 是几了

• 主 資深大佬 : GDC

  @rigortek 也想过正则，没想明白怎么整，能详细点吗

• 資深大佬 : Mithril

  如果是兼容 ASCII 编码的字符串直接位运算就可以。

• 資深大佬 : KentY

  我会用 ascii code 的方法. 有兴趣可以看看 vim 实现的”~”

• 主 資深大佬 : GDC

  @Mithril 都是 ASCII 编码，就是 base64 后的字符

• 資深大佬 : ysc3839

  应该没有了，用普通的方法，编译器会优化好的。
  https://www.programmingsimplified.com/c/program/c-program-change-case

  不过刚刚在 https://godbolt.org/ 试了一下，用 ctype.h 的 isupper islower toupper tolower，编译出来并没有内联，而是 call 这几个函数。觉得 call 影响性能的话还是直接写判断和加减比较好。

• 資深大佬 : tonytonychopper

  用啥方法都是 O(n)，而且像上说到，编译器会优化。

• 資深大佬 : 52coder

  @ysc3839 赞同，使用 c 库里的 isupper 等函数没内联暂开的话，可以手写函数 inline，毕竟就判断个 ascii 码范围，应该可以实现内联。

• 資深大佬 : JerryCha

  那么有没有什么办法能保证每个字符都遍历到且时间复杂度小于 O(n)呢（比如说 O(logn)）

• 資深大佬 : Mithril

  大写字符是 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

  希腊字母？
  带 accent/umlaut 的字母？
  不知道 tr 能不能做。至少 vim 里的~可以完美转换。

• 資深大佬 : wangyzj

  ascii 吧

• 資深大佬 : Believer

  ascii table

• 資深大佬 : Bromine0x23

  @JerryCha 每个字符都遍历到 ≡ 时间复杂度至少是 O(n)

• 資深大佬 : zhx1991

  ?

  需要遍历就是 O(n) 的

• 資深大佬 : msg7086

  你都说了遍历了，比 O n 小的是跳着历。
  @JerryCha

• 資深大佬 : imn1

  位运算
  if (ch & 32)
  ch = ch & 223
  else
  ch = ch | 225

• 資深大佬 : demos

  可以按 4 字节来遍历，就可以 O(n-4)了

  <img alt=”” src=”https://i.loli.net/2020/01/29/4lLg63t1eAhy7qT.png”>

• 資深大佬 : crab

  判断范围然后异或 0x20

• 資深大佬 : ericgui

  hashmap ？提前搞好对应关系？

• 資深大佬 : augustheart

  最快的方法就只有遍历字符判断这一种。如果要进一步优化，用查表应该比 if 快一丁点，但是不会有多显著

• 資深大佬 : icyalala

  即使都是 O(n), 效率也会相差甚远。
  尤其是带分支的来判断范围的，在输入是混合符号的情况下，分支预测失败会导致效率会降低好几倍。

  查表+unrolling 是我能想到最快的。

• 資深大佬 : Windsooon

  1. 如果可以使用额外空间的话，先建立大小写字母的对应哈希表，然后遍历替换。空间复杂度是常量，时间复杂度是 O(n)，n 为字符串长度。
  2. 如果不能使用额外空间的话，可以先实现两个辅助函数，一个将大写字母转成小写字母，一个将小写字母转成大写字母。然后遍历字符串，先判断是大写还是小写，然后调用对应的函数。

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

  1. 假设存在这样的算法，不需要遍历所有字符串即可完成替换。
  2. 设立目标字符串 A，选定其中一个字符 a 为此算法无需遍历的。将 a 的大小写翻转，得到新字符串 A’
  3. 因为算法没有遍历 a，所以算法对 A 与 A’得到的结果应该是一样的，不符合实际情况。
  4. 所以不存在这样的算法。

• 資深大佬 : inhzus

  @Windsooon 什么哈希函数能比 comp，add/min 的速度更快…

• 資深大佬 : Windsooon

  @inhzus 我表达得不够准确，在这个题目下方法 2 会比方法 1 快，因为只需要一次比较和一次加减。

• 資深大佬 : 2exploring

  自定义 ascii table，把其中大写和小写字母位置换一下，其余的和标准 ascii table 一样。转的时候直接用字符当下标访问自定义的 ascii table 就是转换后的值。

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

  这个方法稍微改一下还可以用于 utf-8 编码的文本。这次自定义的表不是存 ascii 字符了，而是在大小写字母的位置放 0x20，其他位置放 0，操件由直接赋值改为异或后赋值（在许多机器上 a ^= b 和 a = b 的执行效率是一样的），原理上面有提到了。

• 資深大佬 : 2exploring

  @Windsooon 你确定一次比较就能知道是大小写？

• 資深大佬 : 2exploring

  @inhzus 你看我上面说的法子够快吗？不要把 hash 想复杂了，其实就是一个函数映射关系，这个问题里输入值是有限的，且连续的，且数量不大的，这种情况提前打个表，还要多简单。

• 資深大佬 : flyoungstudio

  Shell：
  echo abcXYZhello123 | tr [a-z] [A-Z]

• 資深大佬 : alphatoad

  遇事不决，fpga

• 資深大佬 : luozic

  全部是英文和数字，遍历一次需要 O(n)。有啥方法不用遍历再转换？

• 資深大佬 : nvkou

  抛砖引玉。像这种上下文无关的任务可以显卡并行化处理。不过脱离 php 范畴了。

• 資深大佬 : msaionyc

  @JerryCha 遍历操作的时间复杂度是不可能小于 O(n)的

• 資深大佬 : ts8zs

  直接加个网页字体…