博文

百度首席架构师揭密:算法是百度工程师的利器(来自《程序员》杂志)(2006-04-12 13:57:00)

摘要:百度首席架构师揭密:算法是百度工程师的利器 2006.04.06  来自:《程序员》杂志 周利民     “工欲善其事,必先利其器”,对于百度工程师来说,算法就是他们解决难题的利器。

  为什么这么说?因为百度搜索引擎研发的各个环节都离不开算法。我们需要快速,准确、实用、创新和不断改进的算法来满足用户的需求。
 
  百度面对的是海量的互联网数据,以及每天上亿次的检索请求。它要求百度能够收录和索引超过10亿的中文网页,并提供快速的检索服务。这只有高效率的算法才能完成。

  百度招聘的工程师在加入公司后,有一道入门练习题,就是编写一个数据扫描分析程序,要求写出的程序能在1分钟之内扫描分析完千万量级的数据,才算及格。高水平的程序员可以利用高效的算法在10秒以内解决问题,甚至只要六七秒。但如果没用对算法,花一星期的时间,也做不到1分钟之内。

  大家可以设想一下,百度有十亿以上的网页,如果要在一周甚至三天内处理一遍,平均每秒处理要多少个?每天1亿次的检索又意味着峰值时每秒要处理多少次检索?事实上,针对一个问题,我们可以想出很多的算法,但如果效率不高,是无法真正投入使用的。
  
  Web搜索引擎是一个很新的研究领域,因为从它诞生到现在不过10年左右的时间。学术界IR(Information Retrieval)领域的研究为搜索引擎提供了不少算法方面的理论基础模型,但这些理论距构建一个好的Web搜索引擎还有很大一段距离。这需要我们探索和开发很多新的算法及系统。实际上,百度搜索引擎中的很多算法都极具创新性,而且都是基于实际应用的需求。这是和学术界研究工作的一个较大差异。学术界的算法研究主要是为了解决某个学术方面的问题,不是太关注实用性,以及效率。
  
  举个例子来说,在传统的中文分词算法研究中,学术界最关注的是能达到多高的准确率,但对算法的运行速度上考虑的相对较少。可在百度,如果使用的分词算法速度太慢,就根本无法应用。此外,百度面对的是Web上的大量数据,大部分传统的IR算法都会遇到信息爆炸的问题,我们需要想出很多新的方法来解决这些问题。这对我们的工程师的算法提出了很高的要求。
 
  Web上的数据是不断变化的,用户......

阅读全文(3705) | 评论:0 | 复制链接

算法:元素选择问题总结(2006-01-15 16:42:00)

摘要:元素选择问题 注:中位数:中间大小的数 ;上取整用|  |表示,下取整用[ ]表示 1.选最大
输入:n个不等的数
输出:max

算法1    Findmax
1. max←L[1]
2. for i←2 to lenth[L]
        do if max ......

阅读全文(8401) | 评论:8 | 复制链接

数学猜想(转)(2005-11-25 14:47:00)

摘要:数学猜想 1.【回归数猜想】
    英国大数学家哈代(G.H.Hardy,1877-1947)曾经发现过一种有趣的现象:       153=13+53+33   371=33+73+13   370=33+73+03   407=43+03+73 他们都是三位数且等于各位数字的三次幂之和,这种巧合不能不令人感到惊讶.更为称奇的是,一位读者看过哈代的有趣发现后,竟然构造出其值等于各位数字四(五,六)次幂之和的四(五,六)位数:   1634=14+64+34+44  54748=55+45+75+45+85    548834=56+46+86+86+36+46 像这种其值等于各位数字的 n 次幂之和的 n 位数,称为 n 位 n 次幂回归数.本文只讨论这种回归数,故简称为回归数,人们自然要问:对于什么样的自然数 n 有回归数?这样的 n 是有限个还是无穷多个?对于已经给定的 n ,如果有回归数,那么有多少个回归数?
  1986年美国的一位数学教师安东尼.迪拉那(Anthony Diluna)巧妙地证明了使 n 位数成为回归数的 n 只有有限个.
  设 An 是这样的回归数,即:    An=a1a2a3...an=a1n+a2n+...+ann  (其中 0<=a1,a2,...an<=9)    从而  10n-1<=An<=n9n  即 n 必须满足 n9n>10n-1  也就是  (10/9)n<10n       ⑴    随着自然数 n 的不断增大,(10/9)n 值的增加越来越快,很快就会使得 ⑴ 式不成立,因此,满足⑴的 n 不能无限增大,即 n 只能取有限多个.进一步的计算表明:    (10/9)60=556.4798...<10*60=600......

阅读全文(6709) | 评论:2 | 复制链接

2005年9月12日电脑报第36期编程点将(2005-09-12 20:45:00)

