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

0

Простейшим способом реализации множества является хранение его элементов в упорядоченной последовательности. Предпочтение такой реализации заложено в интерфейсе java.util.SortedSet, который расширяет возможности java.util.Set и предполагает упорядоченность элементов множества. Даже в случае отсутствия компаратора можно рпределить некоторые отношения упорядоченности элементов множества. В принципе способ упорядочить элементы всегда имеется. Например, можно воспользоваться адресами объектов в памяти. Поэтому рассмотрим реализацию АТД «множество» с помощью упорядоченной последовательности (другие реализации оставлены для упражнений). Каждую из трех основных операций множества реализуем с помощью унифицированной версии алгоритма слияния, который в качестве исходного данного принимает две отсортированные последовательности, представляющие исходные множества, и создает последовательность, представляющую получаемое в результате множество, будь то объединение, пересечение или разность исходных множеств. Упорядочение для обоих множеств может основываться на любом правиле (например, на принципе полного упорядочения) с условием, что одно и то же правило применено к обоим множествам, с которыми предполагается работа. Описание унифицированного алгоритма слияния приведено во фрагменте кода 10.3.

Алгоритм generic Merged В) :

Input: множества, представленные отсортированными последовательностями А и В.

Output: множество, представленное отсортированной последовательностью С.

{А и В не уничтожаются} let A’ be a copy of А И копирование А в А’ let В’ be a copy of В II копирование В в В’ while A’ and В’ are not empty do // пока А’ и Б’ не пусты a <- A.first() b <- B’.firstQ

if a < b then

alsl_ess(a,C) ,4′.removeFirst() else if a = b then

bothAreEqual(a, b, C) ,4′.removeFirst() B’. removeFirst() else

blsLess (b,C) B’.removeFirst() while A’ is not empty do // пока А’ не пусто a <- 4′.first() alsl_ess(a,C) /4′.removeFirst() while B’ is not empty do // пока В’ не пусто b <- В’ .first() blsLess (Ь,С) B’.removeFirst()

Фрагмент кода 10.3. Унифицированный алгоритм слияния, использующий методы alsLess, bothAreEqual и blsLess, определяющие состояние С. Этот алгоритм не изменяет исходные последовательности

Унифицированный метод слияния интерактивно изучает и сравнивает текущие элементы аи b последовательностей А и В соответственно, определяя их соотношение (а < Ь, а = b или а > Ь). После этого в зависимости от результата сравнения и выполняемой операции (объединение, пересечение или разность) определяется необходимость копирования одного из элементов в конец создаваемой последовательности С.

Например, в операции объединения меньший элемент копируется в создаваемую последовательность, при равенстве — любой из них (допустим, а). Такой подход гарантирует, что копируется элемент, который присутствует только в одном из множеств, чтобы избежать дублирования. Вид копирования будет определяться вспомогательными методами alsLess, bothAreEqual и blsLess с учетом требуемой операции.

Слияние как модель проектирования

Унифицированный алгоритм слияния представляет собой модель проектирования шаблонных методов (template method pattern) (см. п. 6.3.5). Модель проектирования шаблонных методов — это модель проектирования программ, описывающая универсальный механизм выполнения вычислений, который можно настраивать переопределением некоторых шагов. В данном случае описываем метод объединения двух последовательностей в одну. Для управления процессом объединения достаточно определить поведение трех абстрактных методов.

Во фрагменте кода 10.4 показана Java-реализация абстрактного класса Merger. Для конкретной реализации процесса слияния требуется создать класс-наследник класса Merger и переопределить три вспомогательных метода alsLess, bothAreEqual и blsLess. Из фрагмента кода 10.5 видно, насколько просто можно описать каждую из операций объединения, пересечения и разности применением этих методов. После переопределения вспомогательных методов шаблонный метод merge выполняет следующие действия:

•                    в классе UnionMerger метод merge копирует каждый элемент из А и В в С, но не дублирует ни один из них;

•                    в классе IntersectMerger метод merge копирует все элементы изАиВ в С, отбрасывая элементы, присутствующие в одном множестве, но отсутствующие в другом;

