Typickou operací nad množinou je testování, zda obsahuje konkrétní prvek. Tato operace se jednak využívá při vkládání prvku do množiny, jednak bude často volána uživatelem. Její časová složitost je tedy kritická a měli bychom najít lepší řešení, než lineární vyhledávání, které jsme použili v implementaci třídy ArrayList. Možným vylepšením je udržovat seznam hodnot seřazený a pro testování přítomnosti prvku v tomto seznamu použít binárního vyhledávání.
Binární vyhledávání spočívá v rozdělení množiny prvků, kterou prohledáváme, na dvě části, a to takovým způsobem, že všechny hodnoty v levé části budou menší než hodnoty v pravé části. Podle hodnoty hledaného klíče pak rozhodneme, zda budeme dále hledat v levé nebo pravé části, a celý postup opakujeme dělením vybrané části až do okamžiku, kdy získáme hledaný prvek nebo prázdnou množinu klíčů. Je to vlastně zobecněná metoda půlení intervalu, kterou jistě znáte z numerické matematiky.
Složitost takového vyhledávání je logaritmická v případě, že dělení bude probíhat vždy na dvě stejně velké části. To znamená, že s každým zdvojnásobením počtu prohledávaných položek se čas nutný pro vyhledání prvku zvětší v nejhorším případě o konstantu.
Zajistíme-li uspořádání seznamu hodnot podle velikosti, můžeme využít variantu binárního vyhledávání nad seřazeným seznamem. To spočívá v neustálém půlení intervalu indexů, přičemž jako počáteční interval vezmeme rozsah všech indexů v seznamu. V každém kroku vybereme prostřední prvek a podle hodnoty jeho klíče zjistíme, zda se hledaná hodnota nachází v levé nebo pravé polovině. S vybranou polovinou indexů pak postup opakujeme, až se dostaneme k hledanému prvku nebo až se velikost intervalu zmenší na nulu a zjistíme, že prvek v seznamu není. V tomto případě máme vždy zajištěno, že dělení proběhne na dvě poloviny, takže časová složitost binárního vyhledávání nad seřazeným seznamem je vždy logaritmická. Jinou možností, jak realizovat binární vyhledávání, je použití seřazeného vyhledávacího stromu, kde tato podmínka již není automaticky splněna, ale k tomu se dostaneme později.
Na rozdíl od lineárního vyhledávání, kde jsme vystačili s metodou equals() pro porovnání prvků na rovnost, zde budeme ale potřebovat i uspořádání prvků a k tomu jazyk Java žádnou standardní metodu objektu nedefinuje. Napadá vás nějaké řešení?
Využijeme podobně jako v případě rozhraní Command triku se zapouzdřením operace do rozhraní a předání objektu, který toto rozhraní implementuje. Porovnatelnost objektů tedy můžeme zavést tak, že vytvoříme rozhraní Comparable obsahující metodu compareTo() pro porovnání a budeme vyžadovat, aby porovnávané objekty toto rozhraní implementovaly:
interface Comparable {
int compareTo(Object o);
}
Volání o1.compareTo(o2) vrátí zápornou hodnotu, pokud je o1 menší než o2, nulovou hodnotu, pokud se objekty rovnají, a kladnou hodnotu, je-li o1 větší než o2. Metoda compareTo() by měla být konzistentní s metodou equals() v tom smyslu, že compareTo() vrátí nulu právě tehdy, jestliže equals() vrátí true.
V následujícím příkladu si implementaci binárního vyhledávání s využitím rozhraní Comparable ukážeme prakticky.
 | Příklad 3.11. |
