Главная » Java, Структуры данных и алгоритмы » Реализация на основе расширяемого массива

0

Основной недостаток реализации вектора на основе простого массива, рассмотренной в п. 5.1.2, состоит в необходимости предварительного указания размера массива /V, то есть максимального числа элементов вектора. Если же действительное число элементов значительно меньше N, то при такой реализации бесполезно занимается место в памяти. Хуже того, если п окажется больше значения /V, то реализация приведет к сбою программы. К счастью, существует простой способ разрешения этой проблемы.

Предположим, имеются средства увеличения размера массива А, содержащего элементы вектора S. Безусловно, в Java (и других языках программирования) в действительности невозможно увеличить размер массива, его длина ограничена заданным значением TV, как отмечалось ранее. Вместо этого при возникновении переполнения, то есть при п = N, и вызове метода insertAtRank выполняются следующие операции:

1)                     создается новый массив В длиной 2N\

2)                      копируется A[i] в /?[/], где / = 0, …, N- 1;

3)                      присваивается А = В, то есть используется В как массив, содержащий S.

Данная стратегия замещения массивов известна как расширяемый массив, так как она как бы продолжает исходный массив для размещения

Рис. 5.2. Изображение трех этапов «увеличения» расширяемого массива: (а) создание нового массива В\ (Ь) копирование элементов из А в В; (с) переадресация ссылки А к новому массиву. На рисунке не показана последующая утилизация старого массива «сборщиком мусора»

Во фрагменте кода 5.2 представлена реализация АТД «вектор» с помощью расширяемого массива.

public class ArrayVecta {

private Object[ ] a;                                   // массив, содержащий элементы вектора

private int capacity =16; // длина массива a private int size = 0; // число элементов вектора //конструктор

public ArrayVeotor() { a = new Object[capacity]; } // время 0(1) // аксессорные методы

public Object elemAtRank(int r) { return a[r]; }                                         // время 0(1)

public int size() { return size; }

public boolean isEmpty() { return size() = = 0; }                                      // время 0(1)

// методы модификации ,

public Object replaceAtRank(int r, Object e) {                                            // время 0(1)

Object temp = a[r]; a[r] = e; return temp;

public Object removeAtRank(int r) {                                        // время 0(1)

Object temp = a[r];

for (int i=r; i<size-1; i++)                                          // перемещает элементы назад

a[i],= a[i+1];

size———————- ;

return, temp;

}

public void insertAtRank(int r, Object e) {                                           // время 0(1)

большего числа элементов (см. рис. 5.2) и напоминает краба-отшельника, который перебирается в большую раковину после того, как вырастет из старой.

if (size =- capacity) { // переполнение capacity *= 2;

Object[ ] b = new Object[capacity]; for (int i—0; ksize; i++) b[i] = a[i];

a = b; }

for (int i=size-1; i>=r; i—) // перемещает элементы вперед

a[i+1] = a[i]; a[r] = e; size++;

}

}

Фрагмент кода 5.2. Класс ArrayVector, реализующий АТД «вектор» с помощью расширяемого массива. Для простоты не отмечены условия возникновения ошибки. Кроме того, код содержит только средства увеличения массива, и отсутствуют средства его уменьшения. Более подробно об этом при решении упражнений (3-5.1 и 3-5.3)

С точки зрения эффективности приведенная стратегия замещения массивов кажется относительно медленной, так как для замещения одного массива при необходимости вставки элемента требуется О(п) времени, что не очень приемлемо. Тем не менее следует отметить, что после замещения массива появляется возможность добавления п новых элементов перед необходимостью нового замещения. В результате можно показать, что время выполнения операций, производимых над изначально пустым вектором, в действительности не так уж велико. Для краткости назовем добавление последнего элемента вектора операцией «проталкивания». Далее, используя модель проектирования, называемую амортизацией, покажем, что последовательность подобных операций над вектором, реализованным на основе расширяемого массива, может быть достаточно эффективной.

Утверждение 5.1. Пусть S — вектор, реализованный на основе расширяемого массива А, как было описано выше. Общее время выполнения последовательности операций проталкивания п в массиве S при условии, что S изначально пустой, а А имеет размер N = I, есть О(п).

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

Предположим, что стоимость каждой операции проталкивания в S (с учетом времени на увеличение массива) равна одному кибер-доллару. Далее предположим, что для увеличения массива длиной к до размеров длиной 2к требуется к кибер-долларов, что является платой за время, потраченное на копирование элементов. Таким образом, каждая операция проталкивания, требующая увеличения массива, стоит три кибер-долла- ра. Оценим каждую операцию проталкивания, которая не приводит к переполнению, в два кибер-доллара. При этом учтем два кибер-доллара, сэкономленных на добавлении элемента, не приводившего к увеличению массива. Переполнение происходит в том случае, когда вектор S содержит 2′ элементов, где / > 0 на некоторое целое число, и длина массива, используемого для представления вектора S, также есть 2′. Таким образом, для увеличения массива вдвое потребуется 2′ кибер-долларов. К счастью, эти кибер-доллары можно получить из элементов, записанных в ячейки 2”1 до 2’— 1 (см. рис. 5.3). Обратите внимание, что предыдущий случай переполнения возник, когда число элементов впервые превысило 2’~1

Рис. 5.3. Демонстрация последовательности операций проталкивания над вектором: (а) массив из 8 ячеек заполнен — в ячейках от 4 до 7 хранятся по два кибер-доллара; (Ь) операция проталкивания приводит к переполнению и увеличению длины вдвое. При копировании восьми старых элементов в новый массив используются кибер-доллары, уже сохраненные в таблице; добавление нового элемента оплачивается долларом, сохраненным при выполнении операции проталкивания, а доход в два кибер-доллара хранится в ячейке 8

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

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии