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

[GDC]

例如，输入 abcXYZhello123 输出 ABCxyzHELLO123 ；

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

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

不限语言，最好是 php 或 js 的，仅仅提供思路讨论也行。

[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]

直接加个网页字体...