|
|
Boost-Commit : |
From: sundman.anders_at_[hidden]
Date: 2008-05-24 15:48:57
Author: asundman
Date: 2008-05-24 15:48:56 EDT (Sat, 24 May 2008)
New Revision: 45736
URL: http://svn.boost.org/trac/boost/changeset/45736
Log:
* Impl. new distance function (manhattan)
* Added a unit test file with tests for dist_fun's and dbscan (copied from dbscan file).
* Added second version of euclid_dist function (euclid_dist_pretty). For development and benchmarking purposes.
* Added a speed bench mark (dfunctest.cpp) file for distance function.
Added:
sandbox/cluster/boost/algorithm/cluster/detail/lambda_result_of.hpp (contents, props changed)
sandbox/cluster/libs/algorithm/cluster/src/dfunctest.cpp (contents, props changed)
sandbox/cluster/libs/algorithm/cluster/src/unittests.cpp (contents, props changed)
Text files modified:
sandbox/cluster/boost/algorithm/cluster/dist_func.hpp | 54 ++++++++++++++++++++++++++++++++++++++-
1 files changed, 52 insertions(+), 2 deletions(-)
Added: sandbox/cluster/boost/algorithm/cluster/detail/lambda_result_of.hpp
==============================================================================
--- (empty file)
+++ sandbox/cluster/boost/algorithm/cluster/detail/lambda_result_of.hpp 2008-05-24 15:48:56 EDT (Sat, 24 May 2008)
@@ -0,0 +1,112 @@
+// Copyright 2004, 2005, 2006 Cryolite.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// Copyright Shunsuke Sogame 2007-2008.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// Copyright Yusuke Kajimoto 2007.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// This 'pathch' was provided by Shunsuke Sogame as a response to
+// a boost mailing list question about how to get the boost lambda and
+// boost fusion libraries to work toghether.
+#ifndef BOOST_PP_IS_ITERATING
+#ifndef BOOST_LAMBDA_RESULT_OF_HPP
+#define BOOST_LAMBDA_RESULT_OF_HPP
+
+
+#include <boost/preprocessor/facilities/intercept.hpp>
+#include <boost/preprocessor/iteration/iterate.hpp>
+#include <boost/preprocessor/repetition/enum_binary_params.hpp>
+#include <boost/preprocessor/repetition/enum_params.hpp>
+#include <boost/tuple/tuple.hpp>
+
+
+#if !defined(BOOST_LAMBDA_RESULT_OF_MAX_ARITY)
+#define BOOST_LAMBDA_RESULT_OF_MAX_ARITY 3
+#endif
+
+
+namespace boost {
+
+
+ template<class F>
+ struct result_of;
+
+
+ namespace lambda {
+
+ template<class T>
+ class lambda_functor;
+
+ }
+
+
+ namespace lambda_result_of_detail {
+
+ // rvalue
+ template<class A>
+ struct to_ref
+ {
+ typedef A const &type;
+ };
+
+ // lvalue
+ template<class A>
+ struct to_ref<A &>
+ {
+ typedef A &type;
+ };
+
+ }
+
+
+ // 0ary
+ template<class T>
+ struct result_of<lambda::lambda_functor<T>(void)>
+ {
+ typedef typename lambda::lambda_functor<T>::nullary_return_type type;
+ };
+
+ template<class T>
+ struct result_of<lambda::lambda_functor<T> const(void)> :
+ result_of<lambda::lambda_functor<T>(void)>
+ { };
+
+
+ // 1ary-
+#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, BOOST_LAMBDA_RESULT_OF_MAX_ARITY, <boost/algorithm/cluster/detail/lambda_result_of.hpp>))
+#include BOOST_PP_ITERATE()
+
+
+} // namespace boost
+
+
+#endif
+#else
+#define n BOOST_PP_ITERATION()
+
+
+template<class T, BOOST_PP_ENUM_PARAMS(n, class A)>
+struct result_of<lambda::lambda_functor<T>(BOOST_PP_ENUM_PARAMS(n, A))> :
+ T::template sig<
+ tuples::tuple<
+ BOOST_PP_ENUM_BINARY_PARAMS(n, typename lambda_result_of_detail::to_ref<A, >::type BOOST_PP_INTERCEPT)
+ >
+ >
+{ };
+
+template<class T, BOOST_PP_ENUM_PARAMS(n, class A)>
+struct result_of<lambda::lambda_functor<T> const(BOOST_PP_ENUM_PARAMS(n, A))> :
+ result_of<lambda::lambda_functor<T>(BOOST_PP_ENUM_PARAMS(n, A))>
+{ };
+
+
+#undef n
+#endif
Modified: sandbox/cluster/boost/algorithm/cluster/dist_func.hpp
==============================================================================
--- sandbox/cluster/boost/algorithm/cluster/dist_func.hpp (original)
+++ sandbox/cluster/boost/algorithm/cluster/dist_func.hpp 2008-05-24 15:48:56 EDT (Sat, 24 May 2008)
@@ -11,9 +11,14 @@
#include "boost/fusion/adapted.hpp"
#include "boost/fusion/algorithm.hpp"
-
+#include "boost/lambda/lambda.hpp"
#include "boost/bind.hpp"
+// This file is currently required to get Fusion and Lambda to
+// work together.
+#include "detail/lambda_result_of.hpp"
+
+
namespace boost { namespace algorithm { namespace cluster {
template<typename T1, typename T2>
@@ -31,11 +36,56 @@
),
boost::bind(std::multiplies<double>(), _1, _1)
),
- 0., std::plus<double>()
+ 0, std::plus<double>()
)
);
}
+template<typename T1, typename T2>
+double euclid_dist_pretty( const T1 & t1, const T2 & t2)
+{
+ using namespace boost::lambda;
+ return std::sqrt
+ (
+ static_cast<double>(
+ boost::fusion::fold
+ (
+ boost::fusion::transform
+ (
+ t1, t2, (_1 * _1)(_1 - _2)
+ ),
+ 0, _1 + _2
+ )
+ )
+ );
+}
+
+namespace impl {
+ template<typename T>
+ struct absdiff : std::binary_function<T, T, T>
+ {
+ T operator ()(const T & t1, const T & t2) const
+ {
+ return t1 < t2 ? t2 - t1 : t1 - t2;
+ }
+ };
+}
+
+template<typename T1, typename T2>
+double manhattan_dist( const T1 & t1, const T2 & t2)
+{
+ using namespace boost::lambda;
+
+ return boost::fusion::fold
+ (
+ boost::fusion::transform
+ (
+ t1, t2, impl::absdiff<double>()
+ ),
+ 0, _1 + _2
+ );
+}
+
}}}
#endif
Added: sandbox/cluster/libs/algorithm/cluster/src/dfunctest.cpp
==============================================================================
--- (empty file)
+++ sandbox/cluster/libs/algorithm/cluster/src/dfunctest.cpp 2008-05-24 15:48:56 EDT (Sat, 24 May 2008)
@@ -0,0 +1,84 @@
+#include "boost/algorithm/cluster/dist_func.hpp"
+#include "boost/date_time/posix_time/posix_time.hpp"
+
+#define ITER 500000
+#define REITER 1000
+
+template<typename T>
+void runTests(const T& tup1, const T& tup2, int iter);
+
+int main(int argc, char* argv[])
+{
+ using namespace boost;
+
+ std::cout << "std::pair<double, double> test" << std::endl;
+ runTests(std::make_pair(0,0), std::make_pair(0,1), ITER);
+ std::cout << std::endl;
+
+ std::cout << "tup2 test" << std::endl;
+ runTests(make_tuple(0,0), make_tuple(0,1), ITER);
+ std::cout << std::endl;
+
+ std::cout << "tup3 test" << std::endl;
+ runTests(make_tuple(0,0,0), make_tuple(0,1,2), ITER);
+ std::cout << std::endl;
+
+ std::cout << "tup4 test" << std::endl;
+ runTests(make_tuple(0,0,0,0), make_tuple(0,1,2,3), ITER);
+ std::cout << std::endl;
+
+ std::cout << "tup5 test" << std::endl;
+ runTests(make_tuple(0,0,0,0,0), make_tuple(0,1,2,3,4), ITER);
+ std::cout << std::endl;
+
+ std::cout << "tup6 test" << std::endl;
+ runTests(make_tuple(0,0,0,0,0,0), make_tuple(0,1,2,3,4,5), ITER);
+ std::cout << std::endl;
+
+ std::cout << "tup7 test" << std::endl;
+ runTests(make_tuple(0,0,0,0,0,0,0), make_tuple(0,1,2,3,4,5,6), ITER);
+ std::cout << std::endl;
+
+ std::cout << "tup8 test" << std::endl;
+ runTests(make_tuple(0,0,0,0,0,0,0,0), make_tuple(0,1,2,3,4,5,6,7), ITER);
+ std::cout << std::endl;
+
+ std::cout << "tup9 test" << std::endl;
+ runTests(make_tuple(0,0,0,0,0,0,0,0,0), make_tuple(0,1,2,3,4,5,6,7,8), ITER);
+ std::cout << std::endl;
+
+ std::cout << "tup10 test" << std::endl;
+ runTests(make_tuple(0, 0, 0, 0, 0, 0, 0, 0, 0, 0), make_tuple(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), ITER);
+ std::cout << std::endl;
+
+ return 0;
+}
+
+template<typename T>
+void runTests(const T& tup1, const T& tup2, int iter)
+{
+
+ boost::posix_time::ptime time1, time2;
+ double d[REITER];
+
+ // Euclid dist
+ time1 = boost::posix_time::microsec_clock::local_time();
+ for (int i = 0; i < 10*iter; ++i)
+ {
+ for(int j = 0; j < REITER; ++j)
+ d[j] = boost::algorithm::cluster::euclid_dist(tup1, tup2);
+ }
+ time2 = boost::posix_time::microsec_clock::local_time();
+ std::cout << "euclid_dist (" << d[0] << "): " << (time2 - time1) << std::endl;
+
+
+ // Euclid dist (pretty impl)
+ time1 = boost::posix_time::microsec_clock::local_time();
+ for (int i = 0; i < iter; ++i)
+ {
+ for(int j = 0; j < REITER; ++j)
+ d[j] = boost::algorithm::cluster::euclid_dist_pretty(tup1, tup2);
+ }
+ time2 = boost::posix_time::microsec_clock::local_time();
+ std::cout << "euclid_dist_pretty (" << d[0] << "): " << (time2 - time1) << std::endl;
+}
\ No newline at end of file
Added: sandbox/cluster/libs/algorithm/cluster/src/unittests.cpp
==============================================================================
--- (empty file)
+++ sandbox/cluster/libs/algorithm/cluster/src/unittests.cpp 2008-05-24 15:48:56 EDT (Sat, 24 May 2008)
@@ -0,0 +1,142 @@
+#include <boost/algorithm/cluster/dbscan.hpp>
+#include <boost/algorithm/cluster/dist_func.hpp>
+
+#include <boost/test/minimal.hpp>
+#include <vector>
+#include <cmath>
+
+void test_dbscan();
+void test_dist_fun();
+
+int test_main(int, char *[])
+{
+ test_dbscan();
+
+ test_dist_fun();
+
+ return 0;
+}
+
+void test_dbscan()
+{
+ using namespace boost::algorithm::cluster;
+ using namespace std;
+
+ typedef pair<float, float> two_tuple;
+ typedef vector<two_tuple> tuple_data;
+ typedef tuple_data::iterator tuple_data_iter;
+ typedef vector<tuple_data_iter> cluster;
+ typedef cluster_data<cluster> cluster_data;
+
+ tuple_data tuples(10);
+ BOOST_CHECK(10 == tuples.size());
+
+ for (size_t n = 0; n < 5; ++n)
+ tuples[n].second = 1.f;
+
+ cluster_data clustering;
+ BOOST_CHECK(clustering.empty());
+
+ float eps1 = 0.2f;
+ size_t min_points = 3;
+ clustering = dbscan<cluster>(
+ tuples.begin(), tuples.end(), eps1, min_points,
+ euclid_dist<two_tuple, two_tuple>);
+#if 0
+ cerr << "clusters=" << clustering.size() << "\n";
+ size_t c = 1;
+
+ for (cluster_data::iterator citer = clustering.begin();
+ citer != clustering.end();
+ ++citer)
+ {
+ cerr << "CLUSTER: " << c << "\n";
+ for (cluster::iterator it = citer->begin();
+ it != citer->end();
+ ++it)
+ {
+ cerr << " (" << (*it)->first << ", " << (*it)->second << ")\n";
+ }
+ ++c;
+ }
+#endif
+ BOOST_CHECK(2 == clustering.size());
+
+ float eps2 = 1.01f;
+ clustering = dbscan<cluster>(
+ tuples.begin(), tuples.end(), eps2, min_points,
+ euclid_dist<two_tuple, two_tuple>);
+
+#if 0
+ cerr << "clusters=" << clustering.size() << "\n";
+ c = 0;
+
+ for (cluster_data::iterator citer = clustering.begin();
+ citer != clustering.end();
+ ++citer)
+ {
+ cerr << "CLUSTER: " << c << "\n";
+ for (cluster::iterator it = citer->begin();
+ it != citer->end();
+ ++it)
+ {
+ cerr << " (" << (*it)->first << ", " << (*it)->second << ")\n";
+ }
+ ++c;
+ }
+#endif
+
+ BOOST_CHECK(1 == clustering.size());
+}
+
+
+void test_dist_fun()
+{
+ using namespace std;
+ using namespace boost;
+ using namespace boost::algorithm::cluster;
+
+ // Euclidian distance function tests
+ {
+ BOOST_CHECK(0 == euclid_dist(make_pair(0., 0.), make_pair(0., 0.)));
+ BOOST_CHECK(0 == euclid_dist(make_tuple(0., 0.), make_tuple(0., 0.)));
+ BOOST_CHECK(0 == euclid_dist(make_pair(0., 0.), make_tuple(0., 0.)));
+ BOOST_CHECK(0 == euclid_dist(make_tuple(0., 0.), make_pair(0., 0.)));
+ BOOST_CHECK(0 == euclid_dist(make_tuple(0., 0., 0.), make_tuple(0., 0., 0.)));
+ BOOST_CHECK(0 == euclid_dist
+ (
+ make_tuple(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
+ make_tuple(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
+ ));
+
+ BOOST_CHECK(0 == euclid_dist(make_pair(23, 42), make_pair(23, 42)));
+
+ BOOST_CHECK(5 == euclid_dist(make_pair(0, 0), make_pair(3, 4)));
+ BOOST_CHECK(5 == euclid_dist(make_pair(3, 4), make_pair(0, 0)));
+
+ BOOST_CHECK(5 == euclid_dist(make_tuple(0, 0), make_tuple(3, 4)));
+ BOOST_CHECK(5 == euclid_dist(make_tuple(3, 4), make_tuple(0, 0)));
+ }
+
+ // Manhattan distance function tests
+ {
+ BOOST_CHECK(0 == manhattan_dist(make_pair(0., 0.), make_pair(0., 0.)));
+ BOOST_CHECK(0 == manhattan_dist(make_tuple(0., 0.), make_tuple(0., 0.)));
+ BOOST_CHECK(0 == manhattan_dist(make_pair(0., 0.), make_tuple(0., 0.)));
+ BOOST_CHECK(0 == manhattan_dist(make_tuple(0., 0.), make_pair(0., 0.)));
+ BOOST_CHECK(0 == manhattan_dist(make_tuple(0., 0., 0.), make_tuple(0., 0., 0.)));
+ BOOST_CHECK(0 == manhattan_dist
+ (
+ make_tuple(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
+ make_tuple(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
+ ));
+
+ BOOST_CHECK(0 == manhattan_dist(make_pair(23, 42), make_pair(23, 42)));
+
+ BOOST_CHECK(7 == manhattan_dist(make_pair(0, 0), make_pair(3, 4)));
+ BOOST_CHECK(7 == manhattan_dist(make_pair(3, 4), make_pair(0, 0)));
+
+ BOOST_CHECK(7 == manhattan_dist(make_tuple(0, 0), make_tuple(3, 4)));
+ BOOST_CHECK(7 == manhattan_dist(make_tuple(3, 4), make_tuple(0, 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