编程珠玑笔记(4)-啊哈!算法(III)

  • 问题C
  • 给定一个英语字典,找出其中的所有变位词集合。例如,“pots”、“stop”和“tops”互为变位词,因为每一个单词都可以通过改变其他单词中字母的顺序来得到。

  • 解答
  •   我们获得的啊哈!灵光一现就是标识字典中的每一个词,使得在相同变位词类中的单词具有相同的标识。然后,将所有相同标识的单词集中在一起。这将原始的变位词问题简化为两个子问题:选择标识和集中具有相同标识的单词。对第一个问题,我们可以使用基于排序的标识:将单词中的字母按照字母表顺序排列。要解决第二个问题,我们将所有的单词按照其标识的顺序排序。
      作者在边栏中提供了变位词程序的一个实现,主要用了添加标示符的sign程序,Linux系统的文件行排序程序sort和结果输出程序squash。

      sign程序代码:

      int charcomp (char * x, char * y) { return *x - *y; }
      
      #define WORDMAX 100
      int main(void)
      {
        char word[WORDMAX], sig[WORDMAX];
        while (scanf(%s”, word) != EOF){
          strcpy (sig, word);
          qsort (sig, strlen(sig), sizeof(char), charcomp);
          printf(%s %s\n”, sig, word);
        }
        return 0;
      }
    

      squash程序代码:

      int main(void)
      {
        char word[WORDMAX], sig[WORDMAX], oldsig[WORDMAX];
        int linenum = 0;
        strcpy(oldsig, “”);
        while (scanf(%s %s”, sig, word) != EOF){
          if (strcomp(oldsig, sig) != 0 && linenum > 0)
            printf(“\n”);
          strcpy(oldsig, sig);
          linenum ++;
          printf(%s ”, word);
        }
        printf(“\n”);
        return 0;
      }
    

    调用命令:

    $ sign < dictionary | sort | squash > gramlist
    
  • 原理总结
  •   排序。 排序最显而易见的的用处是产生有序的输出,该输出既可以是系统规范要求的一部分,也可以是另一个程序(也许是一个二分搜索程序)的前期准备工作。但是在变位词问题中,排序并不是关注的焦点。排序是为了将相等的元素集中到一起。这些标识产生了另外一个排序应用:将单词内字母排序使得同一个变位词类中的单词具有标准型。通过给每条记录添加一个额外的键,并按照这些键进行排序,排序函数可以用于重新排列磁盘文件中的数据。

      二分搜索。该算法在有序表中查找元素时极为高效,并且可用于内存排序或磁盘排序。唯一的缺陷就是整个表必须已知并且事先排好序。基于该简单算法的思想在许多应用程序中都有应用。

      标识。当使用等价关系来定义类时,定义一种标识使得类中的每一项都具有相同的标识,而该类以外的其他项则没有该标识,这是很有用的。

      问题定义。本章的中心思想是问题定义的下一步:使用哪些基本操作来解决问题?

      问题解决者的观点。 优秀程序员都有点懒:他们坐下来并等待灵机一动的出现而不急于使用最开始的想法编程。当然,这必须通过在适当的时候开始写代码来加以平衡。真正的技能就在于对这个适当时候的把握,这只能来源于解决问题和反思答案所获得的经验。

      几位读者指出,既然所有的三个旋转需要的运行时间都正比于n,杂技算法的运行速度显然是求逆算法的两倍。杂技算法对数组中的每个元素仅存储和读取一次,而求逆算法需要两次。在实际的计算机上进行实验以比较两者的速度差异,特别注意内存引用位置附近的问题。(习题4)

      下图是作者在400MHz的Pentium机器上运行的三种算法50次所用平均时间,n固定为1 000 000,使旋转距离从1变化为50。其中“Juggling”是杂技算法,“反向”是求逆算法。

    循环移位算法性能

      图中反映出的最明显问题是杂技算法与块交换算法在性能上的差异,对元素的操作次数更少的杂技算法运行的平均时间竟然远高于另外两种算法,最根本的原因在于杂技算法的空间局部性不好,无法发挥高速缓存的性能。另外两种算法的空间局部性都很好,起码对元素的访问具有很强的规律性。

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注