Il tempo costante e il tempo costante ammortizzato sono effettivamente considerati equivalenti?

Il tempo costante ammortizzato può quasi sempre essere considerato equivalente al tempo costante e senza conoscere le specifiche della tua applicazione e il tipo di utilizzo che intendi fare questa coda, la maggior parte delle possibilità sono che sarai coperto.

Un elenco di array ha il concetto di capacità , che è fondamentalmente uguale alla dimensione / lunghezza / numero di elementi più grandi che finora ne è mai stato richiesto. Quindi, ciò che accadrà è che allinizio lelenco dellarray continuerà a riallocarsi per aumentare la sua capacità man mano che continui ad aggiungervi elementi, ma a un certo punto il numero medio di elementi aggiunti per unità di tempo corrisponderà inevitabilmente al numero medio di elementi rimosso per unità di tempo, (altrimenti finiresti comunque la memoria), a quel punto larray smetterà di riallocarsi e tutte le aggiunte saranno soddisfatte al tempo costante di O (1).

Tuttavia , tieni presente che per impostazione predefinita, la rimozione casuale da un elenco di array non è O (1), è O (N), perché gli elenchi di array spostano tutti gli elementi dopo lelemento rimosso di una posizione verso il basso per prendere il posto dellelemento rimosso . Per ottenere O (1) dovrai sovrascrivere il comportamento predefinito per sostituire lelemento rimosso con una copia dellultimo elemento dellelenco dellarray, quindi rimuovere lultimo elemento, in modo che nessun elemento venga spostato. Ma poi, se lo fai, non hai più esattamente una coda.

Commenti

• Dannazione, buon punto sulle rimozioni; Non ‘ lo consideravo. E poiché ‘ stiamo rimuovendo elementi in modo casuale, ‘ non significa tecnicamente ‘ Non è più una coda in quel senso comunque?
• Sì, significa che non la stai davvero trattando come una coda. Ma non so come pensi di trovare gli elementi da rimuovere. Se il tuo meccanismo per trovarli si aspetta che siano presenti nella coda nellordine in cui sono stati aggiunti, allora sei sfortunato.Se non ti interessa se lordine degli elementi viene alterato, allora stai bene.
• Laspettativa è che il mio RandomQueue implementi Queue e per il metodo remove fornito per rimuovere in modo casuale invece di far scoppiare la testa, quindi non dovrebbe ‘ Non è possibile fare affidamento su un ordine specifico. Penso che, data la sua natura casuale, lutente non dovrebbe ‘ aspettarsi che mantenga un ordine specifico. Ho citato il compito nella mia domanda per chiarimenti. Grazie.
• Sì, sembra che andrà tutto bene se ti assicuri che la rimozione degli elementi venga eseguita nel modo da me suggerito.
• Unultima cosa se non ‘ t mente. ‘ ci ho pensato di più e non ‘ sembra ‘ È possibile avere sia ” true ” O (1) aggiunte e ” true ” O (1) rimozione casuale; ‘ sarà un compromesso tra i 2. O hai una struttura allocata singolarmente (come un array) che fornisce la rimozione ma non laggiunta, o una struttura allocata in blocchi come un Linked- Elenco che fornisce aggiunte ma non eliminazioni. È vero? Ancora una volta, grazie.

La domanda sembra chiedere specificamente un tempo costante, e non un tempo costante ammortizzato . Quindi, rispetto alla domanda citata, no, non sono effettivamente la stessa cosa *. Sono comunque in applicazioni del mondo reale?

Il problema tipico con la costante ammortizzata è che a volte devi pagare il debito accumulato. Quindi, sebbene gli inserimenti siano generalmente costanti, a volte devi sopportare il sovraccarico di reinserire tutto di nuovo quando viene allocato un nuovo blocco.

Dove la differenza tra tempo costante e tempo costante ammortizzato è rilevante per unapplicazione dipende dal fatto che questa velocità molto bassa occasionale è accettabile. Per un numero molto elevato di domini questo va generalmente bene. Soprattutto se il contenitore ha una dimensione massima effettiva (come cache, buffer temporanei, contenitori funzionanti) potresti effettivamente pagare i costi solo una volta durante lesecuzione.

