|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r72500 - in sandbox/bloom_filter/trunk/libs/bloom_filter: doc/html doc/html/style example
From: cpp.cabrera_at_[hidden]
Date: 2011-06-08 22:00:53
Author: alejandro
Date: 2011-06-08 22:00:53 EDT (Wed, 08 Jun 2011)
New Revision: 72500
URL: http://svn.boost.org/trac/boost/changeset/72500
Log:
Added example programs demonstrated in listings to example repository. Updated CSS rules to include syntax highlighting for string literals. Updated tutorial to correct errors in listing code.
Added:
sandbox/bloom_filter/trunk/libs/bloom_filter/example/advanced_bloom.cpp (contents, props changed)
sandbox/bloom_filter/trunk/libs/bloom_filter/example/basic_bloom.cpp (contents, props changed)
Text files modified:
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/style/my.css | 4 ++
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tutorial.html | 69 ++++++++++++++++++++++++++-------------
2 files changed, 49 insertions(+), 24 deletions(-)
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/style/my.css
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/style/my.css (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/style/my.css 2011-06-08 22:00:53 EDT (Wed, 08 Jun 2011)
@@ -73,3 +73,7 @@
.c_func {
color: blue;
}
+
+.c_str {
+ color: purple;
+}
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tutorial.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tutorial.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tutorial.html 2011-06-08 22:00:53 EDT (Wed, 08 Jun 2011)
@@ -57,15 +57,24 @@
<code class="c_keyword">using namespace</code> <code class="c_namespace">std</code>;
<code class="c_type">int</code> <code class="c_func">main</code>() {
- <code class="c_type"> bloom_filter</code><int, 512> <code class="c_id">bloom</code>;
+ <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">INSERT_MAX</code> = 5000;
+ <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">CONTAINS_MAX</code> = 10000;
+ <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">NUM_BITS</code> = 512;
- <code class="c_keyword"> for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = 0; i < 5000; ++i) {
- bloom.insert(i);
- }
-
- <code class="c_keyword"> for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = 5000; i < 10000; ++i) {
- <code class="c_keyword">if</code> (bloom.contains(i)) cout << "collision" << endl;
- }
+ <code class="c_type">bloom_filter</code><int, NUM_BITS> <code class="c_id">bloom</code>;
+ <code class="c_type">size_t</code><code class="c_id"> collisions</code> = 0;
+
+ <code class="c_keyword">for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = 0; i < INSERT_MAX; ++i) {
+ bloom.insert(i);
+ }
+
+ <code class="c_keyword">for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = INSERT_MAX; i < CONTAINS_MAX; ++i) {
+ <code class="c_keyword">if</code> (bloom.contains(i)) cout << "collision" << endl;
+ }
+
+ cout << <code class="c_str">"collisions: "</code>
+ << collisions
+ << endl;
<code class="c_keyword">return</code> 0;
}
@@ -109,8 +118,10 @@
</div>
<p>
Note that the template parameter Seed isn't strictly required, as
- long as some form of seeding is present in the Hasher object. Now
- we can use a richer Bloom filter:
+ long as some form of seeding is present in the Hasher object. By
+ default, boost_hash is defined for users in
+ boost/bloom_filter/hash/default.hpp. This can be used to define
+ Bloom filters with additonal hashing functions easily, as demonstrated below:
</p>
<div class="listing">
@@ -121,26 +132,36 @@
<code class="c_keyword">using namespace</code> <code class="c_namespace">std</code>;
<code class="c_type">int</code> <code class="c_func">main</code>() {
- <code class="c_keyword">typedef</code> <code class="c_namespace">boost::mpl::vector</code><<code class="c_type">Hasher</code><<code class="c_id">int, 1</code>>,
- <code class="c_type">Hasher</code><<code class="c_id">int, 2</code>>,
- <code class="c_type">Hasher</code><<code class="c_id">int, 3</code>> > <code class="c_type">HashFns</code>;
- <code class="c_type"> bloom_filter</code><int, 1024, HashFns> <code class="c_id">bloom</code>;
-
- cout << "false positive rate: "
- << bloom.false_positive_rate()
- << endl;
+ <code class="c_keyword">typedef</code> <code class="c_namespace">boost::mpl::vector</code><<code class="c_type">boost_hash</code><<code class="c_id">int, 1</code>>,
+ <code class="c_type">boost_hash</code><<code class="c_id">int, 2</code>>,
+ <code class="c_type">boost_hash</code><<code class="c_id">int, 3</code>> > <code class="c_type">HashFns</code>;
+
+ <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">INSERT_MAX</code> = 5000;
+ <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">CONTAINS_MAX</code> = 10000;
+ <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">NUM_BITS</code> = 1024;
+
+ <code class="c_type">bloom_filter</code><int, NUM_BITS, HashFns> <code class="c_id">bloom</code>;
+ <code class="c_type">size_t</code><code class="c_id"> collisions</code> = 0;
+
+ cout << <code class="c_str">"false positive rate: "</code>
+ << bloom.false_positive_rate()
+ << endl;
- <code class="c_keyword">for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = 0; i < 5000; ++i) {
+ <code class="c_keyword">for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = 0; i < INSERT_MAX; ++i) {
bloom.insert(i);
}
- <code class="c_keyword">for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = 5000; i < 10000; ++i) {
- <code class="c_keyword">if</code> (bloom.contains(i)) cout << "collision" << endl;
+ <code class="c_keyword">for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = INSERT_MAX; i < CONTAINS_MAX; ++i) {
+ <code class="c_keyword">if</code> (bloom.contains(i)) ++collisions;
}
- cout << "false positive rate: "
- << bloom.false_positive_rate()
- << endl;
+ cout << <code class="c_str">"false positive rate: "</code>
+ << bloom.false_positive_rate()
+ << endl;
+
+ cout << <code class="c_str">"collisions: "</code>
+ << collisions
+ << endl;
<code class="c_keyword">return</code> 0;
}
Added: sandbox/bloom_filter/trunk/libs/bloom_filter/example/advanced_bloom.cpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/example/advanced_bloom.cpp 2011-06-08 22:00:53 EDT (Wed, 08 Jun 2011)
@@ -0,0 +1,38 @@
+// advanced Boost.BloomFilter program
+#include <boost/bloom_filter/bloom.hpp>
+#include <iostream>
+using namespace boost::bloom_filter;
+using namespace std;
+
+int main () {
+ typedef boost::mpl::vector<boost_hash<int, 1>,
+ boost_hash<int, 2>,
+ boost_hash<int, 3> > HashFns;
+
+ static const size_t INSERT_MAX = 5000;
+ static const size_t CONTAINS_MAX = 10000;
+ static const size_t NUM_BITS = 1024;
+
+ bloom_filter<int, NUM_BITS, HashFns> bloom;
+ size_t collisions = 0;
+
+ cout << "false positive rate: "
+ << bloom.false_positive_rate()
+ << endl;
+
+ for (int i = 0; i < INSERT_MAX; ++i) {
+ bloom.insert(i);
+ }
+
+ for (int i = INSERT_MAX; i < CONTAINS_MAX_MAX; ++i) {
+ if (bloom.contains(i)) ++collisions;
+ }
+
+ cout << "false positive rate: "
+ << bloom.false_positive_rate()
+ << endl;
+
+ cout << "collisions: " << collisions << endl;
+
+ return 0;
+}
Added: sandbox/bloom_filter/trunk/libs/bloom_filter/example/basic_bloom.cpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/example/basic_bloom.cpp 2011-06-08 22:00:53 EDT (Wed, 08 Jun 2011)
@@ -0,0 +1,26 @@
+// introductory Boost.BloomFilter program
+#include <boost/bloom_filter/bloom.hpp>
+#include <iostream>
+using namespace boost::bloom_filter;
+using namespace std;
+
+int main () {
+ static const size_t INSERT_MAX = 5000;
+ static const size_t CONTAINS_MAX = 10000;
+ static const size_t NUM_BITS = 512;
+
+ bloom_filter<int, NUM_BITS> bloom;
+ size_t collisions = 0;
+
+ for (int i = 0; i < INSERT_MAX; ++i) {
+ bloom.insert(i);
+ }
+
+ for (int i = INSERT_MAX; i < CONTAINS_MAX_MAX; ++i) {
+ if (bloom.contains(i)) ++collisions;
+ }
+
+ cout << "collisions: " << collisions << endl;
+
+ return 0;
+}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk