33.00s和14.27s，两个截然不同的运行时间值，两次提交尝试解决素数回文问题，终于搞定了！用两个字形容’恼人’！算法不复杂，就是要求时间很’紧’，大部分工作都在考虑着如何缩短运行时间。桃花在冷空气袭来的日子都开了，我的心也算可以放下了！

最近项目吃紧，连续两天没有做ACM习题了，手都有些生了^_^！按照Volume1的习题顺序，该轮到1004题了！这是一道关于’素数回文(Prime Palindromes)’的习题，源自’USACO’，估计是什么比赛吧！大家一定都知道什么是素数，或者又叫质数！那么什么是回文(Palindromes)，不用定义，举几个例子大家就明白了，如121、1331、14741、89098等等看起来对称的数都叫做回文数，具体的定义或者数学上的定义我也没找到，好像对解决此题关系也不大！

Ok!我们来看一下题目，题目很简单，找出输入的两个数之间的所有素数回文，并按照数值顺序输出，每行一个数！要求：运行时间在15秒以内。输入值范围[5, 1000000000]。

如果不估计时间，大家脑中一定选中了’遍历’这种方案，而达到目标前所要解决的两个问题包括如何判断一个数是否是一个素数和如何判断一个数是否为一个回文数？

如何判断素数？这个在大学学习C语言的时候好像是习题，不过算法早已经忘到了’九霄云外’，这样自己就顺手写了一个宏：
#define IS_PRIMER(i) \
        ((i <= 10) \
         ? (i == 2 || i == 3 || i == 5 || i == 7) \
         : (((i % 2 == 0) || (i % 3 == 0) || (i % 5 == 0) || ( i % 7 == 0)) ? 0 : 1))
用几个数测了一下，屡试不爽！为了更加精确的测试，还是到网上找一个素数表吧！这样有参照的测试势必比较准确无误。试着用这个宏找出500以内的所有素数，发现与素数表中的个数不符，仔细查查，一眼就看到了121这个数，按照我的算法，它就是个’素数’了，但实际上它还能被11所整除，别忘了素数的定义："不能被1和自己之外的任何数整除"，看来我的算法是’漏洞百出’，不过在100之内它是有效的，起码算是个’Uncompleted Algorithm’^_^。重新修整一下，改进版如下：
int is_primer(int x) {
        int i;
        for (i = 2; i <= sqrt(x); ++i) {
                if (x % i == 0) {
                        return 0;
                }
        }
        return 1;
}
这种算法也是网上常见的算法，如果和外层的遍历一起来看，这是个接近O(n^2)的算法，显然性能不高！不过目前还少有好算法公布在网上，就暂用这个吧，我也想不出来什么好方法！也许需要好的数学功底才能提高该算法性能！

如何判断回文？这就是个’见仁见智’的问题了。这里提供两种方案，感觉性能上差不多，各有千秋：
[方案一]
/* 获取一个数i的位数n */
#define GET_DIGITS(n, i) do { \
                n = 1; \
                while (i >= pow(10, n)) { \
                        n++; \
                } \
        } while(0)

/*
 * 从外到内，比较每一个对称位上的数值是否相等
 * 如果全相等则是回文，否则不是。
 *
 * ! 这种方法还是很容易想出来的
 */
int is_palindrome(int x) {
        int     i = 0;
        int     j = 0;
        int     n = 0;

        int     high = 0;
        int     low = 0;

        GET_DIGITS(n, x);
        j = (n % 2) ? ((n-1) / 2) : (n / 2);

        for (i = 1; i <= j; ++i) {
                low = x % (int)(pow(10, i));
                high = x/(pow(10, n-i));
                if (low != high) {
                        return 0;
                }
        }
        return 1;
}

[方案二]
/*
 * ‘回文数’再造
 * 从低位到高位，按’低位 * 10 + 高位’累加的方式得到一个数
 * 如果该最终数值与原数一致，则为回文数，否则不是
 *
 * 这个方法对后面的方法还是很有启发的！
 */
int is_palindrome(int x) {
        int     rv = 0;
        int     i = x;

        while (i != 0) {
                rv = rv * 10 + i % 10;
                i = i / 10;
        }

        return rv == x;
}

