When talking about software development 3 goals are often what we are aiming to achieve, correctness, simplicity and maintainability. In a simple word it requires the programmer/developers to write correct code that complies with the software specifications and deliver what it promises, is simple enough for new developers to understand and hence is maintainable to fix the bug and add more functionality by new developers without changes in design/architecture. A good measurement is to the time and resource used to deliver the same quality of software.
These three goals are pre-requests for algorithm software development. Here I would like to add one more goal, extensibility, which allows the software grows further. It requires that the software design/architecture is flexible enough to tweak the existing algorithms or implement new ones, and construct the new software application that utilizes these algorithms. In most of normal software applications the extensibility/flexibility is neglected because of limited of time and resources. In my personal experience on most occasions the software design does not require huge flexibility in non-algorithm software development, because it usually adds extra layer of code and makes the software architecture over-complicated. Usually the pro-flexibility often loses the argument because of the fact that the software flexibility is never coming into use in most occasions and simply it requires more and resource to develop, test and maintain.
However in algorithm software development it is not the case especially in the area like modelling and risk modeling in finance. The performance of algorithm is the main selling point when marketing the software. The performance is key to the customer. Then the algorithm is the key delivery of each software development cycle. In the design/implementation point of view the algorithm is constantly being modified/added to extend the functionality or/and improve the performance.
In algorithm software development extensibility often means
- The software design/architecture allows to design/implement the new algorithm in. And the new algorithm is able to solve all existing problems/systems.
- The software design/architecture allows to design/implement new problems/systems in. And all the existing algorithms are able to solve the newly-added problems/systems.
- The newly added algorithm can be easily coupled with (or utilized by) the newly added problems/systems.
Simply the requirement needs the software design/architecture to decouple the problems/systems with algorithms. Their relationship could be as loose as possible and at the same time provide an easy way to join them together.
2. Strategy pattern
As shown in Figure 1, an interface is provided to convey all the functionality of Strategy. And class Context is to couple the detailed application and Strategy.
The detailed algorithms will be implemented as an implementation/sub-class of interface Strategy. And the Context and Strategy is in "has-a" relationship and described as "association" in UML.
This technique certainly decouples the algorithm with the detailed application. For the software to grow, for instance adding new algorithm, it is simply to implement the new algorithm as an sub-class of Strategy.
3. Example
In my day-to-day job I am playing with quite complex algorithms - solvers, which is used to model/solve first-order DAE from applications like simulation, optimization, parameter estimation and experiment design. And these solvers could be very complex. Solvers can have dozens of configurations, and normally have sub-solvers. Here is the list classes to help understand.
- StrategyConfig : solver configuration
- Strategy: top solver API
The difference here with Figure 1, an extra layer is introduced as StrategyDelegate. This layer is going to help to bridge all the heterogeneity of varying algorithms. For instance use Monto-Calro method and finite element method to solve the problem. The ideas of these two are completely different. The extra layer of StrategyDelegate is to bridge the difference to make sure serve the same API required by Strategy. This will hugely increase the extensibility/flexibility of this design.
Class Problem is the context to couple the systems that these algorithms are designed to solve. It owns a instance of Strategy.
*********************************************************************************
struct StategyConfig{
std::string algo_name;
double absolute_tolerance;
relative absolute_tolerance;
StrategyConfig* subAlg;
};
class Strategy {
public:
status Solve();
std::auto_ptr<Strategy> CreateStrategy(const StrategyConfig& sc);
private:
std::auto_ptr<StragegyDelegate> m_SD;
};
class Algorithm {
public:
// another layer: any public function
};
class StrategyDelegate{
public:
// any interface/functions needed for Strategy.
private:
std::auto_ptr<Algorithm> m_Algorithm;
};
class AbcStrategyDelegate : public StrategyDelegate {
// this is to have an instance of AbcAlgo
};
class AbcAlgo: public Algorithm {
};
class XyzStrategyDelegate : public StrategyDelegate {
// this is t have instance of XyzAlgo
};
class XyzAlgo: public Algorithm {
};
class Problm{
protected:
std::auto_ptr<Strategy> m_strategy;
std::auto_ptr<StrategyConfig> m_config;
};
class ProblemImpl1 : public Problem {
}
*********************************************************************************
Any variation of existing algorithm can be sub-class of the existing algorithms
Any new algorithm is to implement its sub class of StrategyDelegate and Algorithm.
Any variation/new problem can be implemented as the same pattern as Strategy.
The coupling between them is achieved by the "has-a" relationship between Problem
and Strategy.
In this example we see that strategy pattern is used together with other patterns.
- Bridge pattern to bring the difference of varying algorithms to be able to serve the same API required in Strategy.
- Factory method to create varying strategies based on user-defined configuration.
4. One problem in C++ - performance
The main problem with strategy pattern is that an interface has to be implemented/served by the algorithms. And in C++ interface is achieved by abstract class (no data + pure virtual functions). This means that all the interface are dynamically linked in the running time. This could cause the performance issue, because dynamic binding causes the overhead of function invocation and prevents function optimized as inline function by compiler.
One alternative to dynamic polymophism is static polymophism. Use template to implement different algorithms. Each algorithm will have its own copy at compile time. Therefore remove the overhead of dynamic binding. Design pattern such as CRTP (curiously recurring template pattern). Please read my another blogger entry http://cpluspluslearning-petert.blogspot.co.uk/2014/03/design-pattern-curiously-recurring.html.
A good example of strategy pattern in algorithm software development together with other design pattern is QuantLib [4]. The pricing engine of instruments is based on strategy pattern with mixture of other patterns.
5. Emulate multiple inheritance in Java or C#
In Java and C# multiple inheritance is not support like C++. Some folks from C++ background miss this feature still when they are playing in Java and C# field. Strategy pattern can be used to emulate the multiple inheritance in Java and C#.
Problem:
Implement a class FooBar has both the functions of two, Foo and Bar, in Java or C#. Hence FooBar
can be casted into both Foo or Bar.
*********************************************************************************
class Foo {
public:
void F() {
// implementation
}
void G() {
// implementation
}
};
class Bar {
void M() {
// implementation
}
void N() {
// implementation
}
};
*********************************************************************************
Solution:
Obviously Java and C# does not support multiple inheritance for two concrete classes. But they do support if they are interfaces. Here is the trick,
*********************************************************************************
interface IBar {
void M();
void N();
};
class Bar extends IBar {
void M() {
// implementation
}
void N() {
// implementation
}
};
class FooBar extends Foo, IBar {
// delegate the implmention of IBar API to Bar
void M() { m_Bar.M(); }
void N() { m_Bar.N(); }
private:
Bar m_Bar;
}
*********************************************************************************
In this solution FooBar plays the role of "Context" as in Figure 1 and "IBar" plays as the role of "Strategy". And Bar as a concrete implementation of interface "IBar" implements the public API of Bar. Then FooBar can be casted into Foo and IBar to emulate the functionality of multiple inheritance.
[1] http://en.wikipedia.org/wiki/Strategy_pattern
[2] GOF, Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides, "Design Patterns - Elements of Reusable Object-Oriented Software", 1994
[3] Robert C. Martin, "Clean Code - A Handbook of Agile Sofware Craftsmanship", 2009, Prentice Hall
[4] http://quantlib.org/index.shtml
No comments:
Post a Comment