如何生成一段Typoglycemia文本（解答）

关于“生成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个单词。