Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|improve this question

closed as not constructive by Oded, Jim G., Dynamic, ChrisF Sep 30 '12 at 20:49

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

Are you using a third-party, RETE-based rules engine, or something home grown? There's a lot of history and math behind rules engine algorithms. – Matthew Flynn Sep 19 '11 at 20:21
@MatthewFlynn It was home grown. – Brian Reindel Sep 20 '11 at 0:14
up vote 7 down vote accepted

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.

share|improve this answer

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!

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.