url排重和bloom filter(转载)

from http://blog.csdn.net/accesine960/archive/2007/01/23/1491483.aspx.

误差换效率

google黑板报上一片文章,讲Url排重用到的一个技巧:把平均长度较长的Url转换成平均长度较短的GUID来节省空间。在Url排重方面还有一个常用的算法:Bloom Filter 算法。Bloom Filter 算法是查看元素E是否在集合S中存在的快速算法,典型的应用就是拼写检查spellcheck时,查看某个单词是否在字典中存在。关于查询的算法有很多种了,排序折半、B-Tree、Hash-Code 等等。Bloom Filter 的优点是什么呢?

1、Bloom Filter不存储key-value值,Bloom Filter 用一组Hash算法把集合S中的元素E换算成位表示;

2、查询速度快。

我们知道Hash算法一般都有冲突,在Bloom Filter中的冲突就表现为误差了。

Bloom Filter 是一种常见的算法,现在已经有了 Java , C++ , C# , ruby 等各个版本的算法。当然也有很多变种出现以适应更多的需求。

Bloom Filter 是有误差的,但误差在可控制的程度内。换句话说,大多数的误差的恼人之处在于我们无法衡量它。

参考阅读:

http://blog.likeshow.net/article.asp?id=34

http://blogs.msdn.com/devdev/archive/2006/01/23/516431.aspx

http://en.wikipedia.org/wiki/Type_I_and_type_II_errors

http://en.wikipedia.org/wiki/Bloom_filter

http://jaspell.sourceforge.net/javadocs/index-files/index-2.html

http://blogs.msdn.com/devdev/archive/2005/08/17/452827.aspx

http://www.cc.gatech.edu/fac/Pete.Manolios/research/bloom-filters-verification.html

http://homepages.inf.ed.ac.uk/s9902505/specksim/doc/index-files/index-2.html

http://weblogs.asp.net/dfindley/archive/2004/08/19/217485.aspx

http://www.darkridge.com/~jpr5/archive/dads/HTML/bloomFilter.html

http://loaf.cantbedone.org/

url排重和bloom filter(转载)

有效运用auto_ptr

 

有效运用auto_ptr

auto_ptr是一个类模板,用于生成具体的智能指针,它们知道在用完以后如何清理资源。如:

using std::auto_ptr;

auto_ptr<Shape> aShape(new Circle);

aShape->draw(); //画一个circle

(*aShape).draw(); //再画一个circle

如同所有设计良好的智能指针一样,auto_ptr重载了operator->和operator *,因此通常可以假装自己在处理一个内建的指针。

auto_ptr有很多好处,首先非常高效。其次,当auto_ptr离开作用域时,其析构函数将会释放它所指向的任何东西。在上面的代码片段中,aShape所指向的Circle对象们将会有效地被垃圾收集。再次,在类型转换方面,其行为酷似内建指针。如

auto_ptr<Circle> aCircle(new Circle);

aShape = aCircle;

通过灵活使用模板成员参数,一个auto_ptr可以赋值给另一个,只要相应的内建指针支持这种操作就可。在上面的代码中,一个auto_ptr<Circle>可以赋值给 auto_ptr<Shape>,因为一个Circle*可以赋值给一个Shape*(假定Shape是Circle的一个公有基类)。

auto_ptr不同于普通的智能指针的地方在于其赋值操作。当auto_ptr执行赋值操作时,参与赋值的源值和目标值都受到了影响。

auto_ptr在两个场合应该避免使用。首先,他们永远都不应该被用做容器元素。其次,一个auto_ptr应该指向单个元素,而不该指向一个数组。

有效运用auto_ptr

sam’s linux study上一篇感慨文章

linux工程師悲哀

最近接連的幾個面試

讓我有非常的感觸

其實台灣大多數的軟體工作都是windows為主

linux的工作並不是那麼多

裏面又許多是linux device driver

因此本來linux的軟體工程師在台灣的生存就不容易

最近的面試中

很多面試主管都有一個相同的論調

雖然他們要找會linux的engineer

但是如果不能全面都可以的話

工程師的value就不高

這裡所謂的value又是指”除了linux外, 你還要作windows programming”

這往往讓我十分挫敗

但是我常常想到

往往一整間的windows engineer都不會linux

那個不算value不高….但是linux engineer不熟windows programming就是value不高

這種的評量標準我常常不能接受

或許windows是市佔率最高的OS

但是若你要找的是linux engineer, 為何要為難他不熟windows呢

今天還聽到一個有趣的說法

因為linux是open source的一個產物

任何人都可以拿到source code去看

因此他是很簡單的

但是windows因為不知道內部如何運作

所以windows的engineer比較厲害

linux的engineer只是去看code而已, windows的engineer卻都是厲害的hacker

我不知道這樣的說法對不對

不過讓我深深的想到

或許我真的不適合當個software engineer吧

認真思考自己的未來…..

———————————————-

感觉作者有些太悲观了,呵呵。做什么工作都会找到用武之地的。

sam’s linux study上一篇感慨文章

Linux2.6 内核的 Initrd 机制解析(from IBM developworks)

http://www.ibm.com/developerworks/cn/linux/l-k26initrd/

initrd 的英文含义是 boot loader initialized RAM disk,就是由 boot loader 初始化的内存盘。在 linux内核启动前, boot loader 会将存储介质中的 initrd 文件加载到内存,内核启动时会在访问真正的根文件系统前先访问该内存中的 initrd 文件系统。

Linux2.6 内核的 Initrd 机制解析(from IBM developworks)

将内核数据写到用户空间缓冲区的一般操作

内核空间中,不能像写应用程序一样直接把buffer(这是内核的内存)里直接将数据写到另一个缓冲区(用户空间的)里面,或直接从用户空间的缓冲区里读数据。
Linux 里使用FS 寄存器来保存kernel space 和 user space 的切换的状态。所以,如果你想手动的话,可以这样做:

mm_segment_t fs;
fs = get_fs();
set_fs(get_ds());
write_data_to_buf(buf);
set_fs(fs);

也就是先切换到用户空间, 把数据写道buf缓冲区里面,最后再切换回来。

内核的API提供了几个函数来完成切换,就是copy_to_user(), copy_from_user();它们的核心操作都是用汇编实现的代码 ,效率高。

将内核数据写到用户空间缓冲区的一般操作