boost 的 bloom filter 的实现

我们来仔细看看 boost.bloom_filter 是如何设计这个 C++ 的 library 的。

实现一个 bloom filter 需要提供:

  • value_type,key_type 表示 key 的类型,模板的第一个参数传入
  • hash_function_type 表示使用一组 hash function,模板的第二个参数传入,用 boost::mpl::vector 将若干个 hash function 组合起来
  • apply_hash_type 这大概是一个当作 traits 来使用的类

现说说这个 boost.bloom_filter 的问题:

  • 没有扩展性,尽管有一定的抽象了,但是似乎没有通过一些技巧将几种 bloom filter 统一的表征出来,这使得每个特定的类,如 basic_bloom_filter 与 counting_bloom_filter 能 share 的 code 非常少
  • apply_hash_type 其实是为每种不同的 bloom filter 单独写的,但是使用的时候却不和 traits 类一样,显得很别扭

这里有一些值得借鉴的地方是它灵活的使用了一些现有的容器帮助我们存放 hash table:

  • std::bitset 用在 basic_bloom_filter 里面,
  • boost::array 用在 counting_bloom_filter 里面,
  • 而 dynamic_bloom_filter 就使用了 boost::dynamic_bitset

那么如果希望实现一个更加 general 的 bloom filter,我们大概有如下的想法:

  • 容器和不同的操作其实是 couple 的,但是容器是单独设计出来的,我们需要将这些操作为这些对应容器提供出来,表达相应的 knowledge,比较简单的还是通过 traits 的设计
  • 一个公用的 template,通过给定的参数选择容器,并应用默认的 traits,这个 template 在 traits 的接口上实现一般性的 bloom filter
  • typedef 一些常用的 bloom filter,也可以算用 generator 吧,比如 basic_bloom_filter、counting_bloom_filter 等

这样做利于:如果有一些对容器的扩展,比较容易通过 template specification 实现扩展;通过添加新的 generator 就能获得定制过的 bloom filter 了。

template <std::size_t M, std::size_t B>
struct container_selector {
  // in general we use boost::array
  typedef boost::array<M, ...> ContainerType ;
} ;
template <std::size_t M>
struct container_selector<M, 1> {
  typedef std::bitset<M> ContainerType ;
} ;
template <>
struct container_selector<0, 1> {
  typedef boost::dynamic_bitset ContainerType ;
} ;
// maybe some other container for special use?

template <class Container>
struct container_traits {
} ;
// many specifications

// the general template
template <class T, std::size_t M, class HashFns=boost::mpl::vector<boost_hash<T> >,
          std::size_t B = 1,
          class Container=container_selector<M, B>::ContainerType,
          class ContainerTraits=container_traits<Container> >
struct bloom_filter {
} ;

// some specific bloom filters
template <class T, std::size_t M, class HashFns=boost::mpl::vector<boost_hash<T> > >
struct basic_bloom_filter {
  typedef bloom_filter<T, M, HashFns> type ;
} ;
template <class T, std::size_t M, std::size_t B = 2, class HashFns=boost::mpl::vector<boost_hash<T> >>
struct counting_bloom_filter {
 BOOST_STATIC_ASSERT (B > 1) ;
 typedef bloom_filter<T, M, HashFns, B> type ;
} ;

// for users
typename basic_bloom_filter<std::string, 1000>::type bloom1 ;
typename counting_bloom_filter<std::string, 1000, 3>::type bloom2 ;

比较有意思的是怎么区分 counting 和 non-counting 有没有 remove 这种方法,其实这可以用所谓的 SFINAE,大概就是说我们可以按照有 remove 方法来实现,但是对应应该调用 traits 里面某个方法来实现,我们可以为 non-counting 的容器不提供对应方法,这样就使得对 non-counting bloom filter 调用 remove 产生编译错误了。不晓得是不是可以按照这个思路参考 boost.bloom_filter 来重新实现一下?

——————
And it came to pass, before he had done speaking, that, behold, Rebekah came out, who was born to Bethuel, son of Milcah, the wife of Nahor, Abraham’s brother, with her pitcher upon her shoulder.

Advertisements
boost 的 bloom filter 的实现

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s