现在两个难题都解决了，我们只需要遍历加判断即可。那么是先判断素数还是先判断回文呢？看起来判断素数较浪费时间，那我们先判断回文吧！第一次提交代码，不出所料，运行时间33s(我想不止33s，也许33s只是服务器的一个时间上限，大于该时间的统一显示为33s)。看来我们的重新考量一下我们的方案了！这种遍历+判断的方法无论如何是不能够蒙混过关的了^_^。

那么怎么来做呢？方案一是拿来一个数，我们来判断是否是回文，这样绝大部分的数都不是回文数，那么这些判断也都是无效的，但却占用了大量的时间，我们能不能尽量让我们每步操作都是生成结果之路上有效的一步呢？我们来尝试自己生成一定范围内的回文数。回文数组成是有一定的规律可循的。现在我们可以将问题集中在’如何生成位数为n的所有回文数’上！我们举几个例子就能看得出来：
[例子]
6446 — 我们可以看成两个部分 — 高二位的64和低二位的46互为反序数，我们也可以理解为高二位的值随着低二位的变化而变化；
64546 — 我们可以看成三个部分 — 高二位的64和低二位的46互为反序数，再加上中间的一个独立变化的值，我们也可以理解为高二位的值随着低二位的变化而变化；中间值独立变化；

可以看出我们的算法可以将处理分为两类：奇数和偶数。
1、如何生成位数为偶数位的所有回文数？
算法名称：gen_even_palindrome
输入项：n (回文数的位数)
算法步骤：
gen_even_palindrome(n) {
 j = n/2; /* j为独立变化的低位部分的位数 */
 k = (10^j – 1); /* k为独立变化的低位部分的上限值 */
 for (i = 1; i <= k; ++i) {
     /*
      * 这里的i就是低位部分独立变化的值
      */
     if (i % 10) {
      /* 如果 i = 10、1000等这些10^n的数，它们是没有回文的 */
       continue;
     }

     rv = _gen_even_palindrome(i, n); /* rv就是一个n位回文数 */
 }
}

_gen_even_palindrome(x, n) {
        int i = x;
        int j = 1;
        int rv = 0;

 /*
  * 利用低位部分的信息，造出高位部分的数值
  */
        while (i != 0) {
                rv += ((i % 10) * pow(10, n-j));
                i = i / 10;
                j++;
        }

 /* 最后的回文数还要加上低位部分的数 */
        rv += x;
        return rv;
}

2、如何生成位数为奇数位的所有回文数？
算法名称：gen_odd_palindrome
输入项：n (回文数的位数) n > 1 对n = 1作特殊处理便是
算法步骤：
gen_odd_palindrome(n) {
 j = (n + 1)/2; /* j为独立变化的低位部分的位数 *
/
 k = (10^(j-1) – 1); /* k为独立变化的低位部分的上限值 */

 for (h = 0; h <= 9; ++h) { /* 中间位独立变化 */
  for (i = 1; i <= k; ++i) {
   /*
     * 这里的i就是低位部分独立变化的值
     */
   if (i % 10) {
    /* 如果 i = 10、1000等这些10^n的数，它们是没有回文的 */
    continue;
   }

   rv = _gen_odd_palindrome(i, h, n); /* rv就是一个n位回文数 */
  }
 }
}

_gen_odd_palindrome(x, mid, n) {
        int i = x;
        int j = 1;
        int rv = 0;

 /*
  * 利用低位部分的信息，造出高位部分的数值
  */
        while (i != 0) {
                rv += ((i % 10) * pow(10, n-j));
                i = i / 10;
                j++;
        }

 /* 最后的回文数还要加上中间数和低位部分的数 */
 rv += mid * pow(10, (n-1)/2);
        rv += x;
        return rv;
}

至此，我们算是解决了如何生成回文数的问题了，不过目前还有一点不能满足，那就是按照数值顺序来输出回文素数，不知道大家发现没有，上面的回文数生成算法不能保证按照数值顺序生成会文数，所以我们还要再动动脑筋！

这里不妨尝试一下作弊！^_^ 由于回文数生成算法不能保证按照数值顺序输出回文数，那么我们势必需要记下来已经生成的回文数，那么到底有多少回文素数需要记下来呢？我们可以利用前面提到过的’遍历’方案在本地计算一下，结果是不到10000个，那么OK！我们就分配一个大数组，并用一个static global variable记下当前数组使用情况，待所有的回文素数都写入数组，我们对该数组进行一次quick sort，这又需要有个quick sort算法(O(nlogn)级别的，简单快速是我选它的原因)，不过这个比较容易，这里也不详述了。

