Datové struktury a algoritmy v Javě, Část 1: Přehled

Programátoři Java používají datové struktury k ukládání a organizaci dat a k manipulaci s daty v těchto strukturách používáme algoritmy. Čím více porozumíte datovým strukturám a algoritmům a jak fungují společně, tím efektivnější budou vaše programy Java.

Tento výukový program zavádí krátkou sérii představující datové struktury a algoritmy. V části 1 se dozvíte, co je datová struktura a jak jsou datové struktury klasifikovány. Dozvíte se také, co je to algoritmus, jak jsou algoritmy zastoupeny a jak používat funkce složitosti času a prostoru k porovnání podobných algoritmů. Jakmile získáte tyto základní informace, budete připraveni se v části 2 dozvědět o vyhledávání a třídění pomocí jednorozměrných polí.

Co je datová struktura?

Datové struktury jsou založeny na abstraktních datových typech (ADT), které Wikipedia definuje takto:

[A] matematický model pro datové typy, kde je datový typ definován jeho chováním (sémantikou) z pohledu uživatele dat, zejména pokud jde o možné hodnoty, možné operace s daty tohoto typu a chování těchto operací.

ADT se nestará o paměťovou reprezentaci svých hodnot ani o to, jak jsou implementovány jeho operace. Je to jako rozhraní Java, což je datový typ, který je odpojen od jakékoli implementace. Naproti tomu a datová struktura je konkrétní implementace jednoho nebo více ADT, podobných tomu, jak třídy Java implementují rozhraní.

Mezi příklady ADT patří Zaměstnanec, Vozidlo, Pole a Seznam. Zvažte Seznam ADT (také známý jako Sequence ADT), který popisuje uspořádanou kolekci prvků, které sdílejí společný typ. Každý prvek v této kolekci má svou vlastní pozici a jsou povoleny duplicitní prvky. Mezi základní operace podporované List ADT patří:

Vytváření nového a prázdného seznamu
Přidání hodnoty na konec seznamu
Vložení hodnoty do seznamu
Odstranění hodnoty ze seznamu
Iteruje seznam
Zničení seznamu

Datové struktury, které mohou implementovat List ADT, zahrnují jednorozměrná pole s pevnou a dynamickou velikostí a jednotlivě propojené seznamy. (Budete seznámeni s poli v části 2 a propojenými seznamy v části 3.)

Klasifikace datových struktur

Existuje mnoho druhů datových struktur, od jednoduchých proměnných po pole nebo propojené seznamy objektů obsahující více polí. Všechny datové struktury lze klasifikovat jako primitivní nebo agregované a některé jsou klasifikovány jako kontejnery.

Primitivy vs. agregáty

Nejjednodušší druh datové struktury ukládá jednotlivé datové položky; například proměnná, která ukládá logickou hodnotu, nebo proměnná, která ukládá celé číslo. Takové datové struktury označuji jako primitiv.

Mnoho datových struktur dokáže ukládat více datových položek. Například pole může ukládat více datových položek do různých slotů a objekt může ukládat více datových položek prostřednictvím svých polí. Tyto datové struktury označuji jako agregáty.

Všechny datové struktury, na které se v této sérii podíváme, jsou agregáty.

Kontejnery

Cokoliv, ze kterého jsou datové položky ukládány a načítány, lze považovat za datovou strukturu. Mezi příklady patří datové struktury odvozené z dříve zmíněných ADT zaměstnanců, vozidel, polí a seznamu.

Mnoho datových struktur je navrženo k popisu různých entit. Instance Zaměstnanec třída jsou datové struktury, které existují například k popisu různých zaměstnanců. Naproti tomu některé datové struktury existují jako generické paměťové nádoby pro jiné datové struktury. Například pole může ukládat primitivní hodnoty nebo odkazy na objekty. Tuto druhou kategorii datových struktur označuji jako kontejnery.

Stejně jako agregace jsou všechny datové struktury, na které se v této sérii podíváme, kontejnery.

Datové struktury a algoritmy v kolekcích Java

Rámec kolekce Java podporuje mnoho druhů kontejnerových datových struktur a souvisejících algoritmů. Tato řada vám pomůže lépe porozumět tomuto rámci.

Návrhové vzory a datové struktury

Používání návrhových vzorů k seznámení studentů univerzity s datovými strukturami se stalo docela běžným. Dokument Brown University zkoumá několik návrhových vzorů, které jsou užitečné pro návrh vysoce kvalitních datových struktur. Papír mimo jiné demonstruje, že vzor adaptéru je užitečný pro návrh hromádek a front. Demonstrační kód je uveden v seznamu 1.

Výpis 1. Použití vzoru adaptéru pro zásobníky a fronty (DequeStack.java)

