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

0

АТД «очередь с приоритетами» применяет две стандартные модели проектирования — сочетания и компараторы, которые и приводятся в этом подразделе.

Композиционная модель проектирования

Одной из этих моделей является композиционная модель (composition pattern). В ней объект е определяется как сочетание (композиция) других элементов. Эта модель используется в АТД «очередь с приоритетами» при необходимости представить объекты, хранимые в приоритетной очереди, в виде пары. Пара (к,е) представляет собой простейшее сочетание, состоящее из двух объектов. Для реализации данной концепции определим класс, который помещает два объекта в две свои переменные экземпляров и предоставляет метод доступа и обновления этих переменных. Во фрагменте кода 7.2 приведен пример реализации на Java парного шаблона применительно к парам «ключ-элемент», используемым в очереди с приоритетами. К другим видам сочетаний можнр отнести хроцкр, состоящие из, jpex объектов, четверки и, произвольные сочетания, способные хранить любое количество объектрв (например, с домощью последовательности).

public class Item {

private Object key, elem; protected Item (Object k, Object e) { key == k; elem = e;

}

public Object key() { return key; } public Object element() { return elem; } public void setKey(Object k) { key = k; } public void setElement(Object e) { elem = e; }

}

Фрагмент кода 7.2. Класс для пар «ключ-элемент», хранящихся в очереди с приоритетами

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

Компараторная модель

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

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

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

Пример 7.3. Имея ключи 4 и 11, можно утверждать, что первый ключ меньше второго (4 < 11) , если ключами являются целочисленные объекты (дЛя сравнения традиционный образом), но первый клк)^ больше второго, то есть «11» < «4», если к^ючи являются строковыми объектами (для лексикографического сравнения).

Пример 7.4. Геометрический алгоритм может сравнивать точки р и q на плоскости по х-координатам (то есть р< q, если х(р) < x(q)) при сортировке слева направо, в то же время другой алгоритм может сравнивать эти точки по ^-координатам (то есть р < q, если у(р) < y(q)) при сортировке снизу вверх. В принципе никаких противоречий с предложенной выше концепцией не возникает, если точки сравниваются по х или ^-координатам. Точно так же здесь может применяться, например, возможность сравнения точек по расстоянию от начала коррдинат.

Следовательно, для достижения универсальности и многофункциональности очереди с приоритетами не следует полагаться на то, что сами ключи предоставят, критерий для сравнения. Вместо этого для сравнения воспользуемся специальными компараторными (сравнивающими) объектами, не являющимися частями ключей. Допустим, очередь Р в момент создания получает некоторый компаратор, а также имеёт возможность заменять не отвечающий новым условиям компаратор на другой. Компаратор обеспечивает сравнение ключей в Р. Таким образом, программист может написать универсальную реализацию очереди с приоритетами, которая будет корректно работать в контексте различных сред. Формально компараторный объект предоставляет следующие методы, каждый из которых сравнивает два ключа (или сообщает об ошибке, если ключи нельзя сравнивать). Это следующие методы:

isLessThan(tf,Z>): возвращает true при а, меньшем Ь.

Input: пара объектов; Output: boolean.

isLessThanOrEqualTo(tf,Z>): возвращает true при а, меньшем или равном b.

Input: пара объектов; Output: boolean.

isEqualTo(tf,Z>): возвращает true при равенстве а н b.

Input: пара объектов; Output: boolean.

isGreaterThan(tf,Z>): возвращает true при а, большем Ь.

Input: пара объектов; Output: boolean.

isGreaterThanOrEqualTo(tf,Z>): возвращает true при а, большем или равном Ь.

Input: пара объектов; Output: boolean.

isComparable(tf): возвращает true при возможности сравнения.

Input: объект; Output: boolean.

public elass Lexicographic implements Comparator { int xa, ya, xb, yb;

// Компаратор для сравнения точек плоскости в стандартном // лексикографическом порядке.

// С учетом того, что Point2D содержит методы getX() и getY(), // возвращающие его координаты, private void getXY(Object a, Object b) { if (a == null II b == null)

throw new InvalidElementExceptionfNull Argument"); try {

xa = ((Point2D) a).getX(); ya = ((Point2D) a).getY(); xb = ((Point2D) b).getX(); yb = ((Point2D) b).getY();

}

catch (ClassCastException e)

{ throw new lnvalidElementException("Argument not a Point2D"); }

}

public boolean isLessThan(Object a, Object b) { getXY(a, b); if (xa -= xb)

return (ya < yb); else

return (xa < xb);

}

public boolean isLessThanOrEqualTo(Object a, Object b) { getXY(a, b); if (xa == xb)

return (ya <= yb); else

return (xa <= xb);

}

public boolean isEqualTo(Object a, Object b) { getXY(a, b);

return (xa == xb) && (ya == yb);

}

// конструктор и несколько методов опущены…

public boolean isComparable(Object a) { if (a == null)

return false; else {

try { Point2D p = (Point2D) a; }

catch (ClassGastException e) { return false; }

return true;

}

}

}

Фрагмент кода 7.3. Часть компаратора для точек плоскости

Методы АТД «компаратор» имеют допустимо длинные названия, используемые для удобства восприятия. Интересно, что пакет java.util содержит интерфейс модели проектирования «компаратор» (JDK v. 1.2 и далее), использующий достаточно изящный механизм сравнения, основанный на одном-единственном методе:

