Лучший способ реализовать динамический тип стека?или я злоупотребляю Realloc?

Question

Я использую малоизвестный язык, у которого нет собственного типа стека, поэтому я реализовал свой собственный.Читая в сети, я нашел несколько разных подходов к этому.

Это моя реализация (псевдокод)

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

Теперь некоторые люди говорят, что использование вызова realloc() для изменения размера стека после извлечения значения плохо влияет на производительность, поэтому у меня есть несколько вопросов:

1. Лучше всего просто увеличить стек с помощью malloc, а затем освободить его в конце программы?
2. Для изменения размера стека (нажатия) лучше всего увеличить его на 4 байта или больше?
3. Лучше всего ли увеличивать стек, удвоив объем памяти, выделяемой при его заполнении?
4. Что вы думаете о приведенном выше коде?

Answer 1

Стандартный метод заключается в увеличении размера только в 2 раза и уменьшении его только тогда, когда эффективное использование памяти составляет менее четверти.

Таким образом, вы можете быть уверены, что никогда не используете больше O (нужной вам памяти), а также можете доказать, что стек амортизируется постоянно.

(Посмотрите на это с другой стороны:Вы платите три цента за каждый предмет, входящий в стопку или выходящий из нее.Два из них будут использованы при следующем копировании.)

Ссылка на статью в Википедии с более подробным объяснением

Answer 2

Определенно не увеличивайте и не сжимайте по 4 байта за раз.Ваша куча станет очень фрагментированной, и вы проведете слишком много времени в распределителе.Даже в архитектуре с ограниченной памятью вы не захотите заниматься микроуправлением памятью.

Выберите «размер страницы» и увеличьте его на эту величину.Обычно рекомендуют увеличить размер вдвое, но я не понимаю, почему это так.Вероятно, вы знаете больше о том, как будет использоваться стек, чтобы понять, как лучше всего увеличивать его размер.

Answer 3

Почти каждая структура переменного размера, реализованная в популярных библиотеках, содержит небольшие оптимизации, чтобы избежать постоянного перераспределения.Помните, что обычно приходится копировать данные, чтобы увеличить их.

Обычно он вырастает на большие суммы.Общая стратегия состоит в том, чтобы удваивать размер до тех пор, пока он не достигнет некоторого предела, а затем увеличиваться на фиксированную величину.а при уменьшении не беспокойтесь об изменении размера, пока он не потеряет более половины размера.

OTOH, некоторые реализации realloc() уже делают это за вас за кулисами.увы, я сомневаюсь, что ваш «непонятный язык» это делает...