Subject: [Boost-commit] svn:boost r73233 - in sandbox/bloom_filter/trunk/libs/bloom_filter: benchmark doc/html doc/html/style doc/html/tut
From: cpp.cabrera_at_[hidden]
Date: 2011-07-19 02:38:35
Author: alejandro
Date: 2011-07-19 02:38:34 EDT (Tue, 19 Jul 2011)
New Revision: 73233
URL: http://svn.boost.org/trac/boost/changeset/73233
Log:
Added margins to documentation paragraphs in CSS rules. Moved advanced example in tutorial to hashers section. Added a few local ignore rules for benchmarks.
Added:
sandbox/bloom_filter/trunk/libs/bloom_filter/benchmark/.gitignore (contents, props changed)
Text files modified:
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/style/my.css | 13 +++++++
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/hashers.html | 70 ++++++++++++++++++++++++++++++++++++++
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tutorial.html | 72 ---------------------------------------
3 files changed, 84 insertions(+), 71 deletions(-)
Added: sandbox/bloom_filter/trunk/libs/bloom_filter/benchmark/.gitignore
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/benchmark/.gitignore 2011-07-19 02:38:34 EDT (Tue, 19 Jul 2011)
@@ -0,0 +1,3 @@
+bloom_insert
+stdhash_insert
+stdset_insert
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-07-19 02:38:34 EDT (Tue, 19 Jul 2011)
@@ -9,6 +9,15 @@
* See http://www.boost.org/libs/bloom_filter for documentation.
*
******************************************************************************/
+
+.toc
+{
+ margin: 0 4% 0 4%;
+ padding: 0 1pc 0.5pc 1pc;
+ font-size: 80%;
+ line-height: 1.15;
+}
+
.toc ul, .toc li {padding: 0; list-style:none;}
.toc ul {margin: 0 0 0 0;}
.toc p {font-weight: bold;}
@@ -37,6 +46,10 @@
margin-right: 7%;
}
+p {
+ margin: 1% 1%;
+}
+
.listing {
white-space: pre;
background: #d0d0d0;
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/hashers.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/hashers.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/hashers.html 2011-07-19 02:38:34 EDT (Tue, 19 Jul 2011)
@@ -40,6 +40,76 @@
<h1 class="title">Customizing Hash Functions</h1>
+ <p>
+ A Hasher is a function object that overloads operator() such that the following interface is satisfied:
+ </p>
+
+ <div class="listing">
+ <code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_type">T</code>>
+ <code class="c_keyword">struct</code> <code class="c_id">ExampleHasher</code> {
+ <code class="c_type">size_t</code> <code class="c_func">operator</code>()(<code class="c_keyword">const</code> <code class="c_type">T</code>&) <code class="c_keyword">const</code>;
+ };
+ </div>
+ <p>
+ In practice, it would be wise to also provide a Seed template parameter. 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">
+ <code class="c_comment">// link: advanced_bloom.cpp</code>
+ <code class="c_comment">// advanced Boost.BloomFilter program</code>
+ <code class="c_keyword">#include</code> <code class="c_include"><boost/bloom_filter/basic_bloom_filter.hpp></code>
+ <code class="c_keyword">#include</code> <code class="c_include"><iostream></code>
+ <code class="c_keyword">using namespace</code> <code class="c_namespace">boost::bloom_filters</code>;
+ <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">boost_hash</code><<code class="c_type">int, 0</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> = 8192;
+
+ <code class="c_type">basic_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">"bloom filter storage size: "</code>
+ << sizeof(bloom) << <code class="c_str">" bytes"</code>
+ << endl;
+
+ cout << <code class="c_str">"false positive rate: "</code>
+ << bloom.false_positive_rate() * 100.0 << <code class="c_str">"%"</code>
+ << endl;
+
+ <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.probably_contains(i)) ++collisions;
+ }
+
+ cout << <code class="c_str">"false positive rate: "</code>
+ << bloom.false_positive_rate() * 100.0 << <code class="c_str">"%"</code>
+ << endl;
+
+ cout << <code class="c_str">"collisions (false positives): "</code>
+ << collisions
+ << endl;
+
+ <code class="c_keyword">return</code> 0;
+ }
+ </div>
+ <div class="example_output">
+ $> ./advanced_bloom
+ bloom filter storage size: 1024 bytes
+ false positive rate before inserts: 0%
+ false positive rate after inserts: 45.684%
+ collisions (false positives): 1808
+ </div>
+
<hr/>
<div class="spirit-nav">
<a accesskey="p" href="false_positive.html">
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-07-19 02:38:34 EDT (Tue, 19 Jul 2011)
@@ -47,7 +47,7 @@
<li>Inserting Elements</li>
<li>Querying Elements</li>
<li>Removing Elements</li>
- <li>Tips & Warnings</li>
+ <li>Tips & Best Practices</li>
</ul>
</div>
@@ -101,76 +101,6 @@
</li>
</ul>
- <p>
- A Hasher is a function object that overloads operator() such that the following interface is satisfied:
- </p>
-
- <div class="listing">
- <code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_type">T, Seed</code>>
- <code class="c_keyword">struct</code> <code class="c_id">ExampleHasher</code> {
- <code class="c_type">size_t</code> <code class="c_func">operator</code>()(<code class="c_keyword">const</code> <code class="c_type">T</code>&) <code class="c_keyword">const</code>;
- };
- </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. 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">
- <code class="c_comment">// link: advanced_bloom.cpp</code>
- <code class="c_comment">// advanced Boost.BloomFilter program</code>
- <code class="c_keyword">#include</code> <code class="c_include"><boost/bloom_filter/basic_bloom_filter.hpp></code>
- <code class="c_keyword">#include</code> <code class="c_include"><iostream></code>
- <code class="c_keyword">using namespace</code> <code class="c_namespace">boost::bloom_filters</code>;
- <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">boost_hash</code><<code class="c_type">int, 0</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> = 8192;
-
- <code class="c_type">basic_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">"bloom filter storage size: "</code>
- << sizeof(bloom) << <code class="c_str">" bytes"</code>
- << endl;
-
- cout << <code class="c_str">"false positive rate: "</code>
- << bloom.false_positive_rate() * 100.0 << <code class="c_str">"%"</code>
- << endl;
-
- <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.probably_contains(i)) ++collisions;
- }
-
- cout << <code class="c_str">"false positive rate: "</code>
- << bloom.false_positive_rate() * 100.0 << <code class="c_str">"%"</code>
- << endl;
-
- cout << <code class="c_str">"collisions (false positives): "</code>
- << collisions
- << endl;
-
- <code class="c_keyword">return</code> 0;
- }
- </div>
- <div class="example_output">
- $> ./advanced_bloom
- bloom filter storage size: 1024 bytes
- false positive rate before inserts: 0%
- false positive rate after inserts: 45.684%
- collisions (false positives): 1808
- </div>
<p>
All the details of insertion and querying the Bloom filter are handled