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.

Performance

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?

Scalability

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?

Maintainability

How easy is the algorithm to understand and maintain?

Multi-processor compatibility

Do you have multiple processors available? Does this algorithm maximize their usage?

Size

Is code size an issue? Is memory/cache/file size and issue?

These questions will be weighted 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.

Links

• 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