存档

2011年10月 的存档

信息指纹 [数学之美学习笔记]

2011年10月27日 没有评论

---

Hash与信息指纹有什么关系?为什么要用信息指纹?

最近在整理布隆过滤器相关资料的时候,觉得有必要提一下信息指纹和MD5.

不得不承认,自己以前使用hash的方法弱爆了,借《数学之美》的文章记录一下从哈希到信息指纹的缘由。

回忆一下以前使用hash的时候:

情景一:


Java: HashTable<string,int> ht = new HashTable<string,int> ();

C++: map<string,int> m;

其实平时这样用也无所谓,但是数据量大了,string就不好办了。

情景二:

以前自己写过一个爬虫,当时存储URL的时候直接就是以字符串的形式存储的,测试时有的url非常长,当时虽然感觉挺费空间的,但还是偷懒了,逃避困难逃避改变导致了今天的幼稚,所以直面问题,加紧充电,爬虫的重写也在最近的计划中,MD5,布隆过滤器应该都能用到。

入正题,hash为什么要用信息指纹?请看下面的例子

任何一段信息文字,都可以对应一个不太长的随机数,作为区别它和其它信息的“指纹”。

在爬虫中网址的消重上,需要在哈希表中纪录已经访问过的网址(URL)。假设现在要存储在哈希表中如果以字符串的形式直接存储网址,既费内存空间,又浪费查找时间。

阅读全文...

布隆过滤器(Bloom Filter)

2011年10月23日 没有评论

---

最初知道布隆过滤器是通过数学之美了解的,后来学习算法时,09年在西交BBS算法版上偶然看到一篇帖子,讲海量数据处理的,也提到了布隆过滤器,后来的学习过程中发现网上转载的相关文章铺天盖地,参差不一,大部分是一个概述性的东西,要真正为我所用还需要一个深入的思考和细致的分析,本博力求做到这样的思考和分析,对bloom filter做一个详细的总结,所涉参考文献也将一并给出,欢迎讨论。

本帖希望在了解bloom filter的基础上能分析解决实际问题,并实现其代码加深理解,拟包含以下几方面:

欢迎关注并讨论。

阅读全文...

本站部分代码下载

2011年10月21日 1 条评论
分类: C/C++ 标签: , ,

你必须非常努力,才能看起来毫不费力

2011年10月18日 1 条评论

有一个很浪漫的故事

有一群人,他们积极自律,每天按计划行事,有条不紊;他们不张扬,把自己当成最卑微的小草,等待着人生开出花朵的那天。他们早晨5点多起来健身,你在睡觉;7点开始享受丰盛的早餐,蛋白质维生素淀粉粗纤维样样俱全,为新的一天起了一个好头,当他们收拾妥当准备开始一整天的工作时,你还在睡觉;

他们用上午的高效时间完成了一个又一个任务,甚至发现的新的商机,发现了有可能给人生带来改观的机遇,当午餐时间临近,他们伸了伸腰,准备稍作休息,此时你终于起床。

他们的午餐不铺张浪费,却营养全面,他们有选择的进食,因为清楚的知道自己想要的是什么,而你也在起床之后但觉到了饿意,你早早的洗了把脸,甚至连牙都没刷,打开冰箱,拿出了昨晚跟朋友high过之后带回来的薯条以及可乐;

午睡之后,他们重新积极的投入工作,而你也终于吃饱喝足,坐在了电脑前。是的,你的一天开始了。

晚上回到家里,他们也打开了电脑,也许是为了完成白天没来得及做完的工作,也许是因为前两天刚报了一个网络课堂,此时你还沉浸在dota中,你发的贴子还不够有人气,你发现空老师又更新微薄了,电视剧里男女猪脚还没有最后在一起,作恶多端的女二号还没有得到应有的报应。

终于,22点到了,他们停下了工作,或许去满满的书架上拿下了一本书,或许拿起了自己心爱的乐器打算练练手,或许已经上床睡觉。当然,睡之前他们会想一想,自己在这一天都做了什么,有什么收获,又有什么教训。

最后,他们又重新提醒了一下自己那个埋在内心深处的梦想,然后满意的睡去了。此时的你还在等待升级,还在顶贴子,还在刷微薄,还在为了男一号女一号哭哭啼啼,你的一天才刚刚开始精彩。

阅读全文...

分类: 自我管理 标签: , , ,

Dennis M. Ritchie 逝世了

2011年10月13日 没有评论

C语言发明人丹尼斯-里奇去世

美国著名计算机专家、C语言发明人之一丹尼斯·里奇

