Compromís espai-temps

Una compensació espai-temps, també coneguda com a compensació temps-memoria o continu algorítmic espai-temps en informàtica, és un cas en què un algorisme o programa intercanvia un ús més gran de l'espai amb una disminució del temps. Aquí, l'espai fa referència a l'emmagatzematge de dades consumit en realitzar una tasca determinada (RAM, HDD, etc.), i el temps fa referència al temps consumit en realitzar una tasca determinada (temps de càlcul o temps de resposta).[1]

La utilitat d'un determinat equilibri espai-temps es veu afectada pels costos fixos i variables relacionats (per exemple, la velocitat de la CPU, l'espai d'emmagatzematge) i està subjecta a rendiments decreixents.[2]

Història

L'ús biològic de les compensacions temps-memòria es pot veure en les primeres etapes del comportament animal. L'ús del coneixement emmagatzemat o la codificació de reaccions d'estímuls com a "instints" a l'ADN evita la necessitat de "càlculs" en situacions crítiques de temps. Més específicament per als ordinadors, les taules de cerca s'han implementat des dels primers sistemes operatius.

Tipus de compensació

Taules de cerca vs. recàlcul

Una situació habitual és un algorisme que implica una taula de cerca: una implementació pot incloure la taula sencera, la qual cosa redueix el temps de càlcul, però augmenta la quantitat de memòria necessària, o pot calcular les entrades de la taula segons sigui necessari, augmentant el temps de càlcul, però reduint els requisits de memòria.[3]

Índexs de bases de dades versus exploracions de taules

Els sistemes de gestió de bases de dades ofereixen la capacitat de crear estructures de dades d'índex de bases de dades. Els índexs milloren la velocitat de les operacions de cerca a costa d'espai addicional. Sense índexs, de vegades es requereixen operacions d'exploració de taula completa que requereixen temps per localitzar les dades desitjades.

Dades comprimides vs. no comprimides

Es pot aplicar una compensació espai-temps al problema de l'emmagatzematge de dades. Si les dades s'emmagatzemen sense comprimir, ocupen més espai, però l'accés triga menys que si les dades s'emmagatzemen comprimides (ja que comprimir les dades redueix la quantitat d'espai que ocupa, però es necessita temps per executar l'algorisme de descompressió). Depenent de la instància concreta del problema, qualsevol de les maneres és pràctica. També hi ha casos excepcionals en què és possible treballar directament amb dades comprimides, com en el cas dels índexs de mapes de bits comprimits, on és més ràpid treballar amb compressió que sense compressió.

Tornar a renderitzar vs. imatges emmagatzemades

Emmagatzemar només la font SVG d'una imatge vectorial i representar-la com a imatge de mapa de bits cada vegada que es sol·licita la pàgina seria intercanviar temps per espai; més temps utilitzat, però menys espai. Renderitzar la imatge quan es canvia la pàgina i emmagatzemar les imatges renderitzades seria intercanviar espai per temps; més espai utilitzat, però menys temps. Aquesta tècnica es coneix més generalment com a memòria cau.

Codi més petit vs. desenrotllament de bucle

Es pot canviar una mida de codi més gran per una velocitat de programa més alta quan s'aplica el desenrotllament del bucle. Aquesta tècnica fa que el codi sigui més llarg per a cada iteració d'un bucle, però estalvia el temps de càlcul necessari per tornar al començament del bucle al final de cada iteració.[4]

Altres exemples

Els algorismes que també fan ús de compensacions espai-temps inclouen:

Referències

  1. «Time-Space Trade-Off in Algorithms» (en anglès americà), 29-10-2020. [Consulta: 17 maig 2024].
  2. «Space–Time Tradeoffs» (en anglès). [Consulta: 17 maig 2024].
  3. «Chapter 7: Space-for-time tradeoffs» (en anglès). [Consulta: 17 maig 2024].
  4. «Algorithm complexity and time space trade off | Data Structures Using C Tutorials | Teachics» (en anglès americà), 03-06-2020. [Consulta: 17 maig 2024].

Read other articles:

У этого термина существуют и другие значения, см. Аврора. Аврора Современный вид крейсера «Аврора» Служба  Российская империя  РСФСР  СССР  СССР  Россия Назван в честь Аврора Класс и тип судна бронепалубный крейсер Порт приписки Кронштадт Ленинград Организа...

 

2019 Indian Hindi-language drama film by Banty Dubey This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (October 2019) Jacqueline I Am ComingFilm posterDirected byBanty DubeyWritten byPinku DubeyProduced byManjesh GiriStarringRaghubir YadavDiiva DhanoyaShakti KumarKiran PatilCinematographySaravanan ElavarasuEdited bySachin KunalMusic byVipin PatwaProductioncompanyMD ProductionDistribute...

 

985

