如何生成一段Typoglycemia文本（解答）
2012-11-11 23:40 by 老赵, 3848 visits关于“生成Tygolycemia文本”这个问题，已经有许多同学给了答案。不过，似乎大部分同学都只是以“完成”作为目标，并没有在解法的效率和内存占用上做过多考虑。其实对于这种非常简单的问题，给出一个解法并没有太大意义，而是要从中获取一些经验，否则就算反复解决这类简单的问题，得到的进步依然十分有限。
我们很容易想到，解决这个问题只需要从头至尾遍历这个字符串，找到需要重排的单词，并加以处理即可，所以这题的关键在于如何控制内存的占用以及内存复制大小。我们可以举一个最经典的例子：假如我们要将M个N字节的字符串拼接为一个M * N字节的大字符串，则直接使用加号依次进行连接，则会累计开辟及复制2 * N + 3 * N + ... + (M - 1) * N，即规模在M2 * N的数据（尽管内存会被GC不断回收，但复制是绝对省不下来，而且这对GC来说也是极大负担）。但是，假如我们使用StringBuilder，并直接开辟M * N的容量，则只需要额外复制M * N的数据。更进一步，假如我们使用String.Concat(string[])来拼接字符串，则一点额外的复制操作都不需要就能得到最终的字符串。可见，完成同样的工作，占用的内存空间以及内存复制大小是天差地远的。
估计是被强调太多次的缘故，说起此类字符串操作，大部分同学都倾向于使用StringBuilder，但这真是万能的解决方案吗？其实我很多年前就做过实验（一、二、三），强调了在可以使用String.Concat的情况下，它的性能会比StringBuilder更好。StringBuilder更适合在一些动态的环境里，生成一些长度不固定的字符串。另外，很多同学都不重视StringBuilder的初始容量（同理还有List<T>的初始容量），这都是会影响性能的因素。所以，我们除了要知道StringBuilder这个东西以外，还应该知道它的适用场景，其实这些结论都很简单，完全不用死记硬背，靠常理推断即可。
就拿如今的Typoglycemia问题来说，使用一个StringBuilder并非是一个最好的选择，因为在得到初始字符串的情况下，目标字符串的长度也已经完全可以确定下来，换句话说，我们完全可以直接用一个char[]来保存内容，进行处理，并直接生成字符串，这样我们只需要一份额外的字符串空间即可。当然，用StringBuilder时也可以直接指定足够的容量以避免不断扩容，但直接将字符串转为char[]则意味着一次性的，连续的内存复制，而用StringBuilder以后便会以小段小段方式复制内存，性能高低一目了然。
用char[]进行处理还有额外的好处，便是完全无需生成小段的字符串对象。有的同学处理这个问题的时候直接就用上String.Split来拆分字符串，这其实只会对性能带来负面影响。著名的Joe Duffy最近便写了一篇文章，谈到字符串处理时别总是为了图省事，以免“将一个IO密集型应用活活变成了CPU密集型”。在这里假如我们用上了StringBuilder，即便没有动态扩容，也势必会将源字符串拆分为一小段一小段，造成额外的内存复制及GC压力。
因此，我们的代码其实大致会是这样的结构：
static string MakeTypoglycemia(string text) { var charArray = text.ToCharArray(); // 处理charArray内容 return new string(charArray); }
剩下的，便只要找准位置，并打乱即可。我这里采取的策略其实十分简单，只要设定一个下标index（初始值为0），并重复以下三步即可：
- 从当前
index开始，向后找到第一个字母，作为单词的起始位置。假如找不到字母，则表明处理完毕。 - 从当前
index开始，向后寻找单词的分隔字符（空白字符），并随时记录最后一个字母的位置lastLetterIndex（因为空白符前面可能是标点符号）。 index和lastLetterIndex之间便是需要打乱的单词。打乱后，将index设为分隔字符的下一个位置。
于是MakeTypoglycemia方法的代码便呼之欲出了：
static string MakeTypoglycemia(string text) { var charArray = text.ToCharArray(); var index = 0; do { index = FindLetter(charArray, index); if (index >= charArray.Length) break; int lastLetterIndex; var spaceIndex = FindSeparator(charArray, index + 1, out lastLetterIndex); if (lastLetterIndex - index > 2) { Shuffle(charArray, index + 1, lastLetterIndex - 1); } index = spaceIndex + 1; } while (index < charArray.Length); return new string(charArray); }
其中用到两个辅助方法FindLetter及FindSeparator，都十分简单：
static int FindLetter(char[] charArray, int startIndex) { for (var i = startIndex; i < charArray.Length; i++) { if (Char.IsLetter(charArray[i])) return i; } return charArray.Length; } static int FindSeparator(char[] charArray, int startIndex, out int lastLetterIndex) { lastLetterIndex = -1; for (var i = startIndex; i < charArray.Length; i++) { var ch = charArray[i]; if (" \t\r\n".IndexOf(ch) >= 0) return i; if (Char.IsLetter(ch)) lastLetterIndex = i; } return charArray.Length; }
这里还用到一个Shuffle方法就不多解释了，一个传统的数组随机化的实现而已，只是需要跳过非字母的字符（用于处理“couldn't”这种情况）：
static readonly Random Random = new Random(DateTime.Now.Millisecond); static void Shuffle(char[] charArray, int startIndex, int endIndex) { for (var i = startIndex; i <= endIndex; i++) { if (!Char.IsLetter(charArray[i])) continue; var index = Random.Next(startIndex, endIndex + 1); if (!Char.IsLetter(charArray[index])) continue; var temp = charArray[index]; charArray[index] = charArray[i]; charArray[i] = temp; } }
从中可以看出，其实这样一个高效的实现也可以十分清晰而简单，可以说并没有因为追求效率而引入任何复杂度。使用这种做法，我们只用了一份额外的字符串大小的内存（即一个char[]对象）便得到了目标字符串，那么我们能否把这一份额外的内存开销也省下来呢？答案是肯定的，不过这个问题我们下次再谈。
最后说个有趣的东西：假如不追求效率，并且假设输入文本完全是用空格分割的字母，这个问题还有更好玩的“一行解法”，例如：
static string MakeTypoglycemia(string text) { var random = new Random(); return String.Join("", text.Split(' ').Select(s => s.Length <= 3 ? s : s[0] + new String(s.Substring(1, s.Length - 2).OrderBy(_ => random.Next()).ToArray()) + s[s.Length - 1])); }
以上代码完全借助.NET中内置的功能，并没有增加任何辅助方法。从效率的角度来说，这种做法当然不值一提。那么，您能否估计一下，这个做法到底会产生多少额外的内存复制？假设这是一个长度为N的字符串，其中所有的单词长度都大于3，并且总共有M个单词。
我没考虑到的地方：用
split拆分字符串带来的额外内存分配，以及最后输出结果时 join 的内存分配，内存使用变成了 O(3N) 而不是理想的 O(N)（不过 Go 的内存分配大概比 .NET 的开销要小——纯属猜测）关于
shuffle有两个问题：abc/efg这种中间出现符号的需要特殊处理么……Random.Next每调用一次就生成一个随机数，所以整个程序需要生成 N 个随机数，这部分的内存占用是否需要考虑？（我写的版本里缓存了一个随机数组，但是这需要提前知道文本中最长的单词的长度）