Hello World
Spiga

如何生成一段Typoglycemia文本(解答)

2012-11-11 23:40 by 老赵, 2517 visits

关于“生成Tygolycemia文本”这个问题,已经有许多同学给了答案。不过,似乎大部分同学都只是以“完成”作为目标,并没有在解法的效率和内存占用上做过多考虑。其实对于这种非常简单的问题,给出一个解法并没有太大意义,而是要从中获取一些经验,否则就算反复解决这类简单的问题,得到的进步依然十分有限。

我们很容易想到,解决这个问题只需要从头至尾遍历这个字符串,找到需要重排的单词,并加以处理即可,所以这题的关键在于如何控制内存的占用以及内存复制大小。我们可以举一个最经典的例子:假如我们要将MN字节的字符串拼接为一个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),并重复以下三步即可:

  1. 从当前index开始,向后找到第一个字母,作为单词的起始位置。假如找不到字母,则表明处理完毕。
  2. 从当前index开始,向后寻找单词的分隔字符(空白字符),并随时记录最后一个字母的位置lastLetterIndex(因为空白符前面可能是标点符号)。
  3. indexlastLetterIndex之间便是需要打乱的单词。打乱后,将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);
}

其中用到两个辅助方法FindLetterFindSeparator,都十分简单:

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个单词。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

15 条回复

  1. iwinux
    121.33.190.*
    链接

    iwinux 2012-11-12 09:19:29

    我没考虑到的地方:用 split 拆分字符串带来的额外内存分配,以及最后输出结果时 join 的内存分配,内存使用变成了 O(3N) 而不是理想的 O(N)(不过 Go 的内存分配大概比 .NET 的开销要小——纯属猜测)

    关于 shuffle 有两个问题:

    1. abc/efg 这种中间出现符号的需要特殊处理么……
    2. Random.Next 每调用一次就生成一个随机数,所以整个程序需要生成 N 个随机数,这部分的内存占用是否需要考虑?(我写的版本里缓存了一个随机数组,但是这需要提前知道文本中最长的单词的长度)
  2. 老赵
    admin
    链接

    老赵 2012-11-12 10:55:30

    @iwinux

    话说回来,比如在Java或.NET这种环境里,内存复制是一方面,GC还有压力。GC压力比较难以估计,对象数量也会有影响,总之如果可以少些字符串就少些了,活活。

    其实我倒不是很关注shuffle的具体实现细节,当然我是保留非字母的字符位置(题目里也强调了)。此外大部分系统里Random用的是LCG随机数生成器,不占用额外(堆)内存,就是些浮点数运算罢了。

  3. SNAKE
    120.39.23.*
    链接

    SNAKE 2012-11-12 11:53:01

    当初在微博上做的和您写的相差无几,但这样做好的原因在哪我却感觉比较模糊,您这么一说就全清晰了.

  4. 原子发射器遥控器
    123.120.28.*
    链接

    原子发射器遥控器 2012-11-12 13:11:35

    这题只能考.net/java。。 ruby的字符串本来就是可变的,就没这么麻烦了。。

  5. 老赵
    admin
    链接

    老赵 2012-11-12 14:22:16

    @原子发射器遥控器

    麻烦在哪里,不就差个ToCharArray么?更何况“参数不变”是要求。

    当然这题用.NET和Java最清晰,因为每一步的内存使用都是很容易明确的。

  6. 链接

    一刀一个 2012-11-12 15:28:41

    代码看起来很舒服.

    有个问题: 关于c#性能的优化, 是纯粹依赖经验的积累, 还是可以参考哪些数据或文档?

  7. 老赵
    admin
    链接

    老赵 2012-11-12 16:22:51

    @一刀一个

    好像我判断的最多的就是“靠常理推测”,比如它用了什么样的实现方式,数据结构等等。

  8. 张洋
    123.120.53.*
    链接

    张洋 2012-11-13 22:42:45

    话说,这个问题感觉如果用lex搞也许也不错

  9. 老赵
    admin
    链接

    老赵 2012-11-14 10:39:02

    @张洋

    应该可以,但过了……还有lex是通用的,效率其实相对较低,现在相当于是ad-hoc的做法。

  10. MaskRay
    113.116.118.*
    链接

    MaskRay 2012-11-17 18:56:16

    Hi,我在你旁邊哦……你用的 shuffle 算法被稱作 Fisher-Yates shuffle。

  11. 老赵
    admin
    链接

    老赵 2012-11-18 22:17:52

    @MaskRay

    啥叫你在我旁边……

  12. 书童
    115.236.66.*
    链接

    书童 2012-11-21 13:24:25

    那么我们能否把这一份额外的内存开销也省下来呢?答案是肯定的,不过这个问题我们下次再谈。

    如果要这样我认为在unsafe环境下 获得字符指针的方式可以做得到

  13. 老赵
    admin
    链接

    老赵 2012-11-21 17:01:37

    @书童

    没错。

  14. _龙猫
    183.129.255.*
    链接

    _龙猫 2012-11-23 15:59:04

    我的实现差不多,我很欣慰啊,呵呵

  15. Dreampuf
    208.36.133.*
    链接

    Dreampuf 2012-12-05 11:45:59

    最后一个问题,应该有 M * [(N-1) * (N-1) + 2] + 1 次内存分配

    • Split -> M
    • Select ->
      • s[0] -> 1
      • new string ... -> (N-1) * (N-1)
      • s[-1] -> 1
    • String.join -> 1

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我