新浪科技讯 北京时间10月13日上午消息,维基百科资料显示,美国著名计算机专家、C语言发明人之一丹尼斯·里奇(Dennis Ritchie )已于10月9日去世,享年70岁。

里奇生于1941年9月9日。他发明了包括C语言在内的多种编程语言,并研发了Multics和Unix等操作系统。1983年,里奇获得图灵奖。

转自:新浪科技

阅读全文...

推荐文章

2011年10月13日 4 条评论

重载流操作符的函数定义 -- 一个小问题所想到的

2011年10月8日 没有评论

 

以前助教班的学生昨天问了一个小问题: 重载输出流操作符的定义为什么一定是如下格式:

ostream & operator << (ostream & output, const ClassType & object)
{
	output << ...
	...
	return output;
}

他说以前遇到这种格式“复杂”的东西直接看参考书怎么写的,今天突然觉得这个为什么这样写啊,写成其他的形式不行么?记得我刚学C++的时候也犯过类似抄参考书的毛病,后来慢慢才理解了。针对重载输出流操作符有如下问题:

  1. 返回类型为什么是引用?
  2. 第一个参数为什么用引用?
  3. 第二个参数为什么又是const引用?

一个函数的定义,从返回类型到形参列表,我们都要有清晰的认识和理解,才能明白应该怎样编写这个函数。

  1. 返回引用是为了使得返回结果为左值,相当于一个独立对象的作用,使我们可以做连续输出的操作,例如
     cout << object1 << object2 <<endl; 

    注意:返回引用要慎用,尤其是不能返回局部变量的引用,一般返回引用是针对当前对象返回 *this 或者返回const 类型的引用。

  2. 第一个参数之所以为引用,首先是避免了IO对象的复制,注意:这里不是刻意避免IO对象的复制,而是IO对象不可复制或赋值,所以这里必须用引用类型,不能传递流类型。由此我们应该知道,既然IO对象不支持复制或赋值,则一方面流对象不能存储在vector或其它容器中(只有支持复制的类型才可以存储vector等容器中);另一方面,形参或返回类型都不能为流类型(因为涉及复制),如果要传递或返回IO对象,则必须传递指向该流对象的指针或引用。此外,可能你会注意,为什么第二个参数为const类型,那第一个参数为什么不是const呢?ostream之所以为非const类型,很明显,写入流会改变流的状态,所以使用非const
  3. 第二个形参为const类型的引用,关于这样形参的好处,在博文“美妙的const”中有详细阐述。首先对于要输出的类类型,避免了对象的复制;其次,一般输出一个对象是不应该改变该对象的,故为const;再者,const引用可以使得传递参数更为灵活,例如,这样定义,我们就可以使用同一个定义来传递输出const和非const对象。关于const与非const对象的问题,参见博文美妙的const.
  4. 说到这里,顺便提一下重载输入流操作符,在输入流操作符函数定义中,第二个参数则必须为非const,因为输入流要改变该对象。

阅读全文...

男女最性感的十个瞬间(zz)

2011年10月7日 没有评论

 

今天在网上看到一篇文章,挺有意思,转来娱乐

女人最性感的十个瞬间:

1 隐约露出丝袜的蕾丝花边;

2 在深邃的夜里点燃一根淡淡的香烟;

3 双手有意无意交叉放在胸前;

4 沐浴之后头上湿漉漉的水滴涟涟;

5 神情地注视着你的双眼;

6 娇柔地躺在心爱的男人枕边;

7 丈夫回家之后做好一桌的饭;

8 刚起床之后衣冠不整让人浮想联翩;

9 穿着自己心爱男人的宽松衬衫;

10 在爱人面前前狂野十足地把被子一掀。

男人最性感的十个瞬间:

1 刷碗

2 刷碗

3 刷碗

阅读全文...

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

乔布斯去世

2011年10月6日 没有评论

 

今天早上来到实验室,微博上铺天盖地的消息:乔布斯去世了!

苹果公司网站发布的消息说:“苹果失去了一位富有远见和创造力的天才,世界失去了一个不可思议之人。”

世界失去了一位天才,一个能把科学技术、艺术、工业设计融为一体的CEO,一个能把濒临倒闭的公司做成市值世界第一的CEO,一个有勇气拥有不同想法并努力改变世界的人!乔帮主,世界会记住你来过!

缅怀乔老爷,重温乔帮主的精神:stay hungry,stay foolish!

乔布斯在斯坦福大学的演讲(中英字幕)

阅读全文...