duanple

Brian W. Kernighan and Rob Pike

[说明：本文由phylips@bmy翻译自Regular Expressions Languages, algorithms, and software 1999-01 Author： Brian W. Kernighan and Rob Pike。Brain 和 Rob是朗讯科技贝尔实验室的研究人员，可以通过他们各自的邮件bwk@bell-labs.com and rob@bell-labs.com联系他们。]
原文链接：http://www.ddj.com/architect/184410904?pgno=1，转载请保留全部信息。 read more

1. 给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。 

2. 有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序
 
3. 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词 read more

http://blog.csdn.net/nileel/archive/2008/06/03/2508918.aspx

今天下午去微软面试，被问到了海量数据查询优化的问题，由于平时开发的应用数据量比较小，不太关注性能优化的问题，所以不知如何作答，很是郁闷。从网上搜索出海量数据查询优化的两篇文章，转载下来，权当学习性能优化的开始。 read more

http://www.cnblogs.com/neoragex2002/archive/2007/11/01/VC8_Object_Layout_Secret.html

哈哈，从M$ Visual C++ Team的Andy Rich那里又偷学到一招：VC8的隐含编译项/d1reportSingleClassLayout和/d1reportAllClassLayout 。看个复杂的例子吧(如下)，现在假设我们想知道Derived类的对象布局，怎么办? 在Project Properties->C++->Command Line->Additional Options里面加上/d1reportSingleClassLayoutDerived吧！ read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720098283597120/

对于通常的尾递归很容易转换成循环。通过手工模拟我们基本上就可以确定如何进行转换。实际上尾递归的转换也可以看成是下面这种模式的特殊情况，在这种模式下，尾递归只是一个这样的递归树。 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/70971767200982584340501/

1.求最长回文子串。
[解法]：
将整个字 符串反过来写在原字符串后面，中间用一个特殊的字符隔开。这样就把问题变为了
求这个新的字符串的某两个后缀的最长公共前缀。而某两个后缀的lcs的计算利用后缀数组，可以O(1),这样总的复杂度就可以降为O(n)。
eg：aabebf  —->   aabebf&fbebaa read more

涉及到字符串的问题，无外乎这样一些算法和数据结构：自动机 KMP算法 Extend-KMP 后缀树 后缀数组 trie树 trie图及其应用。当然这些都是比较高级的数据结构和算法，而这里面最常用和最熟悉的大概是kmp，即使如此还是有相当一部分人也不理解kmp，更别说其他的了。当然一般的字符串问题中，我们只要用简单的暴力算法就可以解决了，然后如果暴力效率太低，就用个hash。当然hash也是一个面试中经常被用到的方法。这样看来，这样的一些算法和数据结构实际上很少会被问到，不过如果使用它们一般可以得到很好的线性复杂度的算法。 read more

1.将字符串转换成整数，将整数转换为字符串，浮点数与字符串的转换(atoi itoa)

