URL:
https://svn.lrde.epita.fr/svn/oln/trunk/milena
ChangeLog:
2008-01-24 Matthieu Garrigues <garrigues(a)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;
}