Czasoprzestrzeń kompromis - Space–time tradeoff
Czasoprzestrzeni lub czasowo pamięć kompromis w informatyce jest przypadek, gdy algorytm lub programowe transakcji zwiększyła wykorzystanie przestrzeni z zmniejszono czas. Tutaj przestrzeń dotyczy pamięci danych zużywanej w wykonaniu określonego zadania ( RAM , dysk twardy , itp) i czasu odnosi się do czasu zużywanego w wykonaniu określonego zadania ( obliczenie czasu lub w czasie reakcji ).
Użyteczność danego kompromis czasoprzestrzeni wpływa powiązanych stałych i kosztów zmiennych (z, na przykład, CPU prędkość, przestrzeń składowania) i podlega malejących przychodów .
Zawartość
Historia
Wykorzystanie biologiczna kompromisów czas pamięci można zobaczyć na wcześniejszych etapach zachowań zwierząt . Korzystanie przechowywanej wiedzy lub kodujących reakcje bodźce jak „instynktów” w DNA eliminuje potrzebę „obliczenia” w sytuacjach krytycznych czasowo. A dokładniej do komputerów, tablice look-up zostały wdrożone od najwcześniejszych systemów operacyjnych.
W 1980 roku Martin Hellman pierwszy zaproponował kompromis używając czasu pamięci do kryptoanalizy .
Rodzaje kompromis
tablice przeglądowe vs. przeliczenia
Najczęstszym sytuacja jest algorytmem udziałem tabeli odnośników : implementacja może obejmować całą tabelę, która skraca czas obliczeń, ale zwiększa ilość potrzebnej pamięci, lub może obliczyć wpisów w tabeli, ile potrzeba, zwiększając czas obliczeń, ale zmniejszając zapotrzebowanie na pamięć ,
Sprężone vs. nieskompresowanych danych
Przestrzeń-Czas kompromis może być stosowany do problemu przechowywania danych. Jeśli dane są przechowywane bez kompresji, zajmuje więcej miejsca, ale dostęp zajmuje mniej czasu, niż gdyby dane były przechowywane skompresowane (od kompresję danych zmniejsza ilość miejsca potrzebnego, ale na to potrzeba czasu, aby uruchomić algorytm dekompresji ). W zależności od konkretnego przypadku problemu, albo sposób jest praktyczne. Istnieje również rzadkie przypadki, w których nie jest możliwe bezpośrednie pracować skompresowanych danych, na przykład w przypadku prasowanych indeksów bitmapy , gdzie jest szybciej do pracy ściskania niż bez kompresji.
Re-rendering obrazów vs. przechowywane
Przechowywanie tylko SVG źródło o wektor obraz i czynią je jako bitmapy za każdym razem, gdy strona jest żądany czas będzie handel na przestrzeni; Jeszcze raz używane, ale mniej miejsca. Renderowania obrazu, gdy strona zostanie zmieniona i przechowywanie renderowanych obrazów byłby handel przestrzeń do czasu; więcej przestrzeń używane, ale mniej czasu. Ta technika jest bardziej powszechnie znane jako pamięci podręcznej .
Mniejsza w porównaniu pętli kodu rozwijania
Większy rozmiar kodu mogą być przedmiotem obrotu na większą prędkość programu przy stosowaniu odwijanie pętli . Technika ta sprawia, że kod jest już dla każdej iteracji pętli, ale oszczędza czas obliczeń wymaganych do skoków z powrotem do początku pętli na końcu każdej iteracji.
Inne przykłady
Algorytmy, które również korzystają z kompromisów czasoprzestrzennych obejmują:
- Gigantyczny krok-baby-krok algorytm obliczania dyskretnych logarytmów
- Tęczowe tablice w kryptografii, gdzie przeciwnik stara się zrobić lepiej niż czas wymagany wykładniczej dla ataku brute-force . Tęczowe tablice używać wartości precomputed częściowo w przestrzeni mieszającej z kryptograficznej funkcji skrótu do łamania haseł w ciągu kilku minut, a nie tygodni. Zmniejszenie rozmiaru tabeli tęczy zwiększa czas wymagany do iteracji na przestrzeni mieszającej.
- Atak meet-in-the-middle używa kompromis czasoprzestrzeni znaleźć klucza kryptograficznego w zaledwie encryptions (i przestrzeni) w porównaniu do oczekiwanych encryptions (ale tylko spacja) od naiwnego ataku.
- Programowanie dynamiczne , gdzie złożoność czas problemu można znacznie zmniejszyć poprzez zastosowanie większej ilości pamięci.