•                    в классе SubtractMerger метод merge копирует в С каждый элемент, присутствующий в А, но отсутствующий в В.

Также можно рассмотреть расширение АТД «множество» с помощью дополнительных методов insert и remove для ввода и удаления элементов множества. Поскольку применяется сортированная последовательность, эти методы можно реализовать простым сканированием последовательности, являющейся множеством, за О(п) времени, как это предлагается для решения в упражнении М-10.7.

//** Унифицированное слияние сортированных последовательностей. 7 public abstract class Merger {

private Object a, b; // текущие элементы в А и В private Objectlterator iterA, iterB; // итераторы А и В /** Унифицированный шаблонный метод слияния 7

public void merge(Sequence A, Sequence В, Comparator comp, Sequence С) {

iterA = A.elements(); iterB = B.elements();

boolean aExists = advanceA(); // Boolean проверка наличия текущего a boolean bExists = advanceB(); // Boolean проверка наличия текущего b while (aExists && bExists) { // основной цикл для слияния а и b if (comp.isLessThan(a, b)) {

alsl_ess(a, С); aExists = advanceA();

}

else if (comp.isEqualTo(a, b)) { bothAreEqual(a, b, C);

aExists = advanceA(); bExists = advanceB(); } else {

blsLess(b, C); bExists = advanceB();

}

}

while (aExists) { alsl_ess(a, C); aExists = advanceA(); } while (bExists) { blsl_ess(b, C); bExists == advanceB(); }

// вспомогательные методы, перенастраиваемые подклассами protected void alsLess(Object a, Sequence C) { } protected void bothAreEqual(Object a, Object b, Sequence C) { } protected void blsLess(Object b, Sequence C) { } // вспомогательные методы private boolean advanceA() { if (iterA.hasNext()) { a = iterA.nextObject(); return true;

}

return false;

}

private boolean advanceB() { if (iterB.hasNext()) { b = iterB.nextObject();

return true;

} •

return false;

}

}

Фрагмент кода 10.4. Класс Merger, реализующий унифицированный алгоритм слияния

//** Класс, переопределяющий унифицированную модель слияния // для объединения двух множеств */ public class UnionMerger extends Merger {

protected void alsLess(Object a, Sequence C) { C.insertLast(a); // ввести a

}

protected void bothAreEqual(Object a, Object b, Sequence C) { C.insertLast(a); // ввести а (но не его дубликат b)

}

protected void blsLess(Object b, Sequence C) { C.insertLast(b); // ввести b

}

}

//** Класс, переопределяющий унифицированную модель слияния

// для пересечения двух множеств */

public class IntersectMerger extends Merger {

protected void alsLess(Object a, Sequence C) { } protected void bothAreEqual(Object a, Object b, Sequence C) { C.insertLast(a); // ввести а (но не его дубликат b)

}

protected void blsLess(Object b, Sequence C) { }

//** Класс, переопределяющий унифицированную модель слияния // для разности двух множеств */ public class SubtractMerger extends Merger { protected void alsLess(Object a, Sequence C) { C.insertLast(a); // ввести a

}

protected void bothAreEqual(Object a. Object b. Sequence C) { } protected void blsLess(Object b, Sequence C) { }

}

Фрагмент кода 10.5. Классы, расширяющие класс Merger с помощью вспомогательных методов объединения, пересечения и разности множеств

Производительность алгоритма слияния

Теперь проанализируем время выполнения унифицированного алгоритма слияния. При очередной итерации одного из циклов из А, В или из обоих множеств одновременно удаляется один элемент. Исходя из того, что сравнение занимает 0(1) времени и каждый вызов вспомогательного метода также требует 0(1) времени, общее время выполнения genericMerge(^,5) составит 0(па + пв), где па — размер А,апд— размер В. Следовательно, слияние занимает время, пропорциональное количеству участвующих в процессе элементов. А значит, имеет место следующее утверждение.

Утверждение 10.4. АТД «множество» может быть реализован упорядоченной последовательностью и унифицированной схемой слияния, поддерживающей операции union, intersect и subtract за 0(п) времени, где п обозначает сумму размеров участвующих в процессе множеств.

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

По теме:

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