[mpl] sort algorithm complexity
In the page it is informed that sort has an average complexity of O(nlog n), but I'm writing this: template <typename T, typename U> struct sort_hierarchy_pred : mpl::not_< boost::is_base_and_derived<T, U> >::type { }; typedef mpl::back_inserter< mpl::vector<> > aux_in; template <typename SequenceT> struct sort_hierarchies : public mpl::sort<SequenceT, typename mpl::lambda<sort_hierarchy_pred<mpl::_, mpl::_> >::type , aux_in> {}; and for a sequence of 5 or more, the compile time and memory usage gets too huge. To became unuseable. What I'm trying to achieve is a sequence of types that are sorted with the bases first... Could anybody shed some light why and if there's some workaround this? thanks in advance, Felipe. -- Felipe Magno de Almeida Developer from synergy and Computer Science student from State University of Campinas(UNICAMP). Unicamp: http://www.ic.unicamp.br Synergy: http://www.synergy.com.br "There is no dark side of the moon really. Matter of fact it's all dark."
On 8/5/05, Felipe Magno de Almeida <felipe.m.almeida@gmail.com> wrote:
template <typename T, typename U> struct sort_hierarchy_pred : mpl::not_< boost::is_base_and_derived<T, U>
::type { };
Sorry, already discovered the problem. (I had searched for some time the problem a while ago and just found out now). It seems to be the >::type, that way I think it will evaluate is_base_and_derived even when not needed, turning it in a O(n^2) complexity. The mpl::not makes no sense either, and is faulting a typename before mpl::not if I was to use >::type. It is incredible I passed so much time to find this. -- Felipe Magno de Almeida Developer from synergy and Computer Science student from State University of Campinas(UNICAMP). Unicamp: http://www.ic.unicamp.br Synergy: http://www.synergy.com.br "There is no dark side of the moon really. Matter of fact it's all dark."
On 8/5/05, Felipe Magno de Almeida <felipe.m.almeida@gmail.com> wrote:
The mpl::not makes no sense either, and is faulting a typename before mpl::not if I was to use >::type.
the typename makes no sense, as I never saw an integral constant as a base class. -- Felipe Magno de Almeida Developer from synergy and Computer Science student from State University of Campinas(UNICAMP). Unicamp: http://www.ic.unicamp.br Synergy: http://www.synergy.com.br "There is no dark side of the moon really. Matter of fact it's all dark."
Felipe Magno de Almeida <felipe.m.almeida@gmail.com> writes:
In the page it is informed that sort has an average complexity of O(nlog n), but I'm writing this:
template <typename T, typename U> struct sort_hierarchy_pred : mpl::not_< boost::is_base_and_derived<T, U> >::type { };
I don't think that's a valid strict weak ordering criterion, because for two classes unrelated by inheritance it produces true in either argument order.
typedef mpl::back_inserter< mpl::vector<> > aux_in; template <typename SequenceT> struct sort_hierarchies : public mpl::sort<SequenceT,
^^^^^^ It's up to you of course, but I'd leave that out.
typename mpl::lambda<sort_hierarchy_pred<mpl::_, mpl::_> >::type
^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^ This is just a waste of code; sort already invokes lambda on its predicate internally, as do all MPL algorithms accepting lambda expressions. As a matter of fact, they all use applyN<...>, which invokes lambda internally. Invoking lambda on the outside may be costing you some significant compilation speed, because the resulting metafunction class is a large nested type. The fastest thing would probably be to make sort_hierarchy_pred a metafunction class itself. [Aleksey, I'm not sure why the sort Expression Semantics uses explicit lambda and apply_wrap2; I don't think it helps to make anything clearer]
, aux_in> {};
and for a sequence of 5 or more, the compile time and memory usage gets too huge. To became unuseable.
What I'm trying to achieve is a sequence of types that are sorted with the bases first...
mpl::sort<Seq, boost::is_base_and_derived<_,_> >::type is the simplest way, if Seq is a mutable sequence. Otherwise, mpl::sort< Seq , boost::is_base_and_derived<_,_> , mpl::back_inserter<mpl::vector<> >
::type
HTH, -- Dave Abrahams Boost Consulting www.boost-consulting.com
On 8/5/05, David Abrahams <dave@boost-consulting.com> wrote:
Felipe Magno de Almeida <felipe.m.almeida@gmail.com> writes:
I don't think that's a valid strict weak ordering criterion, because for two classes unrelated by inheritance it produces true in either argument order.
Is it possible to use a non-strict weak ordering criterion with mpl::sort and have it sorted? All that I care is that the deriveds be after its bases in this sequence. Or is there any better way to accomplish this? Thanks, Felipe.
HTH,
-- Dave Abrahams Boost Consulting www.boost-consulting.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Felipe Magno de Almeida Developer from synergy and Computer Science student from State University of Campinas(UNICAMP). Unicamp: http://www.ic.unicamp.br Synergy: http://www.synergy.com.br "There is no dark side of the moon really. Matter of fact it's all dark."
Felipe Magno de Almeida <felipe.m.almeida@gmail.com> writes:
On 8/5/05, David Abrahams <dave@boost-consulting.com> wrote:
Felipe Magno de Almeida <felipe.m.almeida@gmail.com> writes:
I don't think that's a valid strict weak ordering criterion, because for two classes unrelated by inheritance it produces true in either argument order.
Is it possible to use a non-strict weak ordering criterion with mpl::sort and have it sorted?
What do the requirements for sort say about it? That's the final authority.
All that I care is that the deriveds be after its bases in this sequence. Or is there any better way to accomplish this?
Do it the way I told you to in my post. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On 8/5/05, David Abrahams <dave@boost-consulting.com> wrote:
Felipe Magno de Almeida <felipe.m.almeida@gmail.com> writes: is the simplest way, if Seq is a mutable sequence. Otherwise,
mpl::sort< Seq , boost::is_base_and_derived<_,_> , mpl::back_inserter<mpl::vector<> >
::type
Is there any reason why the code above compiled in less than 5 seconds, while the other I used wasnt compiling at all, the compiler complained about insuficient memory(it used about 500MB). I can see that the other way it needed more template instantiations, but it seemed to me like the number of instantiations should be linearly bigger, but that not what it seems at all... I'm testing it with a vector of 15 types only. Thanks,
HTH,
-- Dave Abrahams Boost Consulting www.boost-consulting.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Felipe Magno de Almeida Developer from synergy and Computer Science student from State University of Campinas(UNICAMP). Unicamp: http://www.ic.unicamp.br Synergy: http://www.synergy.com.br "There is no dark side of the moon really. Matter of fact it's all dark."
Felipe Magno de Almeida <felipe.m.almeida@gmail.com> writes:
On 8/5/05, David Abrahams <dave@boost-consulting.com> wrote:
Felipe Magno de Almeida <felipe.m.almeida@gmail.com> writes: is the simplest way, if Seq is a mutable sequence. Otherwise,
mpl::sort< Seq , boost::is_base_and_derived<_,_> , mpl::back_inserter<mpl::vector<> >
::type
Is there any reason why the code above compiled in less than 5 seconds, while the other I used wasnt compiling at all, the compiler complained about insuficient memory(it used about 500MB).
Maybe because you violated the requirements of the algorithm by not using a strict weak ordering?
I can see that the other way it needed more template instantiations, but it seemed to me like the number of instantiations should be linearly bigger, but that not what it seems at all... I'm testing it with a vector of 15 types only.
If you pass sort a bogus criterion, all bets are off. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams writes:
[Aleksey, I'm not sure why the sort Expression Semantics uses explicit lambda and apply_wrap2; I don't think it helps to make anything clearer]
Because there is no other way to write that out (auxiliary metafunction aside). -- Aleksey Gurtovoy MetaCommunications Engineering
Aleksey Gurtovoy <agurtovoy@meta-comm.com> writes:
David Abrahams writes:
[Aleksey, I'm not sure why the sort Expression Semantics uses explicit lambda and apply_wrap2; I don't think it helps to make anything clearer]
Because there is no other way to write that out (auxiliary metafunction aside).
Sorry, I must be dense. Why not just use apply<...> ? -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams writes:
Aleksey Gurtovoy <agurtovoy@meta-comm.com> writes:
David Abrahams writes:
[Aleksey, I'm not sure why the sort Expression Semantics uses explicit lambda and apply_wrap2; I don't think it helps to make anything clearer]
Because there is no other way to write that out (auxiliary metafunction aside).
Sorry, I must be dense. Why not just use apply<...> ?
The code in question is this (from http://www.boost.org/libs/mpl/doc/refmanual/sort.html): typedef back_inserter< vector<> > aux_in; typedef lambda<pred>::type p; typedef begin<s>::type pivot; typedef partition< iterator_range< next<pivot>::type, end<s>::type > , apply_wrap2<p,_1,deref<pivot>::type> // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ , aux_in , aux_in >::type partitioned; If 'pred' is a placeholder expression (e.g. 'is_float<_1>'), replacing the highlighted line with , apply<pred,_1,deref<pivot>::type> would blend together two of them into one, leading to unpredictable results: // the above is actually equivalent to this one, which // is not going to work , apply< is_float<_1>, _1, deref<pivot>::type > -- Aleksey Gurtovoy MetaCommunications Engineering
participants (3)
-
Aleksey Gurtovoy -
David Abrahams -
Felipe Magno de Almeida