In applicazioni critiche questi tempi potrebbero essere inaccettabili. Se ti viene richiesto di soddisfare una garanzia di consegna a breve termine, non puoi fare affidamento su un algoritmo che occasionalmente lo supererà. Ho già lavorato a progetti del genere, ma sono estremamente rari.

Dipende anche da quanto sia alto questo costo. I vettori tendono a funzionare bene poiché il loro costo di riallocazione è relativamente basso. Se vai alla mappa hash, tuttavia, la riallocazione può essere molto più alta. Anche se, di nuovo, per la maggior parte delle applicazioni probabilmente va bene, specialmente i server più longevi con un limite superiore agli elementi nel contenitore.

* Cè un po di problema qui però. Al fine di rendere qualsiasi contenitore generico essere un tempo costante per linserimento una delle due cose deve valere:

• Il contenitore deve avere una dimensione massima fissa; oppure
• puoi assumere che lallocazione della memoria dei singoli elementi sia tempo costante .

Commenti

• ” liver server ” sembra una frase strana da usare qui. Vuoi dire ” live server ” forse?

Dipende – dallottimizzazione della velocità effettiva o della latenza:

• Latenza- sistemi sensibili richiedono prestazioni costanti. Per uno scenario del genere, dobbiamo enfatizzare il comportamento nel caso peggiore del sistema. Esempi sono sistemi soft real time s giochi che vogliono ottenere un framerate coerente, o server web che devono inviare una risposta entro un certo lasso di tempo ristretto: sprecare cicli della CPU è meglio che arrivare in ritardo.
• I sistemi ottimizzati per il throughput non si preoccupano blocchi occasionali, a condizione che la quantità massima di dati possa essere elaborata a lungo termine. In questo caso siamo principalmente interessati alla performance ammortizzata. Questo è generalmente il caso del calcolo dei numeri o di altri lavori di elaborazione in batch.

Nota che un sistema può avere diversi componenti che devono essere classificati in modo diverso. Per esempio. un moderno elaboratore di testi avrebbe un thread dellinterfaccia utente sensibile alla latenza, ma thread ottimizzati per il throughput per altre attività come il controllo ortografico o le esportazioni di PDF.

Inoltre, la complessità algoritmica spesso non ha importanza quanto potremmo pensa: quando un problema è limitato a un certo numero, le caratteristiche delle prestazioni effettive e misurate sono più importanti del comportamento “per n molto grandi”.

Commenti

• Sfortunatamente, ho pochissime conoscenze.La domanda termina con: ” Le operazioni add (x) e remove () in una RandomQueue devono essere eseguite a tempo costante per operazione “.
• @Carcigenicate a meno che tu non sappia per certo che il sistema è sensibile alla latenza, luso della complessità ammortizzata per selezionare una struttura dati dovrebbe essere assolutamente sufficiente.
• Ho limpressione che potrebbe essere un esercizio di programmazione o un test. E certamente non facile. Assolutamente vero che raramente è importante.

Se ti viene chiesto un “tempo costante ammortizzato” algoritmo, il tuo algoritmo può a volte richiedere molto tempo. Ad esempio, se si utilizza std :: vector in C ++, tale vettore potrebbe avere spazio allocato per 10 oggetti e quando si alloca lundicesimo oggetto, viene allocato lo spazio per 20 oggetti, vengono copiati 10 oggetti e lundicesimo aggiunto, che richiede molto tempo. Ma se aggiungi un milione di oggetti, potresti avere 999.980 operazioni veloci e 20 lente, con un tempo medio veloce.

Se ti viene chiesto un algoritmo “tempo costante”, il tuo algoritmo deve essere sempre veloce, per ogni singola operazione. Ciò sarebbe importante per i sistemi in tempo reale in cui potresti aver bisogno di una garanzia che ogni singola operazione sia sempre veloce. Il “tempo costante” molto spesso non è necessario, ma non è decisamente uguale al “tempo costante ammortizzato”.