存档

2011年9月 的存档

美妙的const

2011年9月15日 没有评论

 

最近编程总遇到const的问题,于是就想总结一下,这里的总结不是想面面俱到,而是想把个人觉得有必要注意的问题和那些让人感觉const美妙的地方梳理一下,欢迎留言补充

本文大概将分三个层面

  • const指针、const引用、const引用形参
  • const在类中
  • const与重载

------------- const指针、const引用、const引用形参 --------------------

【1】const修饰指针和引用

1. 术语“const引用”就是“指向const对象的引用”,习惯说成const引用与非const引用。这点与指针不同,指针中“const指针”与“指向const对象的指针”是不同的。

2. 值得注意的是:const引用和指向const对象的指针二者有一个共同点:const引用既可以指向const对象又可以指向非const对象;指向const对象的指针亦是如此.

3. 关于const指针与指向const对象的指针,举一个很简单例子

int m=1, n=5;
const int *p1=&m;   //指向const对象的指针:const修饰的是*p1, 即*p1的值是只读的;但是p1这个指针是可以修改的。
int * const p2=&n;  //const指针:const修饰的是p2, 即p2这个指针是只读的;但是*p2的值是可以修改的。
p1=&n;              //p1的指针修改为变量n的地址,而这个地址就是p2,相当于p1=p2;
*p2=3;              //*p2的值修改为3,当然*p1的值也就是3
printf("%d %d\n",*p1,*p2);

【2】形参为const引用的好处

说到const,就不得不提const引用类型的形参,真正理解了const引用形参的好处,才发现它真是美妙的很

简单总结一下,欢迎补充

阅读全文...

博客被各搜索引擎收录情况

2011年9月8日 1 条评论

 

记录一下,博客先后被Google,百度,soso,bing等收录啦!O(∩_∩)O~,下面是搜索“勇幸”关键词博客在各引擎的排名情况。

  • Google

写了几篇博文后,博客就被谷歌收录了,刚开始排在了第一页的末端,前几天已经上升到第一的位置啦,O(∩_∩)O~,截图留念

而且Google的网页更新周期相当快,几天吧,我对网站的更新,两三天后就收录了最新的。

google收录情况

阅读全文...

海量数据处理之归并、堆排、前K方法的应用:一道面试题

2011年9月8日 6 条评论

 

最初关注海量处理方面是因为好久以前在西安交大BBS算法版上看到一个牛人总结的帖子,收集了起来,后来发现网上铺天盖地地转载过,那个帖子提供了一些解决问题很好的思路,所以就零碎地整理过海量数据处理方面的一些方法,但终归没有深入并做一个稍微细致的思考,从这篇博文开始,希望能坚持整理出来。

下面一道面试题是以前大雄考过我的,据说是那时一些公司常问的类型题目,这里回顾并总结一下,欢迎大家讨论并提出问题。

题目:一个10G的关键词的log,找出词频最高的前K个词,设可用内存为2G左右

分析:

本题的难点主要有两处,一是如何在有限内存下对大文件进行词频统计;二是如何在有限内存的下找出词频的前K大个词

  1. 词频统计

词频统计,我们很自然的会想到使用hash。但是直接hash内存是放不下的啊…怎么办?其实对于有限内存下的大文件处理,都可总结为归并的思想,不过要注意归并时的分段亦是有学问的。请比较归并a与归并b方法

  • 归并a:将数据分为5段,分别对每段在内存中hash统计并将统计结果写入文件,然后合并分段的hash。

问题:表面看来不错的主意,实则有很大问题,稍微想一下,a方法存在一个主要的困难就是,hash合并的时候相当于同时在5个文件中判断是否有相同的词,要这样做会非常繁琐。

怎么解决呢?我当时是受编程珠玑中第一题(排序一千万个32位整数)启发的,它在归并分段的时候,不是直接的简单分段,而是每段取一个范围比如第一段取0~249000之间的数,这样有什么好处?将来的各段数彼此间是没有交集(重复)的。所以我们的思想就是要让这10G的关键词分段后各小段没有交集,这样hash合并就没有问题了。请看归并b

  • 归并b:将数据分为5段,分段时对每个词hashhash值在一个范围中的词语分到一个段中,然后对于每个分段统计的hash结果直接都写入一个文件即可。

分析:使用hash分段,保证各小段没有重复的词。我当时想的方法是将词语的首字拼音打头一样的分在一段中,例如“五谷丰登”、“万箭齐发”分到一起,都是w打头的拼音,其实这仅仅只是hash的一种,至于具体的hash函数,就不讨论了,哈哈

阅读全文...

百度联盟事业部研发工程师招聘/实习生

2011年9月5日 3 条评论

帮师兄转发:

百度联盟事业部研发工程师招聘/实习生

亲爱的同学们:

好消息!百度实习生招聘火热进行中.......

此次招聘,属于部门自主招聘,会走内部推荐哦.......

简历直接送达项目经理,以最快的速度安排招聘哦......

