Using architectural trade-offs
When your code cannot be improved any further by reducing the complexity or choosing the proper data structure, a good approach may be to consider doing some trade-offs. If we review user problems and define what is really important for them, we can relax some of the application requirements. The performance can often be improved by:
- Replacing exact solution algorithms with heuristics and approximation algorithms
- Deferring some work to delayed task queues
- Using probabilistic data structures
Using heuristics and approximation algorithms
Some algorithmic problems simply don't have good state of the art solutions that could run in time acceptable to the user. For example, consider a program that deals with some complex optimization problems such as Traveling Salesman Problem (TSP) or Vehicle Routing Problem (VRP). Both problems are NP-hard problems in combinatorial optimization. The exact algorithms for such problems that have low complexity are not known. This...
