|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r73250 - in sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html: . reference reference/hash
From: cpp.cabrera_at_[hidden]
Date: 2011-07-20 04:57:31
Author: alejandro
Date: 2011-07-20 04:57:29 EDT (Wed, 20 Jul 2011)
New Revision: 73250
URL: http://svn.boost.org/trac/boost/changeset/73250
Log:
Added complexity descriptions for basic_bloom_filter and dynamic_bloom_filter. Added Lance M. Clark to acknowledgments. Added documentation for murmurhash3.
Text files modified:
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/acknowledgements.html | 1
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/index.html | 2
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/bloom.html | 2
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/dynamic_bloom.html | 96 ++++++++++++++++++++++++++++++++++-----
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/hash/default.html | 8 +-
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/hash/murmurhash3.html | 17 +++++--
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/testing.html | 4
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tutorial.html | 2
8 files changed, 105 insertions(+), 27 deletions(-)
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/acknowledgements.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/acknowledgements.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/acknowledgements.html 2011-07-20 04:57:29 EDT (Wed, 20 Jul 2011)
@@ -39,6 +39,7 @@
<li>Jakub Szymanski - for providing feed back relevant to the [de]serialzation of Bloom filters.</li>
<li>Phil Endecott - for providing a review of the earliest announced version of the Bloom filter and suggesting ideas for future improvement.</li>
<li>Dean Michael Berris - for having provided a starting point for the project and given advice that aided in crafting the initial prototype.</li>
+ <li>Lance M. Clark - for giving extensive feedback throughout the development of the documentation.</li>
</ul>
<hr/>
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/index.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/index.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/index.html 2011-07-20 04:57:29 EDT (Wed, 20 Jul 2011)
@@ -33,7 +33,7 @@
<h3 class="author">Alejandro Cabrera</h3>
<div class="toc">
- <p>Table of Contents</p>
+ <h2>Table of Contents</h2>
<ul>
<li>Tutorial</li>
<li>Reference</li>
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/bloom.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/bloom.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/bloom.html 2011-07-20 04:57:29 EDT (Wed, 20 Jul 2011)
@@ -135,7 +135,7 @@
</div>
<div class="toc">
- <p>Function Reference</p>
+ <h2>Function Reference</h2>
<ul>
<li>basic_bloom_filter()</li>
<li>basic_bloom_filter(start, end)</li>
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/dynamic_bloom.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/dynamic_bloom.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/dynamic_bloom.html 2011-07-20 04:57:29 EDT (Wed, 20 Jul 2011)
@@ -136,21 +136,23 @@
</ul>
<h2>Template Parameters Reference</h2>
- <dl>
- <dt>T</dt>
- <dd>The type used for all Bloom filter operations.</dd>
- <dt>HashFunctions</dt>
- <dd>The set of hash functions used by the Bloom filter. Currently required to be an mpl::vector of Hashers.</dd>
- <dt>Block</dt>
- <dd>Used internally by the <a href="http://www.boost.org/doc/libs/release/libs/dynamic_bitset/dynamic_bitset.html">
- dynamic bitset</a>.</dd>
- <dt>Allocator</dt>
- <dd>Used internally by the <a href="http://www.boost.org/doc/libs/release/libs/dynamic_bitset/dynamic_bitset.html">
- dynamic bitset</a>.</dd>
- </dl>
+ <div class="template_ref">
+ <dl>
+ <dt>T</dt>
+ <dd>The type used for all Bloom filter operations.</dd>
+ <dt>HashFunctions</dt>
+ <dd>The set of hash functions used by the Bloom filter. Currently required to be an mpl::vector of Hashers.</dd>
+ <dt>Block</dt>
+ <dd>Used internally by the <a href="http://www.boost.org/doc/libs/release/libs/dynamic_bitset/dynamic_bitset.html">
+ dynamic bitset</a>.</dd>
+ <dt>Allocator</dt>
+ <dd>Used internally by the <a href="http://www.boost.org/doc/libs/release/libs/dynamic_bitset/dynamic_bitset.html">
+ dynamic bitset</a>.</dd>
+ </dl>
+ </div>
<div class="toc">
- <p>Function Reference</p>
+ <h2>Function Reference</h2>
<ul>
<li>dynamic_bloom_filter()</li>
<li>dynamic_bloom_filter(capacity)</li>
@@ -186,6 +188,10 @@
<dd>Constructs a dynamic_bloom_filter object with all bits set to 0 and a default size determined by the underlying dynamic bitset.</dd>
<dt>Warning</dt>
<dd>Be sure to set the capacity using resize().</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html">
+ boost::dynamic_bitset()</a>.</dd>
</dl>
</div>
@@ -195,6 +201,10 @@
<dl>
<dt>Description</dt>
<dd>Constructs a dynamic_bloom_filter with all bits set to 0 and bit_capacity set to capacity.</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html">
+ boost::dynamic_bitset(size_t)</a>.</dd>
</dl>
</div>
@@ -204,6 +214,10 @@
<dl>
<dt>Description</dt>
<dd>Constructs a dynamic_bloom_filter by inserting all the elements in the range (start, end).</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(n)</span> and depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html">
+ boost::dynamic_bitset</a>.</dd>
</dl>
</div>
@@ -215,6 +229,8 @@
<dd>Returns the number of bits used internally by the Bloom filter.</dd>
<dt>Returns</dt>
<dd>this->bits.size()</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
</dl>
</div>
@@ -227,6 +243,8 @@
<dd>Returns the number of hash functions used by the Bloom filter.</dd>
<dt>Returns</dt>
<dd>mpl::size<HashFunctions>.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
</dl>
</div>
@@ -238,6 +256,8 @@
<dd>Returns the current false positive rate based upon the number of hash functions used (k), the number of bits available (m), and the number of bits set (n).</dd>
<dt>Returns</dt>
<dd>A double precision value calculated as (1 - e^(k*n/m))^k.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
</dl>
</div>
@@ -249,6 +269,10 @@
<dd>Returns true if no elements have been inserted into the Bloom filter.</dd>
<dt>Returns</dt>
<dd>this->bits.count() == 0</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html">
+ boost::dynamic_bitset.empty()</a>.</dd>
</dl>
</div>
@@ -260,6 +284,10 @@
<dd>Returns the number of bits currently set in the Bloom filter.</dd>
<dt>Returns</dt>
<dd>this->bits.count().</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html">
+ boost::dynamic_bitset.count()</a>.</dd>
</dl>
</div>
@@ -271,6 +299,8 @@
<dd>Inserts an element into the Bloom filter.</dd>
<dt>Post-condition</dt>
<dd>At least 1 bit and at most num_hash_functions() bits of the Bloom filter will have been set.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(k)</span>.</dd>
</dl>
</div>
@@ -282,6 +312,8 @@
<dd>Inserts all elements in range (start, end).</dd>
<dt>Post-condition</dt>
<dd>At least n bits and at most (n * num_hash_functions()) bits of the Bloom filter will have been set, where n = distance(start, end).</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(n*k)</span>.</dd>
</dl>
</div>
@@ -295,6 +327,8 @@
<dd>True if all hash functions agree with the bitset; false otherwise.</dd>
<dt>Warning</dt>
<dd>It may return a false positive if there are hash collisions - this means that depending on the Size of the Bloom filter and the hash functions used, there is a probability that the Bloom filter will return true even though the element was never inserted.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(k)</span>.</dd>
</dl>
</div>
@@ -306,6 +340,10 @@
<dd>Sets all bits in the Bloom filter to 0, effectively canceling all insertions.</dd>
<dt>Post-condition</dt>
<dd>this->count() == 0</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
+ boost::dynamic_bitset.clear()</a>.</dd>
</dl>
</div>
@@ -315,6 +353,8 @@
<dl>
<dt>Description</dt>
<dd>Swaps the bits and the bit capacity in this Bloom filter with the argument Bloom filter.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
</dl>
</div>
@@ -326,6 +366,10 @@
<dd>Changes the capacity of the Bloom filter to new_capacity.</dd>
<dt>Warning</dt>
<dd>All bits are set to 0 (all inserts are lost) - resize wisely.</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
+ boost::dynamic_bitset.resize()</a>.</dd>
</dl>
</div>
@@ -341,6 +385,10 @@
<dd>Returns a reference to <code class="c_keyword">this</code>.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in <code class="c_keyword">this</code> will be greater than or equal to the number of bits set before the operation.</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
+ boost::dynamic_bitset.operator|=()</a>.</dd>
</dl>
</div>
@@ -356,6 +404,10 @@
<dd>Returns a reference to <code class="c_keyword">this</code>.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in <code class="c_keyword">this</code> will be less than or equal to the number of bits set before the operation.</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
+ boost::dynamic_bitset.operator&=()</a>.</dd>
</dl>
</div>
@@ -371,6 +423,10 @@
<dd>Returns a new, stack-allocated Bloom filter that is the result of performing a union between the lhs and the rhs.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in the new filter will be greater than or equal to the number of bits set in max(lhs.count(), rhs.count()).</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
+ boost::dynamic_bitset.operator|()</a>.</dd>
</dl>
</div>
@@ -386,6 +442,10 @@
<dd>Returns a new, stack-allocated Bloom filter that is the result of performing an intersect between the lhs and the rhs.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in the new filter will be less than or equal to the number of bits set in min(lhs.count(), rhs.count()).</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
+ boost::dynamic_bitset.operator&()</a>.</dd>
</dl>
</div>
@@ -395,6 +455,8 @@
<dl>
<dt>Description</dt>
<dd>Swaps the bits and the bit capacity between the argument Bloom filters.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span></dd>
</dl>
</div>
@@ -406,6 +468,10 @@
<dd>Compares the bits of the argument Bloom filters for equality.</dd>
<dt>Returns</dt>
<dd>True if the bits match, false otherwise.</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
+ boost::dynamic_bitset.operator==()</a>.</dd>
</dl>
</div>
@@ -417,6 +483,10 @@
<dd>Compares the bits of the argument Bloom filters for equality.</dd>
<dt>Returns</dt>
<dd>True if the bits don't match, false otherwise.</dd>
+ <dt>Complexity</dt>
+ <dd>Depends on the implementation of
+ <a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
+ boost::dynamic_bitset.operator!=()</a>.</dd>
</dl>
</div>
<hr/>
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/hash/default.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/hash/default.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/hash/default.html 2011-07-20 04:57:29 EDT (Wed, 20 Jul 2011)
@@ -33,15 +33,15 @@
<a accesskey="h" href="../../index.html">
<img src="../../../../../../doc/src/images/home.png" alt="Home"/>
</a>
- <a accesskey="n" href="../../testing.html">
+ <a accesskey="n" href="murmurhash3.html">
<img src="../../../../../../doc/src/images/next.png" alt="Next"/>
</a>
</div>
<h1 class="title">Default Hash Function</h1>
<div class="listing">
- <code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_id">T</code>, <code class="c_type">size_t</code> <code class="c_id">Size</code>>
- <code class="c_keyword">struct</code> <code class="c_id">boost_hash</code> {
+ <code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_type">T</code>, <code class="c_type">size_t</code> <code class="c_id">Size</code>>
+ <code class="c_keyword">struct</code> <code class="c_type">boost_hash</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>) const;
};
</div>
@@ -60,7 +60,7 @@
<a accesskey="h" href="../../index.html">
<img src="../../../../../../doc/src/images/home.png" alt="Home"/>
</a>
- <a accesskey="n" href="../../testing.html">
+ <a accesskey="n" href="murmurhash3.html">
<img src="../../../../../../doc/src/images/next.png" alt="Next"/>
</a>
</div>
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/hash/murmurhash3.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/hash/murmurhash3.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/hash/murmurhash3.html 2011-07-20 04:57:29 EDT (Wed, 20 Jul 2011)
@@ -24,7 +24,7 @@
<hr/>
<div class="spirit-nav">
- <a accesskey="p" href="../dynamic_bloom.html">
+ <a accesskey="p" href="default.html">
<img src="../../../../../../doc/src/images/prev.png" alt="Prev"/>
</a>
<a accesskey="u" href="../../reference.html">
@@ -38,15 +38,22 @@
</a>
</div>
- <h1 class="title">Default Hash Function</h1>
+ <h1 class="title">Murmurhash3 Hasher</h1>
<div class="listing">
- <code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_id">T</code>, <code class="c_type">size_t</code> <code class="c_id">Size</code>>
- <code class="c_keyword">struct</code> <code class="c_id">boost_hash</code> {
+ <code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_type">T</code>, <code class="c_type">size_t</code> <code class="c_id">Size</code> = 0, <code class="c_type">bool</code> <code class="c_id">Use128Mode</code> = 0>
+ <code class="c_keyword">struct</code> <code class="c_type">murmurhash3</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>) const;
};
</div>
<p>
- A generic Hasher provided by using boost::functional::hash_value. Used by the Bloom filter as a default template parameter for HashFunctions.
+ A Hasher that uses the public domain
+ <a href="http://code.google.com/p/smhasher/wiki/MurmurHash3">murmurhash3
+ </a> under the covers. This hash function excels where speed is the
+ desired goal. The Seed parameter is merely added to the result. The
+ Use128Mode template parameter determines whether the 128-bit hash is
+ calculated or not. This mode is theoretically fastest in 64-bit mode.
+ Only the least significant (32/64) bits are used in the case of 128-bit
+ mode.
</p>
<hr/>
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/testing.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/testing.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/testing.html 2011-07-20 04:57:29 EDT (Wed, 20 Jul 2011)
@@ -24,7 +24,7 @@
<hr/>
<div class="spirit-nav">
- <a accesskey="p" href="reference/hash/default.html">
+ <a accesskey="p" href="reference/hash/murmurhash3.html">
<img src="../../../../doc/src/images/prev.png" alt="Prev"/>
</a>
<a accesskey="h" href="index.html">
@@ -54,7 +54,7 @@
<hr/>
<div class="spirit-nav">
- <a accesskey="p" href="reference/hash/default.html">
+ <a accesskey="p" href="reference/hash/murmurhash3.html">
<img src="../../../../doc/src/images/prev.png" alt="Prev"/>
</a>
<a accesskey="h" href="index.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-20 04:57:29 EDT (Wed, 20 Jul 2011)
@@ -38,7 +38,7 @@
<h2 class="title">Tutorial</h2>
<div class="toc">
- <p>Table of Contents</p>
+ <h2>Table of Contents</h2>
<ul>
<li>Quick Start</li>
<li>Controlling the False Positive Rate</li>
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