Time-memory tradeoff

from Wikipedia, the free encyclopedia

In computer science , a time-memory tradeoff (TMTO, German time-memory compromise or time-memory balance ) is a compromise in which the memory requirement of a program is reduced at the expense of a longer runtime or, conversely, the runtime at the expense of a higher memory requirement is shortened. The aim is to implement the program as efficiently as possible under current technical conditions .

The term is used not only for the resulting compromise and for the weighing process, but also to designate problem classes that suggest such weighing. In addition, some programs and algorithms that have been decisively shaped by this procedure are identified with this word.

Examples of compromise forms

  • Lookup table versus recalculation
    When using lookup tables, the entire table can be precalculated in the implementation, which reduces the runtime but increases the memory requirement.
  • Compressed data versus uncompressed data
    A balance between memory and running time occurs with data compression , whereby the memory requirement of data is reduced, but more time is required for decompression.
  • Re-rendering versus saved images
    If LaTeX formulas are saved on a server as source text and not as an image file, the memory requirement is reduced, but the runtime is increased through repeated rendering.
  • Small program code compared to loop unrolling In the past,
    by breaking up loops , the runtime could be shortened while the program code increased. Today's CPUs no longer need this and sometimes run slower with loop unrolling than without.

Examples of algorithms

With the rainbow tables, the consistent application of this principle has resulted in a complete split of the solution. In a completely independent preparation program, large tables are prepared with a considerable amount of computing effort. Other programs use the prepared tables to break encryptions or passwords in a relatively short time.

Web links