银河里的星星
转载请注明作者：phylips@bmy 出处： http://duanple.blog.163.com/blog/static/7097176720098303134160/
概述
在正则表达式领域，有一本广为推崇的书籍<<精通正则表达式>>，但是作者在书中的很多地方假设那些匹配引擎采用的是回溯的算法。但是实际情况是有些引擎采用的NFA，DFA模拟算法，比如grep，awk，sed，对于它们来说算法复杂度是多项式级的。同时采用回溯的一些引擎也在逐步改进，比如通过采用备忘录方法，记住已经回溯到达的状态，防止重复，也可以避免指数级的复杂度。 read more
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