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

0

В табл. 5.4 представлены результаты сравнения времени выполнения реализации универсального АТД «последовательность» с помощью массива (цикличный вариант) и двусвязного списка.

Операции

Массив

Список

size, isEmpty

0(1)

0(1)

atRank, rankOf, elemAtRank

0(1)

0(П)

first, last, before, after

0(1)

0(1)

replaceElement, swapElements

0(1)

0(1)

replaceAtRank

0(1)

0(n)

insertAtRank, removeAtRank

0(П)

0(n)

insertFirst, insertLast

0(1)

0(1)

insertAfter, insertBefore

0(«)

0(1)

remove

0(ri)

0(1)

Таблица 5.4. Сравнение времени реализации АТД «последовательность» с помощью массива (круговой вариант) и двусвязного списка. При этом п обозначает число элементов последовательности. Занимаемое пространство при реализации на основе двусвязного списка есть 0(п), а при реализации на основе массива — 0(N), где N— длина массива

В результате анализа таблицы можно сделать вывод, что для выполнения методов, использующих разряды (atRank, rankOf и elemAtRank), предпочтительной является реализация на основе массива, а время выполнения/ всех остальных методов доступа одинаково для реализации операций обновления, основанных на использовании позиций (insertAfter, insertBefore и remove), эффективнее с помощью двусвязного списка, чем с помощью массива. Однако время выполнения методов обновления,

использующих разряды (insertAtRank и removeAtRank), в худших условиях одинаково для обеих реализаций, хотя и по различным причинам. Эффективность выполнения операций insertFirst и insertLast одинакова в обоих случаях.

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

Каждая из реализаций имеет свои преимущества и недостатки. Выбор того или иного способа обусловлен конкретными требованиями приложения и зависит от выполняемых операций и свободной памяти. Поскольку структура АТД «последовательность» не зависит от конкретных условий реализации, применяется любой способ реализации, который более соответствует используемому приложению и с минимальными изменениями в программе.

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

По теме:

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