int atoi(const char *str){
    int res = 0;
    int sign;
    assert(str != NULL);
    if(str[0] == ‘-‘) sign = -1;
    else if(str[0] == ‘+’) sign =1;
    else if(isdigit(str[0])){sign = 1;res=str[0] – ‘0’;} read more

这个程序，大概在2006年看到的，当时进行了分析，主要分析了位运算那部分：如何利用浮点数的位表示法快速计算一个近似值。而对于整个迭代计算原理并没有仔细看，今天再重新分析一下，并把当时那部分分析写的更明了些。 read more

并发执行，在我们串行执行的pc上的含义，是指两部分的程序代码，可能以任意的次序执行。如果它们对共享对象进行了修改，如果汇编指令的执行顺序不同，就可能产生不同的结果，这样就有问题，必须对程序的执行过程进行控制。这个本质也提供了一种我们分析一段程序是否需要人工控制的标准:考虑两个程序的汇编级的指令混合，结果会如何？ read more

由于整个网络是非常巨大的，如果想把整个网络上的主机看成同样的层次，运行相同路由算法，这根本是不可行的。实际的网络是通过分层的思想，将数量庞大的主机联系起来。将整个internet划分成很多不同的自治系统，自治系统内部运行一个路由算法，自治系统之间通过边界路由器进行通讯，这样一个分层系统实际上通过一个默认网关地址联系起来，我们可以注意到前面一篇文章中的网络地址0.0.0.0,这个是默认网关地址，即自治系统接入主干网的入口，如果本自治系统内无法找到目标地址，就要交给上层主干网，因为它跨越了不同的区域，这样两个层次在包传递的过程中就联系起来了。 read more

一个http请求的详细过程

我们来看当我们在浏览器输入http://www.mycompany.com:8080/mydir/index.html,幕后所发生的一切。

首先http是一个应用层的协议，在这个层的协议，只是一种通讯规范，也就是因为双方要进行通讯，大家要事先约定一个规范。 read more

面试的时候，书写程序要注意以下几点

1.确认了解题意，如果对题意了解不清，应该向面试人员问清楚
2.明确题意后，首先思考找到一个复杂度可以接受的正确算法，并表述出来，注意可以在草稿纸上写写划划，进行验证
3.观察复杂度能否再次降低
4.书写程序时，一定要认真，坚决防止出现逻辑错误，并根据程序具体分析可能的极端情况，处理好边界，并自己进行用例测试，以验证程序。 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720098311658625/

RSA加密系统，实际上基于这样一个基本事实。大数的素性测试要比因子分解简单的多，因子分解是一个难问题。

素数测试

如何测试一个数n是不是素数呢？简单的办法就是试一下它能否整除比它小的那些数，当然可以优化只检测小于sqare(n),但是无论如何优化，需要检测的数的个数都将不会小于小于sqare(n)的素数的个数。根据拉格朗日定理，小于n的素数的个数大概=n/ln(n)，也就是说这个数目很大，数量级上很接近n了。所以这个路子实际上很难降低复杂度。 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720098210128972/

欧几里德算法

用来求两个数的最大公约数的算法。具体如下
int gcd(int a,int b){
   if(b == 0) return a;
   return gcd(b,a%b); 
}

首先看正确性证明，实际上需要证明gcd(a,b)=gcd(b,a%b),我们只要证明gcd(a,b)=gcd(a-b,b)即可，因为可以由此逐步扩展为gcd(a,b) = gcd(a-k*b,b),而 gcd(a-k*b,b)=gcd(a%b,b)。
因为a,b的公约数必然是a-b,b的公约数故 gcd(a,b) <= gcd(a-b,b);另a-b b的公约数也必然是a b的公约数，gcd(a,b) >= gcd(a-b,b).所以gcd(a,b) = gcd(a-b,b)。证明完毕。 read more

http://blog.csdn.net/programmer_editor/archive/2009/02/06/3865839.aspx

■ 文／牛新庄

编者按：牛新庄，数据库维护、优化和架构专家；曾获得国内数据库领域最高荣誉——“2006年中国首届杰出数据库工程师”； 数年前曾被IBM全球软件部以年薪60万元人民币聘用，而他却婉然拒绝。这样一个躲藏在幕后的“牛人”，有着怎样的学习、发展之路？为此，本刊特邀牛新庄博士，请他讲述一个真实版的“数据库之路”。  read more

转载请注明作者：phylips@bmy

哥德尔完备性定理

希尔伯特在20世纪20年代介绍了他的元数学纲领：一致性有待证明的公理将被包含在一个形式逻辑系统之内，而证明仅仅是有限数目的符号的一种排列而已。当希尔伯特开始思考希尔伯特纲领时，希尔伯特的学生阿克曼和冯诺依曼似乎正在朝着用有限性方法证明PA的一致性的方向大步迈进。他们二人都已经为PA的一个有限的子系统找到了这样的证明，成功似乎指日可待。 read more

 转载请注明作者：phylips@bmy

弗雷格的突破与绝望

弗雷格的一生主要发表了这样三本著作：《概念演算–一种模仿算术语言构造的纯思维的符号语言》（1879）、《算术的基础–对数概念的逻辑数学研究》（1884）《算术的基本规律》（l卷 1893，2卷1903）。 read more

序

人类的历史可以看做一部关于解放的历史。也有这样的说法，懒惰是人类进步的动力。为了偷懒，人类不断的做着各种努力，发明了各种机器工具，将自己从繁重的劳动解放出来，另一方面，每一次大的进步，都需要解放思想，同时也带来了全人类思想的大解放。在这样的历程中，计算机的出现无疑将人类从很多繁重的作业中解放了出来。与此同时，有些人开始思考能否制造出可以像人类一样进行思考的机器，以将人类从创造性的劳动和逻辑思考中解放出来，交给机器去完成。 read more

1.购买cell处理器ps3
安装操作系统，安装编程环境cellsdk
利用该编程环境编译mpi库，blas库，lapack，blacs，scalapck库
这些库放到intel上的异构编程环境下，编写并行程序，将生成的可执行程序放到ps3上，与intel上的运行

测试普遍的blas库和ibm提供的面向cell的blas库的效率差异 read more