Worden constante tijd en geamortiseerde constante tijd effectief als gelijkwaardig beschouwd?

Afgeschreven constante tijd kan bijna altijd worden beschouwd als gelijkwaardig aan constante tijd, en zonder de specifieke kenmerken van uw toepassing en het type gebruik dat u van plan bent te doen deze wachtrij is de meeste kans dat u gedekt wordt.

Een arraylijst heeft het concept capaciteit , wat in feite gelijk is aan de grootste afmeting / lengte / aantal items die is er tot nu toe ooit van geëist. Dus wat er zal gebeuren is dat in het begin de arraylijst zichzelf blijft heralloceren om de capaciteit te vergroten terwijl je er items aan toevoegt, maar op een gegeven moment zal het gemiddelde aantal items dat per tijdseenheid wordt toegevoegd onvermijdelijk overeenkomen met het gemiddelde aantal items. verwijderd per tijdseenheid, (anders zou je uiteindelijk toch geen geheugen meer hebben), waarna de array zichzelf niet meer opnieuw toewijst, en aan alle toevoegingen wordt voldaan op de constante tijd van O (1).

Echter , houd er rekening mee dat willekeurige verwijdering uit een arraylijst standaard niet O (1) is, maar O (N), omdat arraylijsten alle items na het verwijderde item een positie naar beneden verplaatsen om de plaats van het verwijderde item in te nemen . Om O (1) te bereiken, moet u het standaardgedrag overschrijven om het verwijderde item te vervangen door een kopie van het laatste item van de arraylijst en vervolgens het laatste item te verwijderen, zodat er geen items worden verplaatst. Maar als je dat doet, heb je niet echt een wachtrij meer.

Reacties

• Verdomme, goed punt over verwijderingen; Dat heb ik ‘ niet overwogen. En aangezien we ‘ elementen willekeurig verwijderen, betekent niet ‘ dat dit technisch gezien ‘ s in die zin sowieso niet langer een wachtrij?
• Ja, het betekent wel dat je het niet echt als een wachtrij behandelt. Maar ik weet niet hoe u van plan bent de items te vinden die u wilt verwijderen. Als uw mechanisme om ze te vinden verwacht dat ze in de wachtrij staan in de volgorde waarin ze zijn toegevoegd, dan heeft u pech.Als het je niet uitmaakt of de volgorde van de items onleesbaar wordt, dan is alles goed.
• De verwachting is dat mijn RandomQueue de Queue interface, en om de meegeleverde remove -methode willekeurig te verwijderen in plaats van de kop te laten knallen, dus ‘ Er is geen enkele manier om te vertrouwen op een specifieke volgorde. Ik denk dat, gezien de willekeurige aard ervan, de gebruiker niet ‘ mag verwachten dat het een bepaalde volgorde behoudt. Ik citeerde de opdracht in mijn vraag ter verduidelijking. Dank je.
• Ja, het lijkt erop dat het goed komt als je ervoor zorgt dat het verwijderen van items gebeurt zoals ik heb voorgesteld.
• Nog een laatste ding als je don ‘ t geest. Ik ‘ heb er meer over nagedacht, en het lijkt niet ‘ het lijkt ‘ Het is mogelijk om beide ” true ” O (1) toevoegingen en ” true ” O (1) willekeurige verwijdering; het ‘ zal een afweging zijn tussen de 2. Je hebt ofwel een enkelvoudig toegewezen structuur (zoals een array) die verwijdering geeft maar geen toevoeging, of een blok toegewezen structuur zoals een Linked- Lijst met toevoegingen maar geen verwijdering. Is dit waar? Nogmaals bedankt.

De vraag lijkt specifiek te vragen om constante tijd, en niet een afgeschreven constante tijd . Dus met betrekking tot de geciteerde vraag: nee, ze zijn niet in feite hetzelfde *. Zijn ze echter in toepassingen in de echte wereld?

Het typische probleem met afgeschreven constante is dat u af en toe de opgebouwde schuld moet betalen. Dus hoewel inserts over het algemeen constant zijn, heb je soms last van de overhead van alles opnieuw inbrengen wanneer een nieuw blok wordt toegewezen.

Waar het verschil tussen constante tijd en geamortiseerde constante tijd relevant is voor een toepassing, hangt ervan af of deze af en toe zeer lage snelheid is acceptabel. Voor een zeer groot aantal domeinen is dit doorgaans oké. Vooral als de container een effectieve maximale grootte heeft (zoals caches, tijdelijke buffers, werkende containers), zou je deze kosten effectief maar één keer kunnen betalen tijdens de uitvoering.