veřejná třída DequeStack implementuje Stack {Deque D; // obsahuje prvky zásobníku public DequeStack () {D = new MyDeque (); } @Override public int size () {return D.size (); } @Override public boolean isEmpty () {return D.isEmpty (); } @Override public void push (Object obj) {D.insertLast (obj); } @Override public Object top () hodí StackEmptyException {try {return D.lastElement (); } catch (DequeEmptyException err) {throw new StackEmptyException (); }} @Override public Object pop () hodí StackEmptyException {try {return D.removeLast (); } catch (DequeEmptyException err) {throw new StackEmptyException (); }}}

Výpis 1 obsahuje výňatky z Brown University DequeStack třída, která ukazuje vzor adaptéru. Všimněte si, že Zásobník a Deque jsou rozhraní, která popisují ADT Stack a Deque. MyDeque je třída, která implementuje Deque.

Přepisující metody rozhraní

Původní kód, na kterém je Výpis 1 založen, nepředložil zdrojový kód Zásobník, Deque, a MyDeque. Pro jasnost jsem uvedl @ Přepis anotace, které ukazují, že všechny DequeStackpřepíše nekonstruktivní metody Zásobník metody.

DequeStack přizpůsobuje se MyDeque aby to bylo možné implementovat Zásobník. Vše z DequeStackMetodou jsou jednorázová volání do Deque metody rozhraní. Existuje však malá vráska Deque výjimky jsou převedeny na Zásobník výjimky.

Co je to algoritmus?

Historicky používané jako nástroj pro matematické výpočty jsou algoritmy úzce spojeny s informatikou a zejména s datovými strukturami. An algoritmus je sled pokynů, které splní úkol v konečném časovém období. Vlastnosti algoritmu jsou následující:

Přijímá nula nebo více vstupů
Produkuje alespoň jeden výstup
Skládá se z jasných a jednoznačných pokynů
Ukončí po konečném počtu kroků
Je dost základní, aby to člověk mohl provádět pomocí tužky a papíru

Uvědomte si, že programy mohou mít sice algoritmický charakter, ale mnoho programů se nezastaví bez vnějšího zásahu.

Mnoho sekvencí kódu se kvalifikuje jako algoritmy. Jedním příkladem je sekvence kódu, která vytiskne zprávu. Více slavně, Euclidův algoritmus se používá k výpočtu největšího matematického společného dělitele. Lze dokonce učinit případ, že základní operace datové struktury (například uložit hodnotu do slotu pole) jsou algoritmy. V této sérii se z větší části zaměřím na algoritmy vyšší úrovně používané ke zpracování datových struktur, jako jsou algoritmy Binary Search a Matrix Multiplication.

Vývojové diagramy a pseudokód

Jak reprezentujete algoritmus? Psaní kódu před úplným pochopením jeho základního algoritmu může vést k chybám, tak co je lepší alternativou? Dvě možnosti jsou vývojové diagramy a pseudokód.

Použití vývojových diagramů k reprezentaci algoritmů

A vývojový diagram je vizuální reprezentace toku řízení algoritmu. Toto znázornění ilustruje příkazy, které je třeba provést, rozhodnutí, která je třeba provést, logický tok (pro iteraci a jiné účely) a terminály, které označují počáteční a koncový bod. Obrázek 1 ukazuje různé symboly, které vývojové diagramy používají k vizualizaci algoritmů.

Zvažte algoritmus, který inicializuje čítač na 0, čte znaky až do nového řádku (\ n) znak je vidět, zvýší počitadlo pro každý znak číslice, který byl přečten, a vytiskne hodnotu čítače po přečtení znaku nového řádku. Vývojový diagram na obrázku 2 ilustruje tok řízení tohoto algoritmu.

Jednoduchost vývojového diagramu a jeho schopnost vizuálně prezentovat tok řízení algoritmu (takže je snadné ho sledovat) jsou jeho hlavní výhody. Vývojové diagramy mají také několik nevýhod:

Je snadné zavádět chyby nebo nepřesnosti do vysoce podrobných vývojových diagramů z důvodu nudy spojené s jejich vykreslením.
Pozice, označení a připojení symbolů vývojového diagramu vyžaduje čas, dokonce i za použití nástrojů k urychlení tohoto procesu. Toto zpoždění může zpomalit vaše chápání algoritmu.
Vývojové diagramy patří do éry strukturovaného programování a nejsou tak užitečné v objektově orientovaném kontextu. Naproti tomu Unified Modeling Language (UML) je vhodnější pro vytváření objektově orientovaných vizuálních reprezentací.

Použití pseudokódu k reprezentaci algoritmů

Alternativou k vývojovým diagramům je pseudo kód, což je textová reprezentace algoritmu, který se blíží konečnému zdrojovému kódu. Pseudokód je užitečný pro rychlé zapsání reprezentace algoritmu. Protože se syntaxe netýká, neexistují žádná tvrdá pravidla pro psaní pseudokódu.

Při psaní pseudokódu byste se měli snažit o konzistenci. Díky konzistentnosti bude překlad pseudokódu do skutečného zdrojového kódu mnohem snazší. Zvažte například následující zastoupení pseudokódu předchozího protiorientovaného vývojového diagramu:

 DECLARE CHARACTER ch = '' DECLARE INTEGER count = 0 DO READ CH IF CH GE '0' AND ch LE '9' THEN count = count + 1 END IF UNTIL ch EQ '\ n' PRINT count END

Pseudokód nejprve představuje několik PROHLÁSIT příkazy, které zavádějí proměnné ch a počet, inicializováno na výchozí hodnoty. Poté se zobrazí a DĚLAT smyčka, která se provede DOKUDch obsahuje \ n (znak nového řádku), kdy smyčka končí a a TISK výstupy výpisu počethodnota.

Pro každou iteraci smyčky ČÍST způsobí načtení znaku z klávesnice (nebo možná souboru - v tomto případě nezáleží na tom, co tvoří základní vstupní zdroj) a přiřadí se ch. Pokud je tímto znakem číslice (jedna z 0 přes 9), počet je zvýšen o 1.

Výběr správného algoritmu

Datové struktury a algoritmy, které používáte, kriticky ovlivňují dva faktory ve vašich aplikacích:

Využití paměti (pro datové struktury).
CPU time (pro algoritmy, které interagují s těmito datovými strukturami).

Z toho vyplývá, že byste měli dbát zejména na algoritmy a datové struktury, které používáte pro aplikace, které budou zpracovávat velké množství dat. Patří mezi ně aplikace používané pro velká data a internet věcí.

Vyvažování paměti a CPU

Při výběru datové struktury nebo algoritmu někdy objevíte inverzní vztah mezi využitím paměti a časem CPU: čím méně paměti datová struktura využívá, tím více algoritmů spojených s časem CPU potřebuje ke zpracování datových položek datové struktury. Čím více paměti datová struktura využívá, tím méně algoritmů spojených s časem CPU bude ke zpracování datových položek potřebovat - což povede k rychlejším výsledkům algoritmu.

Pokud je to možné, měli byste se snažit vyvážit využití paměti s časem CPU. Tuto úlohu můžete zjednodušit analýzou algoritmů a určením jejich účinnosti. Jak dobře funguje jeden algoritmus proti druhému podobné povahy? Zodpovězení této otázky vám pomůže při výběru mezi několika algoritmy.

Měření účinnosti algoritmu

Některé algoritmy fungují lépe než jiné. Například algoritmus binárního vyhledávání je téměř vždy efektivnější než algoritmus lineárního vyhledávání - něco, co uvidíte sami v části 2. Chcete zvolit nejúčinnější algoritmus pro potřeby vaší aplikace, ale tato volba nemusí být tak zřejmá jak byste si mysleli.

Například co to znamená, pokud algoritmu Selection Sort (představenému v části 2) trvá 0,4 sekundy, než seřadí 10 000 celých čísel na daném stroji? Tato referenční hodnota je platná pouze pro konkrétní stroj, konkrétní implementaci algoritmu a pro velikost vstupních dat.

Jako počítačový vědec používáme časovou a prostorovou složitost k měření účinnosti algoritmu a jejich destilaci do funkce složitosti abstraktní podrobnosti implementace a běhového prostředí. Funkce složitosti odhalují rozptyl v časových a prostorových požadavcích algoritmu na základě množství vstupních dat:

A funkce časové složitosti měří algoritmus časová složitost- což znamená, jak dlouho trvá dokončení algoritmu.
A funkce prostorové složitosti měří algoritmus složitost prostoru- což znamená množství režie paměti požadované algoritmem k provedení jeho úkolu.

Obě funkce složitosti jsou založeny na velikosti vstupu (n), což nějakým způsobem odráží množství vstupních dat. Zvažte následující pseudokód pro tisk pole:

 PROHLÁSIT INTEGRA i, x [] = [10, 15, -1, 32] PRO i = 0 DO DÉLKY (x) - 1 TISK x [i] DALŠÍ i KONEC

Funkce časové složitosti a časové složitosti

Časovou složitost tohoto algoritmu můžete vyjádřit zadáním funkce časové složitosti t (n) = an+ b, kde A (konstantní multiplikátor) představuje dobu potřebnou k dokončení jedné iterace smyčky a b představuje čas nastavení algoritmu. V tomto příkladu je časová složitost lineární.