La meilleure façon de mettre en œuvre un type de pile dynamique? ou suis-je maltraitais realloc?

Question

J'utilise un langage obscur qui n'a pas un type de pile natif, donc j'ai mis mon propre. Maintenant, la lecture sur le net que j'ai trouvé quelques approches différentes pour le faire.

Ceci est mon implémentation (pseudo-code)

//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;
}

Maintenant, certaines personnes disent que l'utilisation d'un realloc () pour redimensionner la pile après popping une valeur est mauvais pour la performance donc j'ai quelques questions:

1. Est-il préférable de pousser juste la pile en utilisant malloc gratuitement puis à la fin du programme?
2. Pour redimensionner la pile (push) est-il préférable d'augmenter de 4 octets ou plus?
3. Est-ce la meilleure façon d'augmenter la pile en doublant la mémoire allouée quand il est rempli?
4. Que pensez-vous du code ci-dessus?

Answer 1

La technique classique consiste à accroître seulement la taille d'un facteur de 2, et à le rétrécir uniquement lorsque l'utilisation efficace de la mémoire est inférieure à trimestre.

De cette façon, vous pouvez être sûr que vous ne jamais utiliser plus de O (la mémoire dont vous avez besoin), et vous pouvez également prouver que la pile est amorti constante de temps.

(regardez cette façon: Vous payez trois cents pour chaque élément entrant ou sortant de la pile Deux d'entre eux seront utilisés lors de la prochaine copie qui se produira.).

Lien vers wikipedia article expliquant plus en détail

Answer 2

Sans aucun doute ne se développent pas et rétrécir 4 octets à la fois. Votre tas deviendra très fragmenté, et vous passer trop de temps dans l'allocateur. Même sur une architecture mémoire limitée, vous ne voulez pas être la mémoire microgestion comme ça.

Choisissez une « taille de la page », et augmentation de ce montant. Il est courant de recommander de doubler la taille, mais je ne sais pas pourquoi. Vous savez probablement plus sur la façon dont la pile sera utilisée pour comprendre la meilleure façon d'incrémenter la taille.

Answer 3

Presque toutes les structures de taille variable mis en œuvre dans les bibliothèques populaires font quelques petites Optimisations pour éviter reallocing tout le temps. Rappelez-vous qu'il a généralement de copier les données pour les rendre plus.

En général, il croît de plus grandes quantités. une stratégie commune est de taille à double jusqu'à ce que si atteint une certaine limite, puis augmenter d'un montant fixe là-bas. et pour la réduction, ne vous inquiétez pas pour redimensionner jusqu'à ce qu'il gaspille plus de la moitié de la taille.

OTOH, certains realloc () mises en œuvre font déjà pour vous derrière des rideaux. hélas, je doute votre « langue obscure » le fait ...