Avvägning mellan rum och tid

En avvägning mellan rum och tid , även känd som avvägning mellan tid och minne eller det algoritmiska rum-tidskontinuumet inom datavetenskap är ett fall där en algoritm eller ett program byter ut ökad utrymmesanvändning med minskad tid. Här utrymme den datalagring som förbrukas för att utföra en given uppgift ( RAM , HDD , etc), och tid avser den tid som förbrukas för att utföra en given uppgift ( beräkningstid eller svarstid ).

Nyttan av en given kompromiss mellan utrymme och tid påverkas av relaterade fasta och rörliga kostnader (av t.ex. CPU- hastighet, lagringsutrymme) och är föremål för minskande avkastning .

Historia

Biologisk användning av kompromisser mellan tid och minne kan ses i de tidigare stadierna av djurbeteende . Genom att använda lagrad kunskap eller koda stimuli-reaktioner som "instinkter" i DNA:t undviker man behovet av "beräkning" i tidskritiska situationer. Mer specifikt för datorer uppslagstabeller implementerats sedan de allra tidigaste operativsystemen.

1980 föreslog Martin Hellman först att använda en tids-minne-avvägning för kryptoanalys .

Typer av avvägning

Uppslagstabeller kontra omräkning

En vanlig situation är en algoritm som involverar en uppslagstabell : en implementering kan inkludera hela tabellen, vilket minskar beräkningstiden, men ökar mängden minne som behövs, eller så kan den beräkna tabellposter efter behov, vilket ökar beräkningstiden, men minskar minneskraven.

Databasindex kontra tabellskanningar

Databashanteringssystem erbjuder möjligheten att skapa datastrukturer för databasindex . Index förbättrar hastigheten för uppslagsoperationer till priset av ytterligare utrymme. Utan index krävs ibland tidskrävande fullbordsskanningsoperationer för att lokalisera önskad data.

Komprimerad vs. okomprimerad data

En avvägning mellan rum och tid kan tillämpas på problemet med datalagring. Om data lagras okomprimerat tar det mer utrymme men åtkomst tar kortare tid än om data lagrades komprimerat (eftersom komprimering av data minskar mängden utrymme det tar, men det tar tid att köra dekomprimeringsalgoritmen ) . Beroende på den specifika instansen av problemet, är båda sätten praktiskt. Det finns också sällsynta fall där det är möjligt att direkt arbeta med komprimerad data, till exempel vid komprimerade bitmappsindex , där det går snabbare att arbeta med komprimering än utan komprimering.

Återrendering kontra lagrade bilder

Att endast lagra SVG -källan för en vektorbild och rendera den som en bitmappsbild varje gång sidan efterfrågas skulle vara bytestid mot utrymme; mer tid används, men mindre utrymme. Att rendera bilden när sidan ändras och att lagra de renderade bilderna skulle byta utrymme för tid; mer utrymme används, men mindre tid. Denna teknik är mer allmänt känd som cachning .

Mindre kod jämfört med loopavrullning

Större kodstorlek kan bytas ut mot högre programhastighet vid tillämpning av loopavrullning . Denna teknik gör koden längre för varje iteration av en loop, men sparar den beräkningstid som krävs för att hoppa tillbaka till början av loopen i slutet av varje iteration.

Andra exempel

Algoritmer som också använder sig av avvägningar mellan rum och tid inkluderar:

• Baby-step jätte-steg algoritm för beräkning av diskreta logaritmer
• Rainbow-tabeller i kryptografi, där motståndaren försöker göra bättre ifrån sig än den exponentiella tid som krävs för en brute-force-attack . Rainbow-tabeller använder delvis förberäknade värden i hashutrymmet för en kryptografisk hashfunktion för att knäcka lösenord på minuter istället för veckor. Att minska storleken på regnbågsbordet ökar den tid som krävs för att iterera över hashutrymmet.
• Meet -in-the-middle-attacken använder en avvägning mellan rum och tid för att hitta den kryptografiska nyckeln i endast ${\displaystyle 2^{n+1}}-$ krypteringar (och $O( 2^{n})$ mellanslag) kontra de förväntade $2^{2n}$ krypteringarna (men bara $O(1)$ mellanslag) för den naiva attacken.
• Dynamisk programmering , där tidskomplexiteten för ett problem kan reduceras avsevärt genom att använda mer minne.

Se även

• Algoritmisk effektivitet – Egenskapen hos en algoritm
• Blums speedup-sats – utesluter att godtyckliga funktioner tilldelar deras beräkningskomplexitet
• Beräkningskomplexitet – Mängden resurser för att utföra en algoritm
• Beräkningsresurs – Något som en dator behöver för att lösa ett problem, till exempel bearbetningssteg eller minne
• Savitchs teorem – Förhållandet mellan deterministisk och icke-deterministisk rymdkomplexitet

externa länkar

• Philippe Oechslin: Att göra en snabbare avvägning mellan kryptoanalytisk tid och minne.
• Once Upon a Time-Memory Tradeoff.