Сотраге(я,/>): возвращает целое число /, такое, что / < 0 при а < />; / = О при a-b\i> 0 при а > Ь. Input: объекты; Output: целое число.

Реализация при помощи несортированной последовательности

В качестве первого варианта реализации очереди Р рассмотрим хранение элементов и их ключей в несортированной последовательности S. Из соображений универсальности будем считать, что S — это обычная последовательность, реализованная либо с помощью массива, либо двусвязного списка (выбор типа реализации, как показано ниже, не сказывается на производительности). Таким образом, элементы в Sявляются парами (к,е), где е — элемент из Р, а к — его ключ. Простейшим способом реализации метода insertltem(/:,e) является добавление парного объекта р = (к,е) в конец последовательности S путем вызова метода insertLast(p). Выполнение метода insertltem занимает 0(1) времени независимо от способа реализации последовательности — с помощью массива или связного списка (раздел 5.3). Этот вариант означает, что S не будет сортироваться, поскольку каждый следующий элемент будет просто добавляться в конец списка без учета порядка ключей. Как следствие, для выполнения операций minElement, minKey или removeMin над очередью Р придется просмотреть все элементы последовательности S, чтобы найти в ней элемент р = (к,е) с наименьшим ключом к.

Таким образом, независимо от способа реализации последовательности все методы поиска для очереди Р занимают 0(п) времени, где п — количество элементов в Р. Более того, даже в самом благоприятном случае эти методы будут занимать 0(п) времени, поскольку каждому из них необходимо время на прохождение всей последовательности для поиска минимального элемента. Следовательно, при использовании несортированной последовательности для реализации очереди с приоритетами получим постоянное время операции ввода элемента, но операция removeMin будет выполняться уже в линейном времени.

Реализация при помощи сортированной последовательности

Другим видом реализации очереди с приоритетами Р с помощью последовательности является последовательность S, в которой элементы сортируются по ключам. Выполнить методы minElement и minKey в таком случае можно простым обращением к первому элементу последовательности с помощью используемого в S метода first. Аналогично метод removeMin очереди Р может быть реализован, как S.remove(5.first()). Поскольку S реализована с помощью связного списка или массива, поддерживающих удаление первого элемента за постоянный промежуток времени (см. раздел 5.3), поиск и удаление из Р элемента с наименьшим значением занимает 0(1) времени. Таким образом, использование сортированной последовательности позволяет применять простой и быстрый способ реализации методов доступа к очереди с приоритетами и удаления элементов.

Однако за удобство приходится платить, так как в этом случае метод insertltem очереди Ртребует сканирования всей последовательности ?для нахождения соответствующей позиции для ввода нового элемента и его ключа. Следовательно, выполнение метода insertltem очереди Р требует 0(п) времени, где п — количество элементов в Р. В итоге при использовании сортированной последовательности для реализации приоритетной очереди ввод элементов выполняется в линейном времени, а поиск и удаление элементов с минимальным значением занимает постоянное время. Фрагмент кода 7.4 иллюстрирует реализацию приоритетной очереди с помощью сортированной последовательности (и ключевых частей из фрагмента кода 7.2).

public class SortedSequencePriorityQueue implements PriorityQueue { protected Sequence S = new NodeSequence(); protected Comparator comp;

protected Object key (Position pos) { return ((Item) pos.element())key();

}

protected Object elem (Position pos) { return ((Item) pos.element()).element();

}

protected Object elem (Object kep) { return ((Item) kep).element();

}

public SortedSequencePriorityQueue (Comparator c) { comp = c; } public int size () {return S.size(); } public boolean isEmpty () { return S.isEmpty(); } public void insertltem (Object k, Object e) throws InvalidKeyException { if (!comp.isComparable(k))

throw new lnvalidKeyException("The key is not valid");

11 Зак 2456

else If (S.isEmptyO)

S.insertFirst(new ltem(k, e)); else If (comp.isGreaterThan(k, key(S.last())))

S.insertAfter(S.last(),new ltem(k,e)); else {

Position curr = S.first();

while (comp.isGreaterThan(k, key(curr)))

curr = S.after(curr); S.insertBefore(curr,new ltem(k,e));

}

}

public Object removeMin() throws PriorityQueueEmptyException { If (S.isEmptyO)

throw new EmptyContainerExceptionfThe priority queue is empty"); else

return elem(S.remove(S.first()));

}

Фрагмент цода 7.4. Фрагмент Java-icnacca PriorityQueue, реализующего очередь с приоритетами с помощью сортированной последовательности. Интерфейс PriorityQueue определяет основные методы АТД «очередь с приоритетами»

Сравнение двух вариантов реализации

В табл. 7.1 приводятся результаты сравнения времени выполнения методов очереди с приоритетами, реализованной с помощью сортированной и несортированной последовательностей. При использовании последовательности можно обнаружить интересную тенденцию. Несортированная последовательность обеспечивает быстрый ввод элементов, но долгие запросы и удаление элементов, а’ сортированная последовательность — быстрый запрос и удаление элементов, но медленный ввод.

Метод

Несортированная

Сортированная

последовател ьн ость

поеледовател ьн ость

size, isEmpty

0(1)

0(1)

insertltem

0(1)

0(п)

minElement, minKey, removeMin

0(л)

0(1)

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

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

По теме:

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