Als reactie op kritieke applicaties kunnen deze tijden onaanvaardbaar zijn. Als u aan een garantie voor een korte doorlooptijd moet voldoen, kunt u niet vertrouwen op een algoritme dat dat af en toe overschrijdt. Ik heb eerder aan dergelijke projecten gewerkt, maar ze zijn buitengewoon zeldzaam.

Het hangt er ook van af hoe hoog deze kosten eigenlijk zijn. Vectoren presteren doorgaans goed omdat hun herallocatiekosten relatief laag zijn. Als je echter naar de hash-map gaat, kan de herverdeling een stuk hoger zijn. Maar nogmaals, voor de meeste toepassingen waarschijnlijk prima, vooral servers met een langere levensduur met een bovengrens voor de items in de container.

* Er is hier echter een klein probleem. Om een container voor algemeen gebruik te maken een constante tijd zijn voor invoeging, een van de volgende twee dingen moet gelden:

• De container moet een vaste maximale grootte hebben; of
• je kunt ervan uitgaan dat de geheugentoewijzing van individuele elementen constante tijd is .

Reacties

• ” leverserver ” lijkt een vreemde bewoording om hier te gebruiken. Bedoel je ” live server ” misschien?

Het hangt ervan af – of u optimaliseert voor doorvoer of voor latentie:

• Latency- gevoelige systemen hebben consistente prestaties nodig. Voor een dergelijk scenario moeten we de nadruk leggen op het slechtste gedrag van het systeem. Voorbeelden zijn zachte real-time systemen zoals s games die een consistente framerate willen bereiken, of webservers die binnen een bepaald krap tijdsbestek een reactie moeten verzenden: CPU-cycli verspillen is beter dan te laat komen.
• Doorvoer geoptimaliseerde systemen geven niet om incidentele onderbrekingen, zolang de maximale hoeveelheid gegevens op de lange termijn kan worden verwerkt. Hier zijn we vooral geïnteresseerd in geamortiseerde prestaties. Dit is over het algemeen het geval bij het verwerken van cijfers of andere batchverwerkingstaken.

Merk op dat een systeem verschillende componenten kan hebben die verschillend moeten worden gecategoriseerd. Bijv. een moderne tekstverwerker zou een vertragingsgevoelige UI-thread hebben, maar doorvoer geoptimaliseerde threads voor andere taken, zoals spellingcontrole of PDF-export.

Ook doet algoritmische complexiteit er vaak niet zoveel toe als we zouden kunnen. denk: wanneer een probleem aan een bepaald getal is gebonden, zijn feitelijke en gemeten prestatiekenmerken belangrijker dan het gedrag “voor zeer grote n “.

Opmerkingen

• Helaas heb ik weinig achtergrondinformatie.De vraag eindigt met: ” De bewerkingen add (x) en remove () in een RandomQueue moeten in constante tijd per bewerking worden uitgevoerd “.
• @Carcigenicate tenzij je zeker weet dat het systeem latentiegevoelig is, zou het gebruik van geamortiseerde complexiteit om een datastructuur te selecteren absoluut voldoende moeten zijn.
• Ik heb de indruk dat dit zou kunnen zijn een programmeeroefening of een test. En zeker geen gemakkelijke. Absoluut waar dat het zelden uitmaakt.

Als u wordt gevraagd om een “afgeschreven constante tijd” algoritme, kan uw algoritme soms lang duren. Als u bijvoorbeeld std :: vector in C ++ gebruikt, kan een dergelijke vector ruimte hebben toegewezen aan 10 objecten, en wanneer u het 11e object toewijst, wordt er ruimte voor 20 objecten toegewezen, worden 10 objecten gekopieerd en wordt de 11e toegevoegd, die kost veel tijd. Maar als u een miljoen objecten toevoegt, heeft u mogelijk 999.980 snelle en 20 langzame bewerkingen, waarbij de gemiddelde tijd snel is.

Als u wordt gevraagd om een “constante tijd” -algoritme, moet uw algoritme altijd snel zijn, voor elke afzonderlijke bewerking. Dat zou belangrijk zijn voor real-time systemen waar je misschien een garantie nodig hebt dat elke afzonderlijke bewerking altijd snel is. “Constante tijd” is vaak niet nodig, maar het is beslist niet hetzelfde als “afgeschreven constante tijd”.