Time-Memory Tradeoff

In der Informatik ist ein Time-Memory Tradeoff (TMTO, deutsch Zeit-Speicher-Kompromiss oder Zeit-Speicher-Ausgleich) ein Kompromiss, bei dem der Speicherbedarf …

In der Informatik ist ein Time-Memory Tradeoff (TMTO, deutsch Zeit-Speicher-Kompromiss oder Zeit-Speicher-Ausgleich) ein Kompromiss, bei dem der Speicherbedarf eines Programmes auf Kosten einer längeren Laufzeit gesenkt wird oder umgekehrt die Laufzeit auf Kosten eines höheren Speicherbedarfs verkürzt wird. Ziel dabei ist es, das Programm unter aktuellen technischen Voraussetzungen möglichst effizient umzusetzen.

Der Begriff wird nicht nur für den entstehenden Kompromiss und für den Vorgang des Abwägens, sondern auch zur Benennung von Problemenklassen, die eine solche Abwägung nahelegen, verwendet. Darüber hinaus werden manche Programme und Algorithmen, die von diesem Vorgehen entscheidend geprägt wurden, mit diesem Wort bezeichnet.

Beispiele für Kompromissformen

  • Lookup-Tabelle gegenüber Neuberechnung
    Bei der Verwendung von Lookup-Tabellen kann in der Implementierung die gesamte Tabelle vorberechnet werden, wodurch die Laufzeit verringert, aber der Speicherbedarf erhöht wird.
  • Komprimierte Daten gegenüber unkomprimierten Daten
    Ein Ausgleich zwischen Speicher und Laufzeit erfolgt bei der Datenkompression, wobei der Speicherbedarf von Daten verringert wird, aber mehr Zeit zum Dekomprimieren benötigt wird.
  • Re-rendering gegenüber gespeicherten Bildern
    Werden auf einem Server LaTeX-Formeln als Quelltext und nicht als Bilddatei gespeichert, so wird der Speicherbedarf gesenkt, aber durch das wiederholte Rendern die Laufzeit erhöht.
  • Kleiner Programmcode gegenüber loop unrolling
    Durch Auflösen von Schleifen konnte früher die Laufzeit verkürzt werden, während sich der Programmcode vergrößert. Heutige CPUs benötigen dies nicht mehr und laufen teilweise mit loop unrolling langsamer als ohne.

Beispiele für Algorithmen

Bei den Rainbow-Tabellen hat die konsequente Anwendung dieses Prinzips zu einer kompletten Zweiteilung der Lösung geführt. In einem völlig eigenständigen Vorbereitungsprogramm werden mit ganz erheblichem Rechenaufwand große Tabellen vorbereitet. Andere Programme nutzen die vorbereiteten Tabellen, um damit in relativ geringer Zeit Verschlüsselungen oder Passwörter zu brechen.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.