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/

有效运用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应该指向单个元素，而不该指向一个数组。

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吧

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

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

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

blogspot.com又解除封锁了

今天查些资料，google到一篇blogspot.com上的文章，直接点击就进去了，竟然没有用到代理。

Linux kernel map(flash video)

Hello world!

Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!