[Olena-patches] milena r1682: Optimize accu::rank, fixes on accus

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-01-24 Matthieu Garrigues <garrigues@lrde.epita.fr> Optimize accu::rank, fixes on accus. * mln/accu/rank.hh: New. A faster version of accu::rank based on histo. * mln/accu/rank_bool.hh: Init nfalse to 0 in init(). * mln/accu/rank_naive.hh: Rename as... * mln/accu/rank_high_quant.hh: ...this. * mln/accu/median.hh: Remove duplicated operator<< (Already in concept/accumulator). * tests/accu/rank.cc: Test each rank of an accumulator. --- mln/accu/median.hh | 7 - mln/accu/rank.hh | 287 ++++++++++++++++++++++++++++++++++++++++++++ mln/accu/rank_bool.hh | 1 mln/accu/rank_high_quant.hh | 182 +++++++++++++++++++++++++++ tests/accu/rank.cc | 58 ++++++++ 5 files changed, 523 insertions(+), 12 deletions(-) Index: trunk/milena/tests/accu/rank.cc =================================================================== --- trunk/milena/tests/accu/rank.cc (revision 1681) +++ trunk/milena/tests/accu/rank.cc (revision 1682) @@ -31,20 +31,67 @@ */ #include <mln/accu/rank.hh> +#include <mln/value/int_u8.hh> -int main() -{ using namespace mln; - accu::rank_<int> accu(3, 5); - +template <typename A> +void fill(Accumulator<A>& accu_) +{ + A& accu = exact(accu_); + accu.take(2); accu.take(3); accu.take(1); accu.take(4); accu.take(5); + accu.take(5); accu.take(2); - mln_assertion(accu.to_result() == 4); + accu.take(5); +} +int main() +{ + { + accu::rank_<value::int_u8> accu(0, 8); + fill(accu); + mln_assertion(accu.to_result() == 1); + } + { + accu::rank_<value::int_u8> accu(1, 8); + fill(accu); + mln_assertion(accu.to_result() == 2); + } + { + accu::rank_<value::int_u8> accu(2, 8); + fill(accu); + mln_assertion(accu.to_result() == 2); + } + { + accu::rank_<value::int_u8> accu(3, 8); + fill(accu); + mln_assertion(accu.to_result() == 3); + } + { + accu::rank_<value::int_u8> accu(4, 8); + fill(accu); + mln_assertion(accu.to_result() == 4); + } + { + accu::rank_<value::int_u8> accu(5, 8); + fill(accu); + mln_assertion(accu.to_result() == 5); + } + { + accu::rank_<value::int_u8> accu(6, 8); + fill(accu); + mln_assertion(accu.to_result() == 5); + } + { + accu::rank_<value::int_u8> accu(7, 8); + fill(accu); + mln_assertion(accu.to_result() == 5); + } + { accu::rank_<bool> accu_bool(1, 5); accu_bool.take(true); accu_bool.take(true); @@ -53,3 +100,4 @@ accu_bool.take(false); mln_assertion(accu_bool == true); } +} Index: trunk/milena/mln/accu/rank_naive.hh (deleted) =================================================================== Index: trunk/milena/mln/accu/rank.hh =================================================================== --- trunk/milena/mln/accu/rank.hh (revision 0) +++ trunk/milena/mln/accu/rank.hh (revision 1682) @@ -0,0 +1,287 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_ACCU_RANK_HH +# define MLN_ACCU_RANK_HH + +/*! \file mln/accu/rank.hh + * + * \brief Define an rank accumulator. + */ + +# include <vector> +# include <mln/accu/internal/base.hh> +# include <mln/accu/histo.hh> +# include <mln/core/concept/meta_accumulator.hh> +# include <mln/trait/value_.hh> +# include <mln/util/pix.hh> +# include <mln/core/inplace.hh> + +namespace mln +{ + + namespace accu + { + + + /*! \brief Generic rank accumulator class. + * + * The parameter \c T is the type of values. + */ + template <typename T> + struct rank_ : public mln::accu::internal::base_< T, rank_<T> > + { + typedef T argument; + typedef T result; + typedef mln::value::set<T> S; + + rank_(unsigned k, unsigned n, const Value_Set<S>& s); + rank_(unsigned k, unsigned n); + + void init(); + void take(const argument& t); + void take(const rank_<T>& other); + void untake(const argument& t); + + unsigned card() const { return h_.sum(); } + + T to_result() const; + + protected: + + unsigned k_; // 0 <= k_ < n + unsigned n_; + + mutable accu::histo<S> h_; + const S& s_; // derived from h_ + + mutable std::size_t sum_minus_, sum_plus_; + + mutable bool valid_; + mutable std::size_t i_; // the median index + mutable argument t_; // the median value + + // Auxiliary methods + void update_() const; + void go_minus_() const; + void go_plus_() const; + }; + + + template <typename I> struct rank_< util::pix<I> >; + + + /*! + * \brief Meta accumulator for rank. + */ + struct rank : public Meta_Accumulator< rank > + { + template <typename T> + struct with + { + typedef rank_<T> ret; + }; + }; + + + + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename T> + inline + rank_<T>::rank_(unsigned k, unsigned n) + : k_(k), + n_(n), + h_(), + s_(h_.vset()) + { + mln_assertion(k_ < n_); + init(); + } + + + template <typename T> + inline + rank_<T>::rank_(unsigned k, unsigned n, const Value_Set<mln::value::set<T> >& s) + : k_(k), + n_(n), + h_(s), + s_(h_.vset()) + { + mln_assertion(k_ < n_); + init(); + } + + template <typename T> + inline + void rank_<T>::take(const argument& t) + { + h_.take(t); + + if (t < t_) + ++sum_minus_; + else if (t > t_) + ++sum_plus_; + + if (valid_) + valid_ = false; + } + + template <typename T> + inline + void + rank_<T>::take(const rank_<T>& other) + { + // h_ + h_.take(other.h_); + + // sum_minus_ + for (unsigned i = 0; i < i_; ++i) + sum_minus_ += other.h_[i]; + + // sum_plus_ + for (unsigned i = i_ + 1; i < h_.nvalues(); ++i) + sum_plus_ += other.h_[i]; + + if (valid_) + valid_ = false; + } + + + template <typename T> + inline + void + rank_<T>::untake(const argument& t) + { + mln_precondition(h_(t) != 0); + h_.untake(t); + + if (t < t_) + --sum_minus_; + else if (t > t_) + --sum_plus_; + + if (valid_) + valid_ = false; + } + + template <typename T> + inline + void + rank_<T>::update_() const + { + valid_ = true; + + if (h_.sum() == 0) + return; + + if (sum_minus_ > k_) + go_minus_(); + else + if ((sum_minus_ + h_[i_]) < k_) + go_plus_(); + else + if (h_[i_] == 0) + { + // go to the heaviest side + if (sum_plus_ > sum_minus_) + go_plus_(); + else + go_minus_(); // default when both sides are balanced + } + } + + template <typename T> + inline + void + rank_<T>::go_minus_() const + { + do + { + sum_plus_ += h_[i_]; + do + --i_; + while (h_[i_] == 0); + sum_minus_ -= h_[i_]; + } + while (sum_minus_ > k_); + t_ = s_[i_]; + } + + template <typename T> + inline + void + rank_<T>::go_plus_() const + { + do + { + sum_minus_ += h_[i_]; + do + ++i_; + while (h_[i_] == 0); + sum_plus_ -= h_[i_]; + } + while ((sum_minus_ + h_[i_]) < k_); + t_ = s_[i_]; + } + + template <typename T> + inline + void + rank_<T>::init() + { + h_.init(); + sum_minus_ = 0; + sum_plus_ = 0; + i_ = (s_.index_of(mln_max(argument)) + - s_.index_of(mln_min(argument))) / 2; + t_ = s_[i_]; + valid_ = true; + } + + template <typename T> + inline + T + rank_<T>::to_result() const + { + if (! valid_) + update_(); + return t_; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::accu + +} // end of namespace mln + +#include <mln/accu/rank_bool.hh> + +#endif // ! MLN_ACCU_RANK_HH Index: trunk/milena/mln/accu/median.hh =================================================================== --- trunk/milena/mln/accu/median.hh (revision 1681) +++ trunk/milena/mln/accu/median.hh (revision 1682) @@ -250,13 +250,6 @@ return h_; } - template <typename S> - inline - std::ostream& operator<<(std::ostream& ostr, const median<S>& m) - { - return ostr << m.to_result(); - } - # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::accu Index: trunk/milena/mln/accu/rank_high_quant.hh =================================================================== --- trunk/milena/mln/accu/rank_high_quant.hh (revision 0) +++ trunk/milena/mln/accu/rank_high_quant.hh (revision 1682) @@ -0,0 +1,182 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_ACCU_RANK_HH +# define MLN_ACCU_RANK_HH + +/*! \file mln/accu/rank.hh + * + * \brief Define an rank accumulator. + */ + +# include <vector> +# include <mln/accu/internal/base.hh> +# include <mln/core/concept/meta_accumulator.hh> +# include <mln/trait/value_.hh> +# include <mln/util/pix.hh> +# include <mln/core/inplace.hh> + +namespace mln +{ + + namespace accu + { + + + /*! \brief Generic rank accumulator class. + * + * The parameter \c T is the type of values. + */ + template <typename T> + struct rank_ : public mln::accu::internal::base_< T, rank_<T> > + { + typedef T argument; + typedef T result; + + rank_(unsigned k, unsigned n); + + void init(); + void take_as_init(const argument& t); + void take(const argument& t); + void take(const rank_<T>& other); + void sort(); + + T to_result() const; + + protected: + + std::vector<T> elts_; + bool is_sorted_; + unsigned k_; // 0 <= k_ < n + unsigned n_; + }; + + + template <typename I> struct rank_< util::pix<I> >; + + + /*! + * \brief Meta accumulator for rank. + */ + struct rank : public Meta_Accumulator< rank > + { + template <typename T> + struct with + { + typedef rank_<T> ret; + }; + }; + + + + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename T> + inline + rank_<T>::rank_(unsigned k, unsigned n) + : k_(k), + n_(n), + is_sorted_(false) + { + mln_assertion(k_ < n_); + init(); + } + + template <typename T> + inline + void + rank_<T>::init() + { + elts_.clear(); + } + + template <typename T> + inline + void rank_<T>::take_as_init(const argument& t) + { + elts_.push_back(t); + is_sorted_ = false; + } + + template <typename T> + inline + void rank_<T>::take(const argument& t) + { + elts_.push_back(t); + is_sorted_ = false; + } + + template <typename T> + inline + void + rank_<T>::take(const rank_<T>& other) + { + elts_.insert(elts_.end(), + other.elts_.begin(), + other.elts_.end()); + is_sorted_ = false; + } + + template <typename T> + inline + T + rank_<T>::to_result() const + { + // Fixme : Call to inplace to unconst (*this). + inplace(*this).sort(); + + if (n_ == elts_.size()) + return elts_[k_]; + else + // FIXME : This alternative is used to handle images edges. + return elts_[(elts_.size() * k_) / n_]; + } + + template <typename T> + inline + void + rank_<T>::sort() + { + if (!is_sorted_) + { + is_sorted_ = true; + std::sort(elts_.begin(), elts_.end()); + } + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::accu + +} // end of namespace mln + +#include <mln/accu/rank_bool.hh> + +#endif // ! MLN_ACCU_RANK_HH Index: trunk/milena/mln/accu/rank_bool.hh =================================================================== --- trunk/milena/mln/accu/rank_bool.hh (revision 1681) +++ trunk/milena/mln/accu/rank_bool.hh (revision 1682) @@ -90,6 +90,7 @@ void rank_<bool>::init() { + nfalse_ = 0; }