Is it possible to evaluate the efficiency of a testable algorithm against alternative solutions that aren't already built? [closed]

Question

An e-commerce application I used to work on used a decision tree and a rules engine for each node in order to determine if a customer qualified for certain discounts.

The problem was that every promotion tree had to be evaluated, so the more promotions the client had the slower the evaluation became.

This was a big problem that was often solved by throwing more hardware at it.

There were alternatives to consider, but the promotions engine was a considerable undertaking.

I always wondered if there was a way to consider an alternative without developing it (or developing it entirely)?

Answer 1

I always wondered if there was a way to consider an alternative without developing it (or developing it entirely)?

Yes. There is.

It's called "design".

You build a model (ideally a mathematical model) of each different algorithm.

You do some analysis on that model to get the "Big-O" time complexity of the algorithms.

The algorithms with less time complexity will usually tend to be faster.

Answer 2

As S.Lott suggested, the standard way of doing it is by abstraction to the Big-O notation. It has shown that for algorithms, this asymptotical consideration is a good predictor on the real performance.

But sometimes, it's too rough (e.g. you cannot tell which O(n^2) implementation is faster) and sometimes it's misleading (there can be an O(n) implementation that is slower for the usual input sets than an O(n^2) implementation). That's why there is a lot of research about performance predictability at our University, with a methodology and tool called Palladio. If you are interested, take a look at it and see that such predictions are far from being trivial. If you are even more interested, try it!

Answer 3

You can try to make an approximation with a few techniques:

• Compare existent and already implemented algorithms which work in a similar way or are parts of the algorithm you want to evaluate,
• Build a mathematical model of each algorithm and evaluate the models (see the answer by S.Lott),
• Build the most essential, performance-wise, parts of each algorithm and profile them.

This being said, you'll obtain just an idea. It may work perfectly well in some cases. It may completely fail in others, because you omitted compiler optimization, or how processor work, or some weird thing in a language or a runtime, etc.

That's why when you see on Programmes.SE questions "Is A faster than B", "If I change this and that, will it become faster?", the only answer they receive is inviting the author of the question to profile the application.

Answer 4

First and foremost you have to compare the asymptotic complexity of the algorithms (the Big-O notation that people have mentioned here). This gives you a way to quickly gauge which algorithm will be faster. Even though O(n^2) might be faster than O(n) for a small input size, the fact that you are worried about performance tells me that your input size is not that small.

If the alternative algorithm passes the complexity analysis, but you are still not sure if it is a better choice, then there must be some benchmark data for it. Whoever came up with the algorithm must have written a paper about it, and must have done some sort of evaluation. You may be able get some idea of the performance from the paper. Sometimes the authors publish the data they used for evaluation, so you may be able to benchmark your algorithm on the same data. And, of course, you can always contact the authors and ask.