Implementujte rozhraní Set pomocí uspořádaného seznamu s binárním vyhledáváním. Porovnání prvků realizujte s využitím rozhraní Comparable. Vlastní binární vyhledávání je obsaženo v pomocné metodě search(), která vyhledá prvek v seznamu a vrátí jeho index. V případě, že se prvek nenajde, vrátí záporné číslo (-1-pos), umožňující získat pozici, na kterou by se hledaná hodnota měla vložit. Volba uvedeného výrazu vychází z toho, že chceme zápornou návratovou hodnotou sdělit vlastně dvě informace současně - jednak to, že jsme prvek nenašli, jednak jeho pozici. Pouhé vrácení záporné pozice by však pro index 0 nefungovalo. Další operace vkládání, rušení a vyhledání prvku pak nejprve metodou search() vyhledají příslušný prvek a vrácenou hodnotu využijí k provedení konkrétní akce.
class OrderedArraySet implements Set
{
public OrderedArraySet(int capacity) {
list = new ArrayList(capacity);
}
private int search(Object elem)
{
Comparable key = (Comparable)elem;
int min = 0;
int max = list.size() - 1;
while( min <= max ) {
int i = (min + max) / 2;
Object obj = list.get(i);
int compare = key.compareTo(obj);
if( compare < 0 )
max = i - 1;
else if( compare > 0 )
min = i + 1;
else
return i;
}
return -1-min;
}
public void add(Object elem)
{
int pos = search(elem);
if( pos < 0 )
list.add(-pos-1, elem);
}
public boolean remove(Object elem)
{
int pos = search(elem);
if( pos < 0 ) return false;
list.remove(pos);
return true;
}
public boolean contains(Object elem)
{
return search(elem) >= 0;
}
public int size()
{
return list.size();
}
public Iterator iterator()
{
return list.iterator();
}
protected ArrayList list;
}
|
Někdy se ovšem můžeme dostat do situace, kdy pracujeme s již definovanými třídami a nemůžeme si dovolit jejich definice rozšířit tak, aby přímo implementovaly rozhraní Comparable. V tom případě máme jinou možnost - můžeme definovat samostatnou třídu implementující následující rozhraní Comparator a její instanci použít pro porovnávání prvků množiny:
interface Comparator {
int compare(Object o1, Object o2);
}
Metoda compare() tohoto rozhraní zajistí porovnání dvou objektů stejně jako metoda compareTo() rozhraní Comparable; vrátí tedy zápornou, nulovou nebo kladnou hodnotu podle toho, zda je objekt o1 menší, roven nebo větší než o2.
Abychom pro tento přístup rozšířili implementaci třídy OrderedArraySet, stačí doplnit další konstruktor, jehož dalším parametrem bude Comparator, a upravit tělo metody search() tak, aby komparátor použila:
class OrderedArraySet implements Set {
. . .
public OrderedArraySet(int capacity, Comparator comparator) {
list = new ArrayList(capacity);
this.comparator = comparator;
}
private int search(Object elem)
{
int min = 0;
int max = list.size() - 1;
while( min <= max ) {
int i = (min + max) / 2;
Object obj = list.get(i);
int compare;
if( comparator == null )
compare = ((Comparable)elem).compareTo(obj);
else
compare = comparator.compare(elem, obj);
if( compare < 0 )
max = i - 1;
else if( compare > 0 )
min = i + 1;
else
return i;
}
return -1-min;
}
. . .
protected Comparator comparator;
}
Poznamenejme, že nastavení instanční proměnné comparator na hodnotu null je zajištěno definicí jazyka Java (na rozdíl od lokálních proměnných, které musíme vždy inicializovat).
| Příklad 3.12. |
Vytvořte objekt implementující rozhraní Comparable pro porovnávání řetězců bez ohledu na velká a malá písmena. Budeme předpokládat, že tento objekt použijeme pouze na porovnávání objektů typu String. Pokud by tomu tak nebylo, museli bychom nejprve pomocí operátoru instanceof zjistit, zda jsou oba objekty instancemi třídy String. Proměnnou comparator naplníme referencí na nově vytvořený objekt, jehož třída je anonymní (není pojmenovaná).
Comparator comparator = new Comparator() {
public int compare(Object o1, Object o2) {
String s1 = (String)o1;
String s2 = (String)o2;
return s1.compareToIgnoreCase(s2);
}
};
|