把这个’回文生成’解决方案提交后，得出14.27s的结果，状态: Accepted。对了千万别忘了，这里还加了些优化，比如不存在位数为6的素数回文，所以当判断n = 6就直接返回，省着走冤枉路！14.27s属于刚及格范畴！该题肯定还有更快的解法，由于太烦，这里就浅尝辄止了！^_^

就在昨天，就在我们的项目要结项的时候，一个影响力不亚于’广岛原子弹’的bug出炉了，蒙蔽我近一个月的问题终于被澄清了，不过为时已晚，项目即将上线，如果想彻底地解决这个问题，需要对整个系统的实现架构作调整，目前能做的只是’亡羊补牢’了。

这里先简单的说一下问题的原因吧！熟悉Unix编程的人都知道有’共享内存映射’这回事儿，我们的问题恰巧就出在对’共享内存映射’的使用不当上。由于我们使用的底层库采用的是mmap的匿名共享内存映射，所以这里例子中的共享内存映射默认就指使用mmap的映射。我们可以利用下面的一个例子简单说明一下我在项目中遇到的问题，实际上看完这个’精简版’之后你会认为这很简单亚，怎么会让你困惑一个月，的确是这样不假，但是如果加上了繁杂的上下文后，找起来也并不是件容易的事情。

假设我们有这样的4个进程，它们的亲缘关系是这样的：A是爷爷，B、C是兄弟，并同为A的儿子，而D则是孙子，是B的儿子，用图表示如下：
A
| —- B
|         |—-D
| 
| —- C
问题就出在D利用mmap映射到匿名设备上后，将返回的起始地址赋值给一块由A创建，B、C、D都继承并能访问到的共享内存中的指针。C的任务是读写这块由D创建的这块儿共享内存中的数据。明眼人一眼就可以看出，C是访问不到这块D映射的共享内存的，即使C知道那块内存在D中的地址，但是由于C没有映射，在C进程空间中即使访问那个相同的地址，实际上访问的虚拟内存页也是不同的，最终的结果就是dump core。不光是C就连B、A也都无法访问D的那块共享内存，原因这里不详说，任一本质量上乘的有关Unix编程的书都会讲到这一点。

出现这样的问题，自己有推卸不掉的责任，先撇开责任不谈，反思自己在查找bug过程中的行为，我觉得有两个问题是今后需要改正的：
1、始终质疑别人的代码，导致在查找bug的时候戴上了’有色眼镜’，思维也发生了倾斜，把大部分时间和精力都花在查找别人的代码漏洞中，而忽略了对自己代码的细致地分析。不过这个过程到让我学了不少以前未接触的’知识领域’^_^。
2、测试时态度不够端正。其实项目负责人当初就对这块儿的可靠性有质疑，只是他当时也不能具体说明到底哪个地方的使用会出问题，回头看来自己在测试时测试用例不全，也是导致没有及时发现对症问题的一个重要原因，从而失去了走向查找出正确问题所在之道的机会！

问题既然发生了，那么我们如何来解决这个问题呢？我和leader一起想了若干种方法结果都被我们一一否决，最后拿出了一个折衷的方案，该方案虽然不存在上述问题了，但是它也让我们的系统不能完全满足用户的需求。这个方案说来也简单那就是采用’池策略’，而且这个池也是一个扩展性不好的池，也就是说我们在系统初始化的时候就预先映射完毕所有的内存，这样所有的A进程的子进程都会继承A的内存映射关系，从而解决上述问题，不过这样做实际上就给系统加了一个限制，容量上的限制。

在接下来的另一个类似需求的项目中我们还需要使用这样的架构，而且这个延续的项目需要的系统容量更大，在这个系统中我们需要对整体的系统架构进行改动了，否则一旦出问题，就不再是’亡羊’就可以’补牢’的了！

目前部门内所有项目的架构基本上都是基于’共享内存’的，虽然’共享内存’是最快的IPC对象，但是它同样给系统带来进程同步性能低下、亲缘关系错综复杂等弊端，甚至于对于我们目前项目这样的需求都不能很好的支持。程序庞大，动一发而牵全身。当然对架构的改造也不是一朝一夕之事，需要的是魄力、时间和耐心，起码让我们的Unix程序符合K.I.S.S这种最适合Unix的文化，目前我们采用的这种架构还是比较臃肿的。