Il modo migliore per implementare un tipo di stack dinamica? O sto abusando realloc?

Question

sto usando un linguaggio oscuro che non ha un tipo di stack nativo così ho implementato il mio. Ora, leggendo in rete ho trovato un paio di approcci diversi per farlo.

Questa è la mia implementazione (codice pseudo)

//push method
function Push(int)
{
    Increase (realloc) stack by 4 bytes;
    Push int into the new memory area;
}

//pop method
function Pop()
{
    collect int from the top of the stack;
    reallocate (realloc) the stack to shrink it by 4 bytes;
    return int;
}

Ora, alcune persone dicono che l'uso di un realloc () chiamata per ridimensionare lo stack dopo popping un valore non è male per le prestazioni così ho alcune domande:

1. E 'meglio crescere solo lo stack utilizzando malloc poi liberarlo alla fine del programma?
2. Per ridimensionare lo stack (push) è la cosa migliore per aumentare di 4 byte o più?
3. E 'best practice per aumentare lo stack raddoppiando la memoria allocata quando è pieno?
4. Quali sono i tuoi pensieri del codice di cui sopra?

Answer 1

La tecnica standard è crescere solo la dimensione di un fattore 2, e ridurla solo quando l'utilizzo di memoria effettiva è inferiore a quarto.

In questo modo si può essere sicuri che non si utilizza mai più di O (la memoria è necessario), e si può anche dimostrare che la pila viene ammortizzato costante di tempo.

(vedere le cose in questo modo: Si paga tre centesimi per ogni voce salire o scendere dalla pila saranno utilizzati Due di loro durante la prossima copia che si verificherà.).

Link all'articolo di wikipedia che spiega più in dettaglio

Answer 2

Sicuramente non crescere e ridursi 4 byte alla volta. Il tuo mucchio diventerà molto frammentato, e si spenderà troppo tempo in l'allocatore. Anche su un'architettura di memoria limitata, non si vuole essere memoria micro-gestione del genere.

Scegliere una "dimensione di pagina", e l'incremento in misura corrispondente. E 'comune a raccomandare raddoppiando le dimensioni, ma non sono sicuro perché. Probabilmente sapete di più su come lo stack sarà utilizzato per capire il modo migliore per incrementare le dimensioni.

Answer 3

Quasi ogni struttura di dimensione variabile implementata in biblioteche popolari fare un po 'piccole ottimizzazioni per evitare reallocing tutto il tempo. Ricordate che di solito ha per copiare i dati per renderlo più grande.

Di solito cresce di grandi quantitá. una strategia comune è quello doppio formato fino se raggiunge un certo limite, e quindi crescono da una quantità fissa là. e per il restringimento, non ti preoccupare per ridimensionare fino a quando è sprecare più della metà le dimensioni.

OTOH, alcuni realloc () implementazioni già farlo per voi dietro le tende. ahimè, dubito tua 'linguaggio oscuro' lo fa ...