Pidetäänkö vakioaikaa ja jaksotettua vakioaikaa tosiasiallisesti vastaavina?

Lyhennettyä vakioaikaa voidaan melkein aina pitää vakioaikaa vastaavana, tietämättä sovelluksesi yksityiskohtia ja käyttötyyppiä, johon aiot tehdä tässä jonossa, useimmat mahdollisuudet ovat, että sinut katetaan.

Taulukko-luettelossa on käsite kapasiteetti , joka on periaatteessa yhtä suuri kuin suurin kohteiden koko / pituus / määrä sitä on toistaiseksi vaadittu. Joten mitä tapahtuu, on se, että alussa taulukkoluettelo jatkaa itsensä jakamista kapasiteettinsa lisäämiseksi, kun lisäät siihen kohteita, mutta jossain vaiheessa keskimääräinen lisättyjen tuotteiden määrä aikayksikköä kohden väistämättä vastaa keskimääräistä kohteiden määrää poistettu aikayksikköä kohti (muuten muistisi loppuisi silti joka tapauksessa), jolloin matriisi lopettaa itsensä jakamisen uudelleen, ja kaikki liitteet täyttyvät O: n (1) vakiona.

Kuitenkin , pidä mielessä, että oletusarvoisesti satunnainen poistaminen taulukkoluettelosta ei ole O (1), vaan O (N), koska taulukkoluettelot siirtävät kaikki poistetun kohteen jälkeen olevat kohteet yhden sijainnin alaspäin poistetun kohteen paikalle. . O (1) -arvon saavuttamiseksi sinun on korvattava oletusarvoinen tapa korvata poistettu kohde kopiolla viimeisen matriisiluettelon kohdasta ja poistaa sitten viimeinen kohde siten, että yhtään kohdetta ei siirretä. Mutta silloin, jos teet niin, sinulla ei ole enää jonoa.

Kommentit

• Hitto, hyvä kohta poistamisiin; En ottanut huomioon ’. Ja koska me ’ poistamme elementit satunnaisesti, ei ’ t tarkoita sitä teknisesti ’ eikö ole enää jonoa siinä mielessä?
• Kyllä, se tarkoittaa, ettet tosiasiassa käsittele sitä jonona. Mutta en tiedä miten aiot löytää poistettavat kohteet. Jos mekanismisi löytää ne odottaa heidän olevan läsnä jonossa siinä järjestyksessä kuin ne on lisätty, sinulla ei ole onnea.Jos et välitä, jos kohteiden järjestys hämmentyy, olet kunnossa.
• Odotan, että RandomQueue toteuttaa Queue -rajapinta ja toimitetulle remove -menetelmälle satunnaisesti poistettavaksi pään ponnahduksen sijasta, joten ’ t olla mikä tahansa tapa luottaa tiettyyn tilaukseen. Luulen, että kun otetaan huomioon sen satunnainen luonne, käyttäjän ei pitäisi ’ odottaa sen pitävän tiettyä järjestystä. Lainasin tehtävääni selvennykseksi. Kiitos.
• Kyllä, näyttää siltä, että sinä olet kunnossa, jos vain varmistat, että kohteen poisto tapahtuu samalla tavalla kuin ehdotin.
• Viimeinen asia, jos et ’ t mieli. Olen ’ ajatellut sitä enemmän, eikä se näytä siltä, että se olisi ’ s voi olla sekä ” true ” O (1) -lisäys että ” true ” O (1) satunnainen poisto; se ’ ll on kompromissi 2: n välillä. Sinulla on joko yksitellen allokoitu rakenne (kuten taulukko), joka antaa poiston, mutta ei additonia, tai palan allokoitu rakenne, kuten Linked- Luettelo, joka antaa lisäyksiä, mutta ei poisto. Onko tämä totta? Kiitos vielä kerran.

Kysymys näyttää nimenomaisesti pyytävän jatkuvaa aikaa eikä lyhennetty vakioaika . Joten lainatun kysymyksen osalta, ei, ne eivät ole tosiasiallisesti samanlaisia *. Ovatko ne tosielämän sovelluksissa?

Tyypillinen amortizoidun vakion ongelma on se, että joskus joudut maksamaan kertyneen velan. Joten vaikka insertit ovat yleensä vakioita, joskus joudut kärsimään kaiken uudelleen asettamisesta uudelleen, kun uusi lohko jaetaan.

Missä vakioajan ja amortisoidun vakioajan välinen ero on sovelluksen kannalta merkityksellinen, riippuu siitä, onko tämä satunnainen erittäin hidas nopeus on hyväksyttävä. Hyvin suurelle määrälle verkkotunnuksia tämä on yleensä ok. Varsinkin jos säiliöllä on todellinen enimmäiskoko (kuten välimuistit, väliaikaiset puskurit, työskentelysäiliöt), voit maksaa ne tehokkaasti vain kerran suorituksen aikana.

