Time-Memory Tradeoff

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 eines Programmes auf Kosten einer längeren Laufzeit gesenkt wird oder umgekehrt die Laufzeit auf Kosten eines höheren Speicherbedarf 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 nahe legen, 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

Bei der Verwendung von Lookup-Tabellen kann in der Implementierung die gesamte Tabelle vorberechnet werden, wodurch die Laufzeit verringert, aber den 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.
Werden auf einem Server (beispielsweise der Wikipedia) LaTeX-Formeln als Quelltext und nicht als Bilddatei gespeichert, so wird der Speicherbedarf gesenkt, aber durch das wiederholte Rendern die Laufzeit erhöht.
Durch Auflösen von Schleifen kann die Laufzeit verkürzt werden, während sich der Programmcode vergrößert.

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.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Space-time tradeoff — In computer science, a space time or time memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution, or vice versa, the computation time can be reduced at the cost of increased memory use. As the… …   Wikipedia

  • Space-time tradeoff — Space time trade off («выбор оптимального соотношения „место время“ (англ. space time trade off)», или, иначе, «выбор оптимального соотношения „время память“» (англ. time memory trade off))  компромиссный подход к решению ряда задач в… …   Википедия

  • Phase-change memory — Computer memory types Volatile RAM DRAM (e.g., DDR SDRAM) SRAM In development T RAM Z RAM TTRAM Historical Delay line memory Selectron tube Williams tube Non volatile …   Wikipedia

  • Just-in-time compilation — In computing, just in time compilation (JIT), also known as dynamic translation, is a method to improve the runtime performance of computer programs. Historically, computer programs had two modes of runtime operation, either interpreted or static …   Wikipedia

  • A5/1 — is a stream cipher used to provide over the air communication privacy in the GSM cellular telephone standard. It was initially kept secret, but became public knowledge through leaks and reverse engineering. A number of serious weaknesses in the… …   Wikipedia

  • Rainbow table — A rainbow table is a lookup table offering a time memory tradeoff used in recovering the plaintext password from a password hash generated by a hash function, often a cryptographic hash function. A common application is to make attacks against… …   Wikipedia

  • Password cracking — is the process of recovering passwords from data that has been stored in or transmitted by a computer system. A common approach is to repeatedly try guesses for the password. The purpose of password cracking might be to help a user recover a… …   Wikipedia

  • Meet-in-the-middle attack — Not to be confused with man in the middle attack. The meet in the middle attack is a cryptographic attack which, like the birthday attack, makes use of a space time tradeoff. While the birthday attack attempts to find two values in the domain of… …   Wikipedia

  • Радужная таблица — Схема упрощенной радужной таблицы с длиной цепочек равной трем. R1 R2 R3 функции редукции, H функция хеширования. Радужная таблица (англ. rainbow table)  специальный вариан …   Википедия

  • Радужные таблицы — Радужная таблица (англ. rainbow table) специальный вариант таблиц поиска (lookup table), использующий механизм уменьшения времени поиска за счет увеличения занимаемой памяти или time memory tradeoff. Радужные таблицы используется для вскрытия… …   Википедия

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”