摘要:2005年9月12日电脑报第36期编程点将 题目:请编程实现将1到9 这九个数字分成三个3位数,要求第一个3位数,正好是第二个3位数的二倍,是第三个3位数的三倍。问应当怎样分法。
首先,我认为题目是错的。 原题:请编程实现将1到9 这九个数字分成三个3位数,要求第一个3位数,正好是第二个3位数的二倍,是第三个3位数的三倍。   按这样编的话应该是没有结果的, 我认为应该是: 第一个3位数,是第三个3位数的三倍,而第二个数是第三个数的两倍。   按修改后的题目:以下是我的程序:   程序的主要思想参考我的c语言程序设计百例的第60题,不过里面的题目也是错的,好像电脑报今年的编程点将有90%取自里面的题目。   /*算法思想:根据题意,最小的三位数m可能是在123-333之间,因此循环取尽这些值,
并由此计算出最大的三位数为:3*m,第二个数为:2*m(按原题应该是:3*m/2)。然后判断每个三位数
的各个位是否有重复,没有的话就完成了任务。当然,可能的分发不止一种,
我们采用count来计算可能的分法并输出来
*/
#include<iostream>
using namespace std;
int ok(int t,int *z);//判断每个三位数的各个位是否已经被取过
int A[9];//存放从小到大的三个三位数的各个位
void main()
{
 int m,count=0;
 for(m=123;m<=333;m++) /*最小的三位数的可能值*/
  if(ok(m,A)&&ok(2*m,A+3)&&ok(3*m,A+6)) /*若满足题意*/
   cout<<"第"<<++count<<"种可能的三个数是:"<<3*m<<" "<<2*m<<" "<<m<<"\n";
} int ok(int t,int *z) /*取得t的各个位的值,将其存入z指向的三个数......

阅读全文(5053) | 评论:5 | 复制链接

2005年5月2日第17期电脑报编程点将(2005-09-10 21:15:00)

摘要:2005年5月2日第17期电脑报编程点将

题目:十个小孩围成一圈分糖果,老师分给第一个小孩10块,第二个小孩2块,第三个小孩8块,第四个小

孩22块,第五个小孩16块,第六个小孩4块,第七个小孩10块,第八个小孩6块,第九个小孩14块,第十个

小孩20块。然后所有的小孩同时将手中的糖分一半给右边的小孩;糖块数为奇数的人可向老师要一块。问

经过这样几次后大家手中的糖的块数一样多?每人各有多少块糖?


我的程序:(这道题在我的c语言程序设计百例里面的第75题)
/*这道题看起来简单,但是其实要一次完全做完整不不是很容易。
当然,这题目本身就有点歧义:起初我是这样理解的:第一个人把一半糖给第二个人,
然后第二个人检查一下糖是不是偶数,不是的话就再要一个糖,
然后再把总的糖分一半给第三个……后来发现这样做没有答案。

我的答案和获奖程序一基本上是一样的,主要的不同点在我的程序的注释的部分。
算法的思路比较简单就不分析了。
*/

