如何生成一段Typoglycemia文本(解答)
2012-11-11 23:40 by 老赵, 3830 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 个随机数,这部分的内存占用是否需要考虑?(我写的版本里缓存了一个随机数组,但是这需要提前知道文本中最长的单词的长度)