【招聘岗位】 - 研发工程师

【招聘部门】 - 联盟事业部(商务搜索部)

【主要工作】

- 用户特征挖掘和行为分析

- 大规模数据的自动化分析处理

- 商务搜索引擎的算法改进、架构优化及策略研发

【招聘要求】

- 在校学生,本科以上学历 - 有充裕的时间实习(两个月以上)

- 优秀的分析问题和解决问题的能力,对解决具有挑战性问题充满激情 - 精通linux平台上的C/C++语言编程,熟悉shell编程

- 熟悉网络编程、多线程编程技术,有相关系统开发和设计经验

- 对数据结构和算法设计有较为深刻的理解

- 具有良好的沟通能力和团队合作精神

阅读全文...

分类: 生活随笔 标签: , ,

关于反转字符串(Reverse Words)的思考及三种解法

2011年9月4日 1 条评论

 

早些时候在水木上看到一道面试题,于是就思考着如何去解,也就有了上篇博客的整理以及这篇文章的思考。

题:反转一个字符串句子中的单词,例如“Do or do not, there is no try.”反转后为“try. no is there not, do or Do”假设所有的单词间都是以空格分离的,将标点符号视为单词的一部分。

基于上篇文章本文提供三种方法解决该问题,第一种是Houdy博客中提到的方法,后两种方法是我在思考这个问题时想到的。其中,前两种方法都是基于Divide-and-Conquer (分治)的思想,该思想非常强大,是解决问题的一个重要的方法;第三种方法是基于非分治的思想,比分治能优化一些,较为直接,欢迎讨论。

注:以下方法在实现中所用到的函数都是源自与上一篇博文:交换两段连续(不连续)内存

方法一(分治A):

上篇文章我们提到了反转内存以及如何交换两段连续和非连续的内存,这里的分析也要基于此。个人感觉Houdy的分析很到位,循序渐进,由浅入深,他的核心思想我就直接转载了,呵呵。

从整体考虑这个问题,我们要处理的是由多个单词(单词间用空格分隔)构成的字符串,这个字符串中基本的元素就是单词和空格。首先拿几个特例来分析一下,看看有没有什么收获。

  1. 字符串中没有空格。这时候相当于字符串中只有一个单词,我们不需要进行任何操作。
  2. 字符串中有一个空格(暂且认为空格在中间)。这是反转两个单词的操作,等价于反转两块不连续的内存块的操作,这个操作上篇文章我们已经实现了
  3. 字符串中有两个空格。例如 ”Tom Jerry Mike”,我们应该怎么处理这种情况呢?结合前面两个特例的分析,我们可以马上想到一种常见的解决问题思路,即分治,也就是Houdy说的 “Divide-and-Conquer”。总体来说,我们可以将包含多于一个空格的字符串划分成三个部分:   |位于空格左边的字符串|空格|位于空格右边的字符串|

这样,我们就完成下面的处理就可以了:

  1. 对空格左边的字符串进行“反转字符串”处理
  2. 对空格右边的字符串进行“反转字符串”处理
  3. 将字符串看成一个整体,对左边的串和右边的串进行“交换两块不连续内存”处理

如果左右字符串中还包含多于一个空格,我们可以分别对他们再进行“分割”+“反转”的操作,直到字符串中的空格数量不大于1,空格数等于1时,做“交换两块不连续内存”的操作。所以,我们需要计算空格数目并记录空格的索引。

阅读全文...

交换两段连续(不连续)内存

2011年9月4日 没有评论

在《编程珠玑,第二版》和《编程之美》中都有关于交换两段连续的内存块的题目,而且非常经典,交换两段连续内存块的问题又可以延伸到交换两段不连续内存块的问题,无论是哪种情况都需要一个基本操作:反转内存块

反转内存时,比较简单,可以两个指针同时走,也可以一个指针,随意,实现如下:

01 // reverse the memory block
02 // goal: |12345| -> |54321|
03 void * reverseMemory(void *pMemory, const size_t memSize)
04 {
05     if(NULL == pMemory) return pMemory;
06     if(memSize < 2)        return pMemory;
07
08     char * beg = static_cast<char *>(pMemory);
09     char * end = beg + memSize -1;
10     for(; beg < end; ++beg, --end)
11     {
12         char memTmp = *beg;
13         *beg = *end;
14         *end = memTmp;
15     }
16     return pMemory;
17 }

其中,函数的两个形参分别为要反转内存的起始地址和内存块的大小。返回值类型为void*,指向反转内存块的起始地址。

实现了反转内存块这一基本操作后,我们就可以用它来交换两段连续的内存,从而解决类似“数组循环移位”的问题。具体算法在编程珠玑和编程之美中都有详细介绍,这里简单说一下:

假设有连续的内存块M和N形如:|----M---|--------N---------|

  1. 首先反转内存块M:M’=reverse(M)
  2. 反转内存块N:N’=reverse(N)
  3. 对整个内存块M’ N’进行反转:(M’N’)’ = NM


阅读全文...