Изменение размера массивов

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

Как мы реализуем API? API говорит, что мы должны просто иметь возможность создавать стек, и он должен иметь возможность увеличиваться и уменьшаться до любого размера. Итак, как мы собираемся расти и сокращать массив?

Ну, первое, что вы можете подумать, это когда клиент помещает новый элемент в стек, увеличивать размер массива на 1, а когда он появляется, уменьшать размер массива на 1. Это легко закодировать, но не стоит, потому что это слишком дорого. Причина в том, что вам нужно создать новый массив, на один размер больше, и скопировать все элементы в этот новый массив.

Таким образом, для вставки первых N элементов потребуется пропорциональное время, если для стека размера N-1 потребуется время N, N-2, время N-1. Таким образом, первые N элементов будут принимать сумму первых N целых чисел, которые, как мы знаем, примерно равны N в квадрате. Квадратичное время для вставки N элементов в стек, такого рода производительность неприемлема для больших проблем, как мы видели, как мы увидим много раз.

Таким образом, задача состоит в том, чтобы сделать изменение размера, но каким-то образом гарантировать, чтобы это происходило нечасто. Хорошо известная техника для этого, называемая повторным удвоением, состоит в том, чтобы, когда массив заполнялся, создавать новый массив в два раза больше и копировать все элементы. Тогда мы не будем часто создавать новые массивы.

Итак, вот реализация этого.

public ResizingArrayStackOfStrings()
{ s = new String[1]; }
public void push(String item)
{
if (N == s.length) resize(2 * s.length);
s[N++] = item;
}
private void resize(int capacity)
{
String[] copy = new String[capacity];
for (int i = 0; i < N; i++)
copy[i] = s[i];

Мы начнем с массива размером 1. Если у нас есть полный стек, который мы знаем по тестированию N, который представляет собой количество элементов в стеке в зависимости от длины массива, то мы просто изменим размер массива на один из двух значений длины до вставки элемента. И как мы изменяем размеры на новую емкость? Мы создаем новый массив этой емкости и просто копируем наш текущий стек в первую половину, а затем возвращаем его.

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

Итак, идея и следствие этого, если вы вставите N элементов в массив, в стек с этим представлением массива, время будет пропорционально N, а не N в квадрате. И причина в том, что вы создаете новый массив только каждый раз, когда он удваивается.. Таким образом, в среднем это все равно, что добавить стоимость одного к каждой операции. Так что, если вы просто рассчитаете стоимость вставки первых N элементов, вместо суммы целых чисел от 1 до N вы получите сумму степеней от 2 до 1. И это даст общую стоимость около 3N.

Это называется амортизированным анализом, где мы рассматриваем общую стоимость, усредненную по всем операциям. И это прекрасный и полезный пример амортизированного анализа для повышения эффективности реализации стека. Теперь у нас есть, что касается поп, мы должны думать о том, как уменьшить массив.

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

Ну, это точно не работает из-за явления, называемого пробуксовкой. Если клиент выполняет чередование push-pop-push-pop, когда массив заполнен, то он будет удваиваться и разрезаться. Будет происходить создание новых массивов для каждой операции. Возьмите время, пропорциональное N для каждой операции, и, следовательно, квадратичное время для всего. Поэтому я не хочу этого делать.

Эффективное решение состоит в том, чтобы подождать, пока массив заполнится на четверть, прежде чем он у вас будет. И это очень легко реализовать. Мы можем просто проверить, заполнен ли массив на четверть, если он есть, мы изменим его размер до половины. И поэтому в этот момент он наполовину полон и может либо расти, добавляя вещи, либо уменьшаться, вычитая вещи. Но не будет другой операции по изменению размера массива, пока она не будет полностью заполнена или наполовину снова заполнена.

public String pop()
{
String item = s[--N];
s[N] = null;
if (N > 0 && N == s.length/4) resize(s.length/2);
return item;
}

Таким образом, во-первых, неизменным является то, что массив всегда заполнен между 25% и 100%. И, во-вторых, каждый раз, когда вы изменяете размер, вы уже заплатили за него в амортизированном смысле.

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



Таким образом, изменение размера массива происходит не так часто, но это очень эффективный способ реализации стекового API с массивом, в котором клиенту не нужно предоставлять максимальную емкость стека. Но, тем не менее, мы гарантируем, что объем используемой нами памяти всегда только кратен количеству элементов в стеке. Итак, анализ теперь говорит, что среднее время выполнения на одну операцию для любой последовательности операций, среднее время выполнения будет пропорционально константе.

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

Так как насчет использования памяти? Что ж, это анализ использования памяти для стеков, и на самом деле памяти меньше, чем для строк. Используемое количество находится в диапазоне от 8N до 32N, в зависимости от того, насколько массив заполнен, и просто от быстрого анализа объема пространства, занимаемого массивами в

Java. Итак, опять же, этот анализ предназначен только для самого стека, а не для строк, которыми владеет клиент. Итак, каковы компромиссы между использованием массива изменения размера и связанного списка? Это две разные реализации одного и того же API, и клиент может использовать их взаимозаменяемо. Какой из них лучше? Во многих ситуациях у нас будет несколько реализаций API, и в зависимости от свойств клиентской программы нам придется выбирать, какой из них лучше использовать. Так что для связанных списков каждая операция в худшем случае требует постоянного времени, это гарантия. Но мы должны использовать немного больше времени и места для работы со ссылками. Так что будет медленнее.

Реализация массива изменения размеров:

public class ResizingArrayStackOfStrings
{
private String[] s;
private int N = 0;
…
}

Мы хорошо амортизируем время, поэтому общее усреднение по всему процессу - это хорошо. У нас меньше места впустую и, возможно, более быстрая реализация каждой операции.

И поэтому для некоторых клиентов, возможно, это имеет значение. Возможно, вы не захотите использовать реализацию массива изменения размеров в тот момент, когда ваш самолет идет на посадку. Вы бы не хотели, чтобы вдруг не выполняли какую-то операцию быстро. Если вам нужен такой порядок, возможно, в интернет-коммутаторе, где пакеты проходят с большой скоростью, вы не захотите оказаться в ситуации, когда вам не хватает некоторых данных, потому что что-то вдруг стало медленным. Так что это компромисс, который может сделать клиент.

Если мне нужна эта гарантия, если я хочу быть уверенным, что каждая операция будет быстрой, я буду использовать связанный список. И если мне не нужна эта гарантия, если я просто забочусь об общем количестве времени, я, вероятно, буду использовать массив изменения размера, потому что общее количество будет намного меньше, потому что отдельные операции выполняются быстро. Так что даже с этими простыми структурами данных у нас есть действительно важные компромиссы, которые на самом деле имеют значение во многих практических ситуациях.