Portal Geschichte | Portal Biografien | Aktuelle Ereignisse | Jahreskalender | Tagesartikel ◄ | 9. Jahrhundert | 10. Jahrhundert | 11. Jahrhundert | ► ◄ | 950er | 960er | 970er | 980er | 990er | 1000er | 1010er | ► ◄◄ | ◄ | 981 | 982 | 983 | 984 | 985 | 986 | 987 | 988 | 989 | ► | ►► Staatsoberhäupter · Nekrolog Kalenderübersicht 985 Januar Kw Mo Di Mi Do Fr Sa So 1       1 2 3 4 2 5 6 7 8 9 10 11 3 12 13 14 15...

American publishing company This article may rely excessively on sources too closely associated with the subject, potentially preventing the article from being verifiable and neutral. Please help improve it by replacing them with more appropriate citations to reliable, independent, third-party sources. (October 2015) (Learn how and when to remove this template message) Bedford/St. Martin'sParent companyMacmillan PublishersStatusActiveFounded1981FounderCharles Christensen and Joan Feinberg...

 

Mythological Swedish royal dynasty For other uses, see Yngling (disambiguation). The Yngling Ingjald slaying his kinsmen. The Ynglings were a dynasty of kings, first in Sweden and later in Norway, primarily attested through the poem Ynglingatal. The dynasty also appears as Scylfings (Old Norse Skilfingar) in Beowulf. When Beowulf and Ynglingatal were composed sometime in the eighth to tenth centuries, the respective scop and skald (poet) expected his audience to have a great deal of backgroun...

 

Anselmo Alliegro y Milá Anselmo Alliegro y Milá (* 8. Dezember 1899 in Yaguajay; † 22. November 1961 in New York City) war ein kubanischer Rechtsanwalt und Politiker, vom 1. bis 2. Januar 1959 geschäftsführender Präsident Kubas. Leben Alliegro war Sohn des italienischen Einwanderers Miguel Alliegro Esculpino und der aus Katalonien stammenden Donatila Milá. Im Laufe seiner politischen Laufbahn, zunächst in der Liberalen Partei (Partido Liberal) und später in der Fortschrittlichen Par...

American science fiction franchise This article is about the franchise. For the film, see Stargate (film). For the device itself, see Stargate (device). For other uses, see Stargate (disambiguation). StargateOfficial franchise logoCreated byDean DevlinRoland EmmerichOriginal workStargate (1994)OwnerMetro-Goldwyn-Mayer (series) StudioCanal (movie) Years1994–2018Print publicationsBook(s)List of novelsComicsList of comicsFilms and televisionFilm(s)Stargate (1994)Television seriesStargate SG-1 ...

 

U.S. House district for New York NY-9 redirects here. The term may also refer to New York State Route 9. New York's 9th congressional districtInteractive map of district boundaries since January 3, 2023Representative  Yvette ClarkeD–BrooklynDistribution100% urban0% ruralPopulation (2022)756,507[1]Median householdincome$71,800[2]Ethnicity50.5% Black31.2% White9.0% Hispanic6.8% Asian1.9% Two or more races0.6% otherCook PVID+25[3] New York's 9th congressional distr...

 

This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: 2014 Monza GP2 Series round – news · newspapers · books · scholar · JSTOR (July 2022) (Learn how and when to remove this template message)    2014 Monza GP2 roundRound details Round 9 of 11 rounds in the 2014 GP2 Series Layout of the Autodromo Nazionale MonzaLocation Autodromo Nazionale Monza, Mo...

1957 studio album by Elvis PresleyElvis' Christmas AlbumStudio album by Elvis PresleyReleasedOctober 15, 1957Recorded January 12–13 and 19, 1957 September 5–7, 1957 StudioRadio Recorders (Hollywood)Genre Christmas pop gospel rock and roll Length30:09LabelRCA VictorProducerSteve SholesElvis Presley chronology Loving You(1957) Elvis' Christmas Album(1957) Jailhouse Rock(1957) Singles from Elvis' Christmas Album Santa Bring My Baby Back (To Me)Released: November 11, 1957[1] B...

 

Metro station in Delhi, India Delhi University North Campus Delhi Metro stationSBI Vishwa Vidyalaya metro stationGeneral informationLocationThe Mall Rd, New Delhi, 110007IndiaCoordinates28°41′41.3″N 77°12′52.6″E / 28.694806°N 77.214611°E / 28.694806; 77.214611Owned byDelhi MetroLine(s)Yellow LinePlatformsSide platformPlatform-1 → HUDA City CentrePlatform-2 → Samaypur BadliTracks2ConstructionStructure typeUndergroundPlatform levels2Parking AvailableAcces...

 