Kriittisissä sovelluksissa näitä aikoja ei voida hyväksyä. Jos sinun on täytettävä lyhytaikainen läpimenotakuu, et voi luottaa algoritmiin, joka toisinaan ylittää sen. Olen työskennellyt aiemmin sellaisissa projekteissa, mutta ne ovat erittäin harvinaisia.

Se riippuu myös siitä, kuinka korkeat nämä kustannukset todella ovat. Vektorit toimivat yleensä hyvin, koska niiden uudelleenjakokustannukset ovat suhteellisen alhaiset. Jos kuitenkin siirryt hash-kartalle, uudelleenjako voi olla paljon suurempi. Vaikka jälleen kerran, useimmissa sovelluksissa luultavasti hieno, varsinkin pidempään eläneet palvelimet, joiden yläosassa olevat säiliön kohteet ovat.

* Tässä on kuitenkin pieni ongelma. Yleiskäyttöisen säilön tekemiseksi olla vakio aika lisäykselle, jompikumpi kahdesta asiasta pitää sisällään:

• Säiliön on oltava kiinteä enimmäiskoko; tai
• voit olettaa, että yksittäisten elementtien muistin kohdennus on vakioaika .

kommentit

• ” maksapalvelin ” tuntuu oudolta käyttää tässä lauseita. Tarkoitatko ehkä ” live-palvelinta ”?

Se riippuu siitä, optimoitko suoritustehon vai viiveen:

• Viive- herkät järjestelmät tarvitsevat tasaisen suorituskyvyn. Tällaisessa tilanteessa meidän on korostettava järjestelmän pahinta mahdollista käyttäytymistä. Esimerkkejä ovat pehmeät reaaliaikaiset järjestelmät, kuten Pelit, jotka haluavat saavuttaa yhdenmukaisen kehysnopeuden, tai verkkopalvelimet, joiden on lähetettävä vastaus tietyssä tiukassa aikataulussa: CPU-jaksojen tuhlaaminen on parempi kuin myöhästyminen.
• Suorituskykyoptimoidut järjestelmät eivät välitä satunnaisia pysähdyksiä, kunhan datan enimmäismäärä voidaan käsitellä pitkällä aikavälillä. Täällä olemme ensisijaisesti kiinnostuneita jaksotetusta tuotosta. Tämä pätee yleensä numeroiden murskaamiseen tai muihin eräkäsittelytyöihin.

Huomaa, että yhdessä järjestelmässä voi olla erilaisia komponentteja, jotka on luokiteltava eri tavalla. Esimerkiksi. nykyaikaisella tekstinkäsittelylaitteella olisi viiveherkkä käyttöliittymäketju, mutta suorituskykyoptimoidut ketjut muihin tehtäviin, kuten oikeinkirjoituksen tarkistus tai PDF-vienti.

Algoritmisella monimutkaisuudella ei myöskään ole väliä niin paljon kuin meillä saattaa olla ajatella: Kun ongelma liittyy tiettyyn lukuun, todelliset ja mitatut suorituskykyominaisuudet ovat tärkeämpiä kuin käyttäytyminen ”erittäin suurille n ”.

Kommentit

• Minulla on valitettavasti hyvin vähän taustaa.Kysymys päättyy seuraavasti: ” RandomQueue-toiminnon add (x) – ja remove () -operaatioiden tulisi toimia vakiona jatkuvaa operaatiota kohti ”. ohjelmointiharjoitus tai testi. Ja varmasti ei helppo. Ehdottomasti totta, että sillä on hyvin harvoin merkitystä.

Jos sinulta kysytään ”lyhennettyä vakioaikaa” algoritmi, algoritmisi voi joskus kestää kauan. Esimerkiksi, jos käytät std :: vektoria C ++: ssa, tällainen vektori voi olla varannut tilaa 10 objektille, ja kun varaat 11. objektin, varataan tilaa 20 objektille, 10 objektia kopioidaan ja 11. lisätään, mikä vie paljon aikaa. Mutta jos lisäät miljoonan objektin, sinulla voi olla 999 980 nopeaa ja 20 hidasta operaatiota, keskimääräinen aika on nopea.

Jos sinulta kysytään ”vakioaika” -algoritmia, algoritmin on aina oltava nopea jokaista operaatiota varten. Se olisi tärkeää reaaliaikaisille järjestelmille, joissa saatat tarvita takuun siitä, että jokainen yksittäinen operaatio on aina nopea. ”Vakioaikaa” ei usein tarvita, mutta se on ehdottomasti ei sama kuin ”lyhennetty vakioaika”.