Software Engineers Handbook/Life Cycle/Design/Choosing an Algorithm
Finding an Algorithm
In many cases, the issue is finding or creating any algorithm. Here are some hints to get past the algorithm writers block, to find an existing algorithm you didn't know existed, and new ways to find algorithms you already knew existed.
- Phone a friend.
- Thoroughly explaining the problem you need to solve to someone else in person, on the phone, or in email often allows you to generate a solution. Your friend might have a solution as well.
- Read an algorithm textbook.
- Skimming or reading an algorithm textbook can produce more terms for web searches, and fields likely to use this algorithm. You might just stumble on the answer.
- Search in other fields.
- If you can express your problem as a problem in other fields, such as computer graphics, other resources become viable.
- Try a newsgroup.
- There's a really good chance that someone else has experienced this problem before. Open source solutions may already be available.
Choosing an Algorithm
In the case where you find more than one appropriate algorithm, you can use these ideas to compare their suitability for your application.
- Implement, then optimize.
- All algorithms available may be good enough.
- How does it run on your typical data? How does it run on your exceptional data?
- Ease of Implementation
- How quickly can you get this algorithm implemented and running?
- What is the order (big O notation) of the algorithm? How does it scale with more input? How does it scale with more complex input?
- How easy is the algorithm to understand and maintain?
- Multi-processor compatibility
- Do you have multiple processors available? Does this algorithm maximize their usage?
- Is code size an issue? Is memory/cache/file size and issue?
These questions will be wieghted differently for different applications. For instance, a prototype will likely emphasize the ease of implementation over the other criteria. A search through a massive database is likely to emphasize performance over the other criteria.
Books and Articles
- Introduction to Algorithms (ISBN 0262032937) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein is a classic Algorithms textbook.
- Selecting the Right Algorithm by Lagoudakis et. al. discusses choosing the correct sorting algorithm
- Selecting a Hashing Algorithm by McKensie et. al.
- comp.graphics.algorithms FAQ contains links and discussions on many algorithms