#include<iostream>
using namespace std;
void main()
{
    const int n=10;
    int child[n]={10,2,8,22,16,4,10,6,14,20};
    int temp,i,count=0;
    bool tag=true;//标志分配完后是否每个数值都是相等的,相等时为false,不等时为true
    while(tag)
    {
        count++;
       &nb......

阅读全文(3707) | 评论:0 | 复制链接

2005年4月25日第16期电脑报编程点将(2005-09-10 20:03:00)

摘要:2005年4月25日第16期电脑报编程点将

题目:小明有五本新书,要借给A,B,C三位小朋友,若每人每次只能借一本,则可以有多少种不同的借法?

我的程序:
/*算法思想:其实这是一个排列的问题,这里我们假设五本书的编号室从1——5,
用数组ABC[3]来表示A,B,C三个人,其数值表示这三个人所借的是什么书
(也就是哪个编号的书)。穷举使三个人都可能借到每一本书,
当然,不能两个人借同一本书。

*/
#include<iostream>
using namespace std;
void main()
{
    int ABC[3],count=0;
    for(ABC[0]=1;ABC[0]<=5;ABC[0]++)
        for(ABC[1]=1;ABC[1]<=5;ABC[1]++)
            for(ABC[2]=1;ABC[2]<=5;ABC[2]++)
                if(ABC[0]!=ABC[1]&&ABC[0]!=ABC[2]&&ABC[1]!=ABC[2])
                    count++;
    cout<<"总的借书方式有:"<<......

阅读全文(3266) | 评论:0 | 复制链接

2005年8月22日第33期电脑报编程点将(2005-09-09 23:54:00)

摘要:2005年8月22日第33期电脑报编程点将
题目:某侦察队接到一项紧急任务,要求在A,B,C,D,E,F六个队员中尽可能多挑若干个人去完成任务,但有以下限制条件:
(1)A和B两人中至少去一个;
(2)A和D不能一起去;
(3)A、E和F三人中要派两个人去;
(4)B和C都去或者都不去;
(5)C和D两人中去一个;
(6)若D不去,则E也不去。
请用程序求出应该让哪几个人去?

我的分析和程序:

/*用整数a,b,c,d,e,f来表示这六个人去或者不去,值为0代表不去,值为1代表去。用循环让这六个数可以取遍0和1,
当满足题目所要求的条件就显示出来,题目中的条件可以通过下面的来判断:
(a||b)==1//条件(1)
&&(a&&d)==0//条件(2)
&&(((a&&e)==1&&f==0)||((a&&f)==1&&e==0)||((e&&f)==1&&a==0))//条件(3)
&&(b==c)//条件(4)
&&(c!=d)//条件(5)
&&(e<=d))//条件(6)
*/

初步程序:————这里没有考虑题目中的:尽可能多挑选若干个人去。也就是人应该尽量多
该程序在VC++6.0通过运行,结果:可以叫下面的人去:A  B  C  F

#include<iostream>
using namespace std;
int AA[6];
char BB[]={'A','B','C','D','E','F'};
void main()
{
    int &a=AA[0],&b=AA[1],&c=AA[2],&d=AA[3],&e=AA[4],&f=AA[5......

阅读全文(4005) | 评论:1 | 复制链接

2005年9月5日第35期电脑报编程点将台(2005-09-10 18:44:00)

摘要:2005年9月5日第35期电脑报编程点将台

题目:构造N*N阶的拉丁矩阵(2<=N<=9),使方阵中的每一行和每一列中的数字1到N只出现一次。如N=4时:
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

我的程序:
/*算法思想:
通过观察,我们可以发现规律就是:第一行从1开始递增直到n,
第二行从2开始递增,当超过n是就得到其与n的模加上1即可,
以此类推直到完成所有的排列。

  我的程序的问题:没有考虑所有可能的情况,只是根据已有的得出规律
  其实相当于是不完全归纳法。不过,要是想得出所有可能的情况的时间复杂度将比较大


*/
#include<iostream>
using namespace std;
void main()
{
    int i,j,n;
    const int maxsize=9;
    int AA[maxsize][maxsize];
    cin>>n;
    if(n<2||n>9)
    {
        cout<<"You are wrong!";
        return ;
    }
    for(i=0;i<n;i++)//初始化
       &......

阅读全文(3510) | 评论:0 | 复制链接

2005年5月16日第19期电脑报编程点将台(2005-09-09 22:45:00)

摘要:2005年5月16日第19期电脑报编程点将台

题目:三对情侣参加婚礼,三个新郎为A,B,C,三个新娘为X,Y,Z。有人不知道谁和谁结婚,于是询问了六

个新人中的三人,但是听到的回答是这样的:A说他将和X结婚;X说她将的未婚夫是C;C说他将的Z结婚。

这人听后知道他们在开玩笑,全是假话。请编程找出谁将和谁结婚。


我的程序:

/*算法思想:对三个新娘分别分别新郎,当满足以下条件时就输出:
X!='A'&&X!='C'&&Z!='C'表示三个假话,&&X!=Y&&X!=Z&&Y!=Z
表示每个新娘的新郎都不一样(^_^也就是没有一妻多夫)

  我的程序的时间复杂度是:n的三次方,所以不是很好,
  但是要是直接从题目中推理然后去掉一些可能性后再配对的话,
  那么其实马上可以得出答案,也就是这题其实出得很差得,完全没
  必要用计算机来推理。

  在我的程序的后面是那期获奖的两个程序。大家可以参考。不过,感觉我的程序
的可读性比较好,获奖的程序我也看了很久理解什么怎么得出来的。
*/
#include<iostream>
using namespace std;
void main()
{
    char X,Y,Z;
    for(X='A';X<='C';X++)
        for(Y='A';Y<='C';Y++)
            for(Z='A';Z<='C';Z++)
   ......

阅读全文(3170) | 评论:0 | 复制链接

2005年8月15日第32期电脑报编程点将(2005-08-25 16:46:00)

摘要:2005年8月15日第32期电脑报编程点将

题目:有30个人,其中有男人、女人和小孩,他们在一家饭馆吃饭,总共花了50元;每个人吃饭的花费是:男人3元,女人2元,小孩1元。请编程求解男人、女人和小孩各几人?

我的分析和程序:
这道题其实跟“百钱买百鸡”几乎是完全相同,很easy。在题目中说:有30个人,其中有男人、女人和小孩。因此就是说这三种人都应该有。我们用mNum,woNum,chNum分别来表示男人,女人和小孩的数量,这他们的值至少为1。

程序:
#include<iostream>
using namespace std;
void main()
{
    int mNum,woNum,chNum,count=0;
    for(mNum=1;mNum<16;mNum++)
        for(woNum=1;woNum<=23;woNum++)
        {
            chNum=30-mNum-woNum;
            if(3*mNum+2*woNum+chNum==50)
                cout<<"第"<<++count<<"种可能是男人、女人、小孩分别为:"
    &......

阅读全文(3395) | 评论:0 | 复制链接