American dramatist Oliver Bell BunceBorn(1828-02-08)February 8, 1828New York CityDiedMay 15, 1890(1890-05-15) (aged 62)New York City Oliver Bell Bunce (February 8, 1828 – May 15, 1890) was an American author, editor, and playwright. Life He was born in New York City, in his youth he joined his uncle's stationery house Jansen & Bell. While connected with this house he began writing plays, several of which were brought out. Fate or the Prophecy, a tragedy in blank verso, and Marco Bo...

American actor For other people named Christopher Knight, see Christopher Knight (disambiguation). Christopher KnightKnight in October 2010BornChristopher Anton Knight (1957-11-07) November 7, 1957 (age 66)New York City, U.S.[1]OccupationsActorbusinessmanYears active1967–presentKnown forPeter Brady in The Brady BunchThe Brady KidsA Very Brady ChristmasThe BradysSpouses Julie Schulman ​ ​(m. 1989; div. 1992)​ Toni Erickso...

 

Miss IndonesiaLogo Miss IndonesiaTanggal pendirian2005TipeKontes kecantikanKantor pusat JakartaLokasi IndonesiaJumlah anggota Miss World(2006-sekarang)Miss ASEAN (2005)Bahasa resmi IndonesiaChairwoman and FounderLiliana TanoesoedibjoTokoh pentingMartha TilaarWulan TilaarLina PriscillaSitus webwww.missindonesia.co.id Miss Sumatera Barat adalah sebuah gelar yang didapat bagi perwakilan provinsi Sumatera Barat di ajang Miss Indonesia. Pemegang titel saat ini adalah Julia Yasmin dari Tanah D...

 

This article is about the Arabian mountain range. For other uses, see Shammar (disambiguation). Mountain range in Saudi Arabia Shammar MountainsThe area of 'Uqdah on the outskirts of Ha'ilNamingNative nameجِبَال شَمَّر (Arabic)GeographyShow map of Saudi ArabiaShow map of Middle EastShow map of Asia Country Saudi ArabiaRegionHa'ilRange coordinates27°30′N 41°36′E / 27.5°N 41.6°E / 27.5; 41.6 The Shammar Mountains (Arabic: جِبَال شَم...

2016 single by Usher featuring FutureRivalsSingle by Usher featuring Futurefrom the album Hard II Love ReleasedAugust 30, 2016 (2016-08-30)Length3:49LabelRCASongwriter(s)Usher Raymond IVKendricke BrownCameron MurphyParis JonesCarlos St JohnNayvadius WilburnProducer(s)K-MajorMurphy KidUsher singles chronology Missin U (2016) Rivals (2016) Party (2016) Future singles chronology Too Much Sauce(2016) Rivals(2016) Used to This(2016) Music videoRivals on YouTube Rivals is a s...

 

German commercial transport finance company DVB Bank SETypeSocietas EuropaeaISINDE0008045501IndustryBankingFounded1923HeadquartersFrankfurt, GermanyArea servedWorldwideKey peopleRalf Bedranowsky (CEO), Rainer JakubowskiProductsFinancial servicesAUM€10.2 billion (2020)OwnerDZ BANK (100%)Number of employees329 (2020)Websitewww.dvbbank.com DVB Bank SE is part of the DZ BANK Group and a specialist in international transportation finance, based in Frankfurt/Main, Germany. The Bank was listed on ...

 

Local government area in New South Wales, AustraliaCity of Canterbury-BankstownNew South WalesLocation of Canterbury-Bankstown in Sydney areaPopulation 346,302 (2016 census)[1] (4th in Australia; 2nd in NSW) 410,419 (2022 est.)[2] • Density3,125.5/km2 (8,095/sq mi)Established12 May 2016Area110.8 km2 (42.8 sq mi)MayorBilal El-Hayek (Labor)Region Inner West South Western Sydney State electorate(s)BankstownCanterburyEast HillsStrathfieldS...

1990 Indian filmGaneshana MaduveFilm posterDirected byH.S. Phani RamachandraWritten byRajachandurScreenplay byKunigal NagabhushanStory byMalladi Venkata Krishna MurthyBased onVinayaka Rao Pelliby Malladi Venkata KrishnamurthyProduced byManikchandStarringAnant NagVinaya PrasadAnjaliMukhyamantri ChandruRamesh BhatCinematographyR. ManjunathEdited bySuresh UrsMusic byRajan–NagendraDistributed byShakti ProductionsRelease date 1990 (1990) CountryIndiaLanguageKannada Ganeshana Maduve (transl....

 

American photographer (born 1968) For other people named Karl Larsen, see Karl Larsen (disambiguation). Karl LarsenBorn (1968-09-25) September 25, 1968 (age 55)Brooklyn, New York, U.S.OccupationPhotographerSpouse Anelize Ferrer Flores ​ ​(m. 2005)​ Karl Larsen (born September 25, 1968) is an American photographer who is known for photographing several celebrities. His best known shot is one of Paris Hilton crying in the back of a police car after she wa...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!