From 0cca9a599a66758cbb5a958b619de3315f26b528 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Thu, 5 Jul 2012 16:39:32 +1000 Subject: Intermediate (broken) commit - smarter strategy --- impl/EquationSystem.hpp | 18 ++++-- impl/MaxStrategy.hpp | 147 ++++++++++++++++++++-------------------------- impl/main.cpp | 16 +++-- impl/systems/example.eqns | 6 +- 4 files changed, 91 insertions(+), 96 deletions(-) diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp index 50a0e45..5549674 100644 --- a/impl/EquationSystem.hpp +++ b/impl/EquationSystem.hpp @@ -13,11 +13,13 @@ struct EquationSystem { virtual ~EquationSystem() { } virtual const Expression* operator[](const Variable&) const = 0; virtual VariableAssignment* eval(const VariableAssignment& rho) const = 0; + virtual unsigned int variableCount() const = 0; virtual Variable& variable(unsigned int) const = 0; + virtual StableVariableAssignment* assignment(const Domain& value) const = 0; + virtual Variable* varFromExpr(const Expression& expr) const = 0; virtual bool equalAssignments(const VariableAssignment&, const VariableAssignment&) const = 0; - virtual void print(std::ostream& cout) const = 0; }; @@ -86,10 +88,10 @@ struct ConcreteEquationSystem : public EquationSystem { return *constant; } - Expression* operator[](const Variable& var) const { + MaxExpression* operator[](const Variable& var) const { return _right_sides[var.id()]; } - Expression*& operator[](const Variable& var) { + MaxExpression*& operator[](const Variable& var) { return _right_sides[var.id()]; } @@ -108,6 +110,14 @@ struct ConcreteEquationSystem : public EquationSystem { return result; } + Variable* varFromExpr(const Expression& expr) const { + for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) { + if (_right_sides[i] == &expr) + return _variables[i]; + } + return NULL; + } + virtual bool equalAssignments(const VariableAssignment& l, const VariableAssignment& r) const { for (unsigned int i = 0, length = _variables.size(); i < length; @@ -133,7 +143,7 @@ struct ConcreteEquationSystem : public EquationSystem { std::vector*> _variables; std::map*> _variable_names; std::vector*> _max_expressions; - std::vector*> _right_sides; + std::vector*> _right_sides; }; template diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp index 9fa7768..977036f 100644 --- a/impl/MaxStrategy.hpp +++ b/impl/MaxStrategy.hpp @@ -5,9 +5,45 @@ #include "EquationSystem.hpp" #include "IdSet.hpp" +template +struct MaxStrategy : public EquationSystem { + MaxStrategy(const EquationSystem& sub) + : _sub(sub) { } + + virtual ~MaxStrategy() { } + virtual const Expression* operator[](const Variable& var) const { + return _sub[var]; + } + virtual VariableAssignment* eval(const VariableAssignment& rho) const { + return _sub.eval(rho); + } + virtual unsigned int variableCount() const { + return _sub.variableCount(); + } + virtual Variable& variable(unsigned int i) const { + return _sub.variable(i); + } + virtual StableVariableAssignment* assignment(const Domain& value) const { + return _sub.assignment(value); + } + virtual bool equalAssignments(const VariableAssignment& r1, const VariableAssignment& r2) const { + return _sub.equalAssignments(r1, r2); + } + virtual Variable* varFromExpr(const Expression& expr) const { + return _sub.varFromExpr(expr); + } + virtual void print(std::ostream& cout) const { + return _sub.print(cout); + } + + virtual unsigned int get(const MaxExpression& e) const = 0; + private: + const EquationSystem& _sub; +}; + template struct MaxStrategyExpression : public Expression { - MaxStrategyExpression(const Expression& expr, const IdMap,unsigned int>& strategy) + MaxStrategyExpression(const Expression& expr, const MaxStrategy& strategy) : _expr(expr), _strategy(strategy) { } virtual Domain eval(const VariableAssignment& rho) const { @@ -17,7 +53,7 @@ struct MaxStrategyExpression : public Expression { const MaxExpression* maxExpr = dynamic_cast*>(opExpr); const std::vector*> args = opExpr->arguments(); if (maxExpr) { - unsigned int i = _strategy[*maxExpr]; + unsigned int i = _strategy.get(*maxExpr); return MaxStrategyExpression(*args[i], _strategy).eval(rho); } else { std::vector argumentValues; @@ -38,16 +74,19 @@ struct MaxStrategyExpression : public Expression { } private: const Expression& _expr; - const IdMap,unsigned int>& _strategy; + const MaxStrategy& _strategy; }; template -struct MaxStrategy : public EquationSystem { - MaxStrategy(const ConcreteEquationSystem& system) - : _system(system), _expressions(system.variableCount(), NULL), _strategy(system.maxExpressionCount(), 0) { +struct ConcreteMaxStrategy : public MaxStrategy { + ConcreteMaxStrategy(const ConcreteEquationSystem& system) + : MaxStrategy(system), + _system(system), + _expressions(system.variableCount(), NULL), + _strategy(system.maxExpressionCount(), 0) { } - ~MaxStrategy() { + ~ConcreteMaxStrategy() { for (int i = 0, length = _system.variableCount(); i < length; ++i) { @@ -59,7 +98,7 @@ struct MaxStrategy : public EquationSystem { const Expression* operator[](const Variable& v) const { if (_expressions[v] == NULL) { - Expression* expression = new MaxStrategyExpression(*_system[v], _strategy); + Expression* expression = new MaxStrategyExpression(*_system[v], *this); _expressions[v] = expression; return expression; } else { @@ -94,6 +133,14 @@ struct MaxStrategy : public EquationSystem { Variable& variable(unsigned int i) const { return _system.variable(i); } + + unsigned int maxExpressionCount() const { + return _system.maxExpressionCount(); + } + + MaxExpression& maxExpression(unsigned int i) const { + return _system.maxExpression(i); + } StableVariableAssignment* assignment(const Domain& v) const { return _system.assignment(v); @@ -103,86 +150,18 @@ struct MaxStrategy : public EquationSystem { return _system.equalAssignments(l, r); } - - struct ImprovementOperator { - virtual ~ImprovementOperator() { } - virtual bool improve( - MaxStrategy& strat, - const VariableAssignment& rho, - const IdSet >& changedIn, - IdSet >& changedOut - ) const = 0; - }; - bool improve(const ImprovementOperator& op, const VariableAssignment& rho, const IdSet >& changedIn, IdSet >& changedOut) { - return op.improve(*this, rho, changedIn, changedOut); - } - - struct NaiveImprovementOperator : public ImprovementOperator { - bool improve( - MaxStrategy& strat, - const VariableAssignment& rho, - const IdSet >& changedIn, - IdSet >& changedOut - ) const { - bool changed = false; - for (unsigned int i = 0, length = strat._system.maxExpressionCount(); - i < length; - ++i) { - MaxExpression& expr = strat._system.maxExpression(i); - Domain bestValue = MaxStrategyExpression(expr, strat._strategy).eval(rho); - unsigned int lastIndex= strat.get(expr); - unsigned int bestIndex = strat.get(expr); - - // this relies on the fact that an expression will only be proessed after the expressions - // it depends on (which should always be true, as they form a DAG) - const std::vector*> args = expr.arguments(); - for (unsigned int j = 0, length = args.size(); - j < length; - ++j) { - const Domain value = MaxStrategyExpression(*args[j], strat._strategy).eval(rho); - if (bestValue < value) { - bestValue = value; - bestIndex = j; - } - } - if (bestIndex != lastIndex) { - changed = true; - strat.set(expr, bestIndex); - } - } - return changed; - } - }; - - struct RepeatedImprovementOperator : public ImprovementOperator { - RepeatedImprovementOperator(const ImprovementOperator& op) - : _subImprovement(op) { } - - bool improve( - MaxStrategy& strat, - const VariableAssignment& rho, - const IdSet >& changedIn, - IdSet >& changedOut - ) const { - if (_subImprovement.improve(strat, rho, changedIn, changedOut)) { - VariableAssignment* rho2 = strat.eval(rho); - improve(strat, *rho2, changedIn, changedOut); - delete rho2; - return true; - } - return false; - } - private: - const ImprovementOperator& _subImprovement; - }; - - struct DependencyImprovementOperator : public ImprovementOperator { - }; - void print(std::ostream& cout) const { cout << _system << std::endl; } + const ConcreteEquationSystem& system() const { + return _system; + } + + const IdMap,unsigned int>& strategy() const { + return _strategy; + } + private: const ConcreteEquationSystem& _system; mutable IdMap,Expression*> _expressions; diff --git a/impl/main.cpp b/impl/main.cpp index b761587..26aedbe 100644 --- a/impl/main.cpp +++ b/impl/main.cpp @@ -6,6 +6,7 @@ #include "Operator.hpp" #include "EquationSystem.hpp" #include "MaxStrategy.hpp" +#include "ImprovementOperator.hpp" #include "FixpointAlgorithm.hpp" extern "C" { @@ -126,14 +127,17 @@ int main (int argc, char* argv[]) { } // PARSE ARGUMENTS - strat improvement - MaxStrategy::ImprovementOperator* naiveImprovement = new MaxStrategy::NaiveImprovementOperator(); - MaxStrategy::ImprovementOperator* improvement = NULL; + ImprovementOperator* naiveImprovement = new NaiveImprovementOperator(); + ImprovementOperator* improvement = NULL; if (!strcmp(argv[3], "repeat")) { - improvement = new MaxStrategy::RepeatedImprovementOperator(*naiveImprovement); + improvement = new RepeatedImprovementOperator(*naiveImprovement); cout << "Repeated strategy improvement" << endl; } else if (!strcmp(argv[3], "naive")) { improvement = naiveImprovement; cout << "Naive strategy improvement" << endl; + } else if (!strcmp(argv[3], "smart")) { + improvement = new SmartImprovementOperator(system); + cout << "Smart strategy improvement" << endl; } else { cout << "Unknown strategy improvement algorithm." << endl; } @@ -143,7 +147,7 @@ int main (int argc, char* argv[]) { cout << system << endl; StableVariableAssignment result(system.variableCount(), infinity()); - MaxStrategy strategy(system); + ConcreteMaxStrategy strategy(system); IdSet > s1(system.variableCount()); IdSet > s2(system.variableCount()); bool changed = false; @@ -159,7 +163,9 @@ int main (int argc, char* argv[]) { cout << endl; exit(0);*/ - changed = strategy.improve(*improvement, result, s1, s2); + s2.clear(); + changed = improvement->improve(strategy, result, s1, s2); + std::cout << (changed ? "true" : "false") << std::endl; } while(changed); cout << endl; diff --git a/impl/systems/example.eqns b/impl/systems/example.eqns index 9ef3135..71ee74a 100644 --- a/impl/systems/example.eqns +++ b/impl/systems/example.eqns @@ -1,3 +1,3 @@ -x1 = max([0,0], min(x1-[1,1], x2)) -x2 = max([0,0], [5,5]+x1, x1) -x3 = max([0,0], [1,1]+x3, [0,0]+x1) +x1 = max(0, min(x1-1, x2)) +x2 = max(0, 5+x1, x1) +x3 = max(0, 1+x3, 0+x1) -- cgit v1.2.3