Algorithmic Efficiency - Software Metrics

Software Metrics

The two most frequently encountered and measurable metrics of an algorithm are:-

  • speed or running time—the time it takes for an algorithm to complete, and
  • 'space'—the memory or 'non-volatile storage' used by the algorithm during its operation.

but also might apply to

  • transmission size—such as required bandwidth during normal operation or
  • size of external memory- such as temporary disk space used to accomplish its task

and perhaps even

  • the size of required 'longterm' disk space required after its operation to record its output or maintain its required function during its required useful lifetime (examples: a data table, archive or a computer log) and also
  • the performance per watt and the total energy, consumed by the chosen hardware implementation (with its system requirements, necessary auxiliary support systems including interfaces, cabling, switching, cooling and security), during its required useful lifetime. See Total cost of ownership for other potential costs that might be associated with any particular implementation.

(An extreme example of these metrics might be to consider their values in relation to a repeated simple algorithm for calculating and storing (π+n) to 50 decimal places running for say, 24 hours, on a processor operating in its own purpose-built heated or air conditioned unit.)

The process of making code more efficient is known as optimization and in the case of automatic optimization (i.e. compiler optimization—performed by compilers on request or by default), usually focus on space at the cost of speed, or vice versa. There are also quite simple programming techniques and 'avoidance strategies' that can actually improve both at the same time, usually irrespective of hardware, software or language. Even the re-ordering of nested conditional statements to put the least frequently occurring condition first can reduce actual instruction path length. For example, a condition might test patients for (age > 18) before testing (blood type == 'AB-') because this type of blood occurs in only about 1 in 100 of the population. This would eliminate the second test at runtime in 99% of instances; something an optimizing compiler would almost certainly not be aware of—but which a programmer can research relatively easily even without specialist medical knowledge.

Read more about this topic:  Algorithmic Efficiency