Betraktas konstant tid och amorterad konstant tid likvärdigt?

Amorterad konstant tid kan nästan alltid betraktas som motsvarande konstant tid och utan att känna till din applikations detaljer och vilken typ av användning du planerar att göra för den här kön är det mesta chansen att du kommer att täckas.

En matrislista har begreppet kapacitet som i princip är lika med den största storleken / längden / antalet objekt som någonsin har krävts av det hittills. Så, vad som kommer att hända är att i början kommer array-listan att fortsätta omfördela sig för att öka sin kapacitet när du fortsätter att lägga till objekt, men vid något tillfälle kommer det genomsnittliga antalet artiklar som läggs till per tidsenhet oundvikligen att matcha det genomsnittliga antalet artiklar borttagen per tidsenhet (annars skulle du så småningom ta slut på minnet ändå), vid vilken tidpunkt matrisen slutar omfördela sig själv, och alla tillägg kommer att uppfyllas vid konstant tid av O (1).

Men , kom ihåg att som standard slumpmässigt borttagning från en matrislista inte är O (1), det är O (N), eftersom matrislistor flyttar alla objekt efter det borttagna objektet en position nedåt för att ta platsen för det borttagna objektet . För att uppnå O (1) måste du åsidosätta standardbeteendet för att ersätta det borttagna objektet med en kopia av det sista objektet i matrislistan och sedan ta bort det sista objektet så att inga objekt flyttas. Men då, om du gör det, har du inte precis en kö längre.

Kommentarer

• Fan, bra poäng för borttagningar; Jag tänkte inte ’. Och eftersom vi ’ slumpmässigt tar bort element, betyder inte ’ det som tekniskt betyder det ’ Är det inte längre en kö i den meningen ändå?
• Ja, det betyder att du inte riktigt behandlar den som en kö. Men jag vet inte hur du planerar att hitta de objekt som ska tas bort. Om din mekanism för att hitta dem förväntar sig att de ska finnas i kön i den ordning de lades till, har du ingen tur.Om du inte bryr dig om varornas ordning blir förvirrad, så går du bra.
• Förväntningen är att min RandomQueue ska implementera Queue gränssnitt och för den medföljande remove -metoden för att slumpmässigt ta bort istället för att poppa huvudet, så det borde inte finnas ’ inte vara något sätt att förlita sig på en specifik beställning. Jag tror med tanke på den slumpmässiga karaktären av det då, att användaren inte ’ t förväntar sig att den ska behålla någon specifik ordning. Jag citerade uppgiften i min fråga för förtydligande. Tack.
• Ja då, det verkar som om det går bra om du bara ser till att artikelborttagningen görs som jag föreslog.
• En sista sak om du inte ’ t sinne. Jag ’ har funderat över det mer och det verkar inte som ’ ’ s möjligt att ha både ” true ” O (1) tillägg och ” true ” O (1) slumpmässig borttagning; det ’ kommer att vara en avvägning mellan 2. Du har antingen enstaka allokerad struktur (som en matris) som ger borttagning men inte tillägg, eller en bitallokerad struktur som en länkad Lista som ger tillägg men inte borttagning. Är detta sant? Återigen tack.

Frågan verkar specifikt fråga om konstant tid och inte en amorterad konstant tid . Så med avseende på den citerade frågan, nej, de är i själva verket inte samma *. Finns de dock i verkliga applikationer?

Det typiska problemet med amorterad konstant är att du ibland måste betala den ackumulerade skulden. Så medan insatser i allmänhet är konstanta måste du ibland drabbas av att sätta in allt igen när ett nytt block tilldelas.

Där skillnaden mellan konstant tid och amorterad konstant tid är relevant för en applikation beror på om denna tillfälliga mycket långsamma hastighet är acceptabel. För ett mycket stort antal domäner är det i allmänhet okej. Speciellt om behållaren har en effektiv maximal storlek (som cachar, temp buffertar, fungerande behållare) kan du effektivt betala de kostar bara en gång under körningen.

Som svarskritiska applikationer kan dessa tider vara oacceptabla. Om du är skyldig att uppfylla en kort tids garanti kan du inte lita på en algoritm som ibland överskrider den. Jag har arbetat med sådana projekt tidigare, men de är oerhört sällsynta.

Det beror också på hur hög denna kostnad faktiskt är. Vektorer tenderar att prestera bra eftersom deras omfördelningskostnad är relativt låg. Om du går till hash-kartan kan omfördelningen dock vara mycket högre. Men igen, för de flesta applikationer förmodligen bra, särskilt längre livslängda servrar med en övre gräns på objekten i behållaren.

* Det är dock lite av ett problem här. För att göra en behållare för allmänt ändamål vara konstant tid för insättning en av två saker måste innehålla:

• Behållaren måste ha en fast maximal storlek; eller
• du kan anta att minnet tilldelas enskilda element är konstant tid .

Kommentarer

• ” leverserver ” verkar en konstig formulering att använda här. Menar du ” live-server ” kanske?

Det beror på – om du optimerar för genomströmning eller för latens:

• Latens- känsliga system behöver konsekvent prestanda. För ett sådant scenario måste vi betona systemets värsta fall. Exempel är mjuka realtidsystem, t.ex. s spel som vill uppnå en konsekvent framrate eller webbservrar som måste skicka ett svar inom en viss kort tidsram: att slösa med CPU-cykler är bättre än att vara sen.
• Genomströmningsoptimerade system bryr sig inte om enstaka bås, så länge den maximala mängden data kan behandlas på lång sikt. Här är vi främst intresserade av amorterad prestanda. Detta är i allmänhet fallet för nummerkramning eller andra batchbearbetningsjobb.

Observera att ett system kan ha olika komponenter som måste kategoriseras olika. T.ex. en modern textbehandlare skulle ha en latenskänslig UI-tråd, men genomströmningsoptimerade trådar för andra uppgifter som stavningskontroll eller PDF-export.

Algoritmisk komplexitet spelar ofta inte lika mycket roll som vi skulle kunna tänk: När ett problem är begränsat till ett visst antal är faktiska och uppmätta prestandaegenskaper viktigare än beteendet ”för mycket stora n ”.

Kommentarer

• Tyvärr har jag väldigt lite bakgrund.Frågan slutar med: ” Funktionerna add (x) och remove () i en RandomQueue ska köras i konstant tid per operation ”.
• @Carcigenicate om du inte vet att systemet är latens-känsligt, att använda amorterad komplexitet för att välja en datastruktur borde vara helt tillräcklig.
• Jag har intrycket att detta kan vara en programmeringsövning eller ett test. Och absolut inte lätt. Helt sant att det väldigt sällan spelar roll.

Om du blir ombedd om en ”amorterad konstant tid” algoritm, kan din algoritm ibland ta lång tid. Om du till exempel använder std :: vector i C ++ kan en sådan vektor ha tilldelat utrymme för 10 objekt, och när du tilldelar det 11: e objektet tilldelas plats för 20 objekt, 10 objekt kopieras och det 11: e läggs till, vilket tar lång tid. Men om du lägger till en miljon objekt kan du ha 999.980 snabba och 20 långsamma operationer, med genomsnittlig tid är snabb.

Om du blir ombedd att använda en ”konstant tid” -algoritm måste din algoritm alltid vara snabb för varje enskild åtgärd. Det skulle vara viktigt för system i realtid där du kan behöva en garanti för att varje enskild åtgärd är alltid snabb. ”Konstant tid” behövs ofta inte, men det är definitivt inte samma som ”amorterad konstant tid”.