Datová struktura pole - Array data structure

Ve výpočetní techniky , což je datová struktura pole , nebo jednoduše jako pole , je datová struktura se skládá z kolekce prvků ( hodnoty nebo veličin ), každý je identifikován alespoň jeden index pole nebo klíče . Pole je uloženo tak, že polohu každého prvku lze vypočítat z jeho indexové n -tice pomocí matematického vzorce. Nejjednodušším typem datové struktury je lineární pole, nazývané také jednorozměrné pole.

Například pole 10 32-bit (4-byte) celočíselné proměnné, s indexy 0 až 9, mohou být uloženy jako 10 slov na adresy paměti 2000, 2004, 2008, ..., 2036 (v hexadecimální soustavě : 0x7D0, 0x7D4,, 0x7D8..., 0x7F4) tak, aby prvek s indexem i měl adresu 2000 + ( i × 4).

Adresa paměti prvního prvku pole se nazývá první adresa, základová adresa nebo základní adresa.

Protože matematický koncept matice může být reprezentován jako dvourozměrná mřížka, dvourozměrná pole se také někdy nazývají matice. V některých případech je termín „vektor“ použit při výpočtu pro označení pole, i když matematicky správnějším ekvivalentem jsou spíše n -tice než vektory . Tabulky jsou často implementovány ve formě polí, zejména vyhledávacích tabulek ; tabulka slov je někdy používána jako synonymum pole .

Pole patří mezi nejstarší a nejdůležitější datové struktury a používá je téměř každý program. Používají se také k implementaci mnoha dalších datových struktur, jako jsou seznamy a řetězce . Účinně využívají logiku adresování počítačů. Ve většině moderních počítačů a mnoha externích úložných zařízeních je paměť jednorozměrné pole slov, jejichž indexy jsou jejich adresy. Procesory , zejména vektorové , jsou často optimalizovány pro operace v poli.

Pole jsou užitečná hlavně proto, že indexy prvků lze vypočítat za běhu . Tato funkce mimo jiné umožňuje jednomu iteračnímu příkazu libovolně zpracovat mnoho prvků pole. Z tohoto důvodu musí mít prvky datové struktury pole stejnou velikost a měly by používat stejnou datovou reprezentaci. Sada platných rejstříků indexů a adresy prvků (a tedy vzorec pro adresování prvků) jsou obvykle, ale ne vždy, pevné, když je pole používáno.

Termín pole se často používá k označení datového typu pole , což je druh datového typu poskytovaného většinou programovacích jazyků na vysoké úrovni, který se skládá ze souboru hodnot nebo proměnných, které lze vybrat jedním nebo více indexy vypočítanými za běhu. Typy polí jsou často implementovány strukturami pole; v některých jazycích je však lze implementovat pomocí hashovacích tabulek , propojených seznamů , vyhledávacích stromů nebo jiných datových struktur.

Termín je také používán, obzvláště v popisu algoritmů , znamenat asociativní pole nebo "abstraktní pole", model teoretické počítačové vědy ( abstraktní datový typ nebo ADT), určený k zachycení základních vlastností polí.

Dějiny

První digitální počítače používaly programování ve strojovém jazyce k nastavení a přístupu ke strukturám polí pro datové tabulky, vektorové a maticové výpočty a pro mnoho dalších účelů. John von Neumann napsal první program pro třídění polí ( sloučení ) v roce 1945, při stavbě prvního počítače s uloženým programem . p. 159 Indexování pole bylo původně prováděno pomocí samočinně se měnícího kódu a později pomocí indexových registrů a nepřímého adresování . Některé sálové počítače navržené v šedesátých letech minulého století, například Burroughs B5000 a jeho nástupci, používaly segmentaci paměti k provádění kontroly indexu v hardwaru.

Jazyky sestavení obecně nemají žádnou zvláštní podporu pro pole, kromě toho, co poskytuje samotný stroj. Nejdříve programovací jazyky na vysoké úrovni, včetně FORTRAN (1957), Lisp (1958), COBOL (1960) a ALGOL 60 (1960), měly podporu pro vícerozměrná pole, stejně jako C (1972). V C ++ (1983) existují šablony tříd pro vícerozměrná pole, jejichž dimenze je pevná za běhu, stejně jako pro pole flexibilní za běhu.

Aplikace

Pole se používají k implementaci matematických vektorů a matic , stejně jako jiných druhů obdélníkových tabulek. Mnoho databází , malých i velkých, se skládá (nebo zahrnuje) jednorozměrná pole, jejichž prvky jsou záznamy .

Pole se používají k implementaci dalších datových struktur, jako jsou seznamy, haldy , hashovací tabulky , deques , fronty , zásobníky , řetězce a VLists. Implementace jiných datových struktur založené na poli jsou často jednoduché a prostorově efektivní ( implicitní datové struktury ), které vyžadují malou prostorovou režii , ale mohou mít špatnou prostorovou složitost, zejména při úpravách, ve srovnání se stromovými datovými strukturami (porovnat seřazené pole s vyhledávací strom ).

Jeden nebo více velkých polí se někdy používají k emulaci in-programu přidělení dynamické paměti , zvláště paměti bazénu alokace. Historicky to byl někdy jediný způsob, jak alokovat „dynamickou paměť“ přenosně.

Pole lze použít k určení částečného nebo úplného řídicího toku v programech jako kompaktní alternativu k (jinak opakujícím se) vícenásobným IFpříkazům. V této souvislosti jsou známy jako řídicí tabulky a používají se ve spojení s účelově vytvořeným tlumočníkem, jehož tok řízení se mění podle hodnot obsažených v poli. Pole může obsahovat ukazatele podprogramů (nebo relativní čísla podprogramů, na které lze působit pomocí příkazů SWITCH ), které řídí cestu provedení.

Identifikátor prvku a adresovací vzorce

Když jsou datové objekty uloženy v poli, jsou jednotlivé objekty vybírány pomocí indexu, který je obvykle nezáporným skalárním celým číslem . Indexům se také říká předpisy. Index mapuje hodnotu pole na uložený objekt.

Existují tři způsoby, kterými lze indexovat prvky pole:

0 ( indexování založené na nule )
První prvek pole je indexován indexem 0.
1 ( indexování podle jednoho )
První prvek pole je indexován indexem 1.
n ( indexování na základě n )
Základní index pole lze libovolně zvolit. Programovací jazyky, které umožňují indexování založené na n, také umožňují negativní hodnoty indexu a další skalární datové typy, jako jsou výčty , nebo znaky mohou být použity jako index pole.

Používání indexování založeného na nule je návrhovou volbou mnoha vlivných programovacích jazyků, včetně C , Java a Lisp . To vede k jednodušší implementaci, kde dolní index odkazuje na posun od počáteční pozice pole, takže první prvek má posunutí nula.

Pole mohou mít více dimenzí, proto není neobvyklé přistupovat k poli pomocí více indexů. Například dvourozměrné pole Ase třemi řádky a čtyřmi sloupci může poskytovat přístup k prvku na 2. řádku a 4. sloupci výrazem A[1][3]v případě systému indexování založeného na nule. Dva indexy se tedy používají pro dvourozměrné pole, tři pro trojrozměrné pole a n pro n -rozměrné pole.

Počet indexů potřebných k určení prvku se nazývá dimenze, rozměrnost nebo hodnost pole.

Ve standardních polích je každý index omezen na určitý rozsah po sobě jdoucích celých čísel (nebo po sobě jdoucích hodnot nějakého výčtového typu ) a adresa prvku je vypočítána „lineárním“ vzorcem na indexech.

Jednorozměrná pole

Jednorozměrné pole (nebo jednorozměrné pole) je typ lineárního pole. Přístup k jeho prvkům zahrnuje jeden dolní index, který může představovat index řádku nebo sloupce.

Jako příklad zvažte deklaraci C, int anArrayName[10];která deklaruje jednorozměrné pole deseti celých čísel. Zde může pole uložit deset prvků typu int. Toto pole má indexy začínající od nuly do devíti. Například výrazy anArrayName[0]a anArrayName[9]jsou první a poslední prvek.

U vektoru s lineárním adresováním je prvek s indexem i umístěn na adrese B + c × i , kde B je pevná základní adresa a c pevná konstanta, někdy se jí říká přírůstek adresy nebo krok .

Pokud platné indexy prvků začínají na 0, je konstanta B jednoduše adresou prvního prvku pole. Z tohoto důvodu programovací jazyk C určuje, že indexy polí začínají vždy na 0; a mnoho programátorů bude tento prvek nazývat „ nulový “ spíše než „první“.

Nicméně, jeden může vybrat index prvního prvku vhodnou volbou základní adresy B . Pokud má pole například pět prvků indexovaných od 1 do 5 a základní adresa B je nahrazena B + 30 c , pak budou indexy stejných prvků 31 až 35. Pokud číslování nezačne na 0, konstanta B nemusí být adresou žádného prvku.

Vícerozměrná pole

Pro vícerozměrné pole by prvek s indexy i , j měl adresu B + c · i + d · j , kde koeficienty c a d jsou přírůstky adres řádků a sloupců .

Obecněji, v K rozměrné pole, adresa prvku s indexy i 1 , i 2 , ..., i k je

B + c 1 · i 1 + c 2 · i 2 +… + c k · i k .

Například: int a [2] [3];

To znamená, že pole a má 2 řádky a 3 sloupce a pole je celočíselného typu. Zde můžeme uložit 6 prvků, které budou uloženy lineárně, ale počínaje lineárním prvním řádkem a pokračujícím druhým řádkem. Výše uvedené pole bude uloženo jako 11 , a 12 , a 13 , a 21 , a 22 , a 23 .

Tento vzorec vyžaduje pouze k násobení a k sčítání pro každé pole, které se vejde do paměti. Navíc, pokud je jakýkoli koeficient fixní mocninou 2, lze násobení nahradit bitovým posunem .

Koeficienty c k musí být zvoleny tak, aby se každá platná indexová n -tice mapovala na adresu odlišného prvku.

Pokud je minimální legální hodnota pro každý index 0, pak B je adresa prvku, jehož indexy jsou všechny nulové. Stejně jako v jednorozměrném případě, mohou být indexy prvek mění změnou základní adresy B . Tedy, v případě, že dvourozměrné pole má řádků a sloupců indexovány 1 až 10 a 1 až 20, v tomto pořadí, pak se nahradí B od B + C 1 - 3 c 2 způsobí, že se označuje jako od 0 do 9 a 4 až 23, , resp. S využitím této funkce některé jazyky (jako FORTRAN 77) uvádějí, že indexy polí začínají na 1, jako v matematické tradici, zatímco jiné jazyky (jako Fortran 90, Pascal a Algol) umožňují uživateli zvolit minimální hodnotu pro každý index.

Dope vektory

Adresní vzorec je zcela definován dimenzí d , základní adresou B a přírůstky c 1 , c 2 , ..., c k . Často je užitečné sbalit tyto parametry do záznamu nazývaného deskriptor pole nebo krokový vektor nebo dope vektor . Velikost každého prvku a minimální a maximální hodnoty povolené pro každý index mohou být také zahrnuty do dopového vektoru. Dope vektor je kompletní popisovač pro pole a je pohodlný způsob, jak předávat pole jako argumenty procedurám . Mnoho užitečných operací krájení pole (jako je výběr dílčího pole, výměna indexů nebo obrácení směru indexů) lze provádět velmi efektivně manipulací s dopovým vektorem.

Kompaktní rozvržení

Koeficienty jsou často voleny tak, aby prvky zabíraly souvislou oblast paměti. To však není nutné. I když jsou pole vždy vytvořena se souvislými prvky, některé operace krájení pole z nich mohou vytvářet nesouvislé dílčí pole.

Ilustrace řádkové a sloupcové hlavní objednávky

Pro dvourozměrné pole existují dvě systematická kompaktní rozvržení. Zvažte například matici

V uspořádání řádků hlavních řádků (přijato C pro staticky deklarovaná pole) jsou prvky v každém řádku uloženy v po sobě jdoucích pozicích a všechny prvky řádku mají nižší adresu než kterýkoli z prvků po sobě jdoucích řádků:

1 2 3 4 5 6 7 8 9

V pořadí hlavních sloupců (tradičně používané Fortranem) jsou prvky v každém sloupci po sobě jdoucí v paměti a všechny prvky sloupce mají nižší adresu než kterýkoli z prvků po sobě jdoucích sloupců:

1 4 7 2 5 8 3 6 9

U polí se třemi nebo více indexy „řádkový řád“ umístí do po sobě jdoucích pozic libovolné dva prvky, jejichž rejstříky indexů se v posledním indexu liší pouze o jeden . „Sloupcový hlavní řád“ je analogický s prvním indexem.

V systémech, které používají mezipaměť procesoru nebo virtuální paměť , je skenování pole mnohem rychlejší, pokud jsou po sobě jdoucí prvky uloženy v po sobě jdoucích pozicích v paměti, spíše než řídce rozptýleny. Mnoho algoritmů, které používají vícerozměrná pole, je bude skenovat v předvídatelném pořadí. Programátor (nebo propracovaný kompilátor) může použít tyto informace k výběru mezi řádkovým nebo sloupcovým rozložením pro každé pole. Například při výpočtu součinu A · B dvou matic by bylo nejlepší mít A uložené v pořadí hlavní řádky a B ve sloupcovém pořadí.

Změna velikosti

Statické pole mají velikost, která je při vytváření pevná, a v důsledku toho neumožňují vložení nebo odebrání prvků. Přidělením nového pole a zkopírováním obsahu starého pole do něj je však možné efektivně implementovat dynamickou verzi pole; viz dynamické pole . Pokud se tato operace provádí zřídka, vložení na konci pole vyžadují pouze amortizovaný konstantní čas.

Některé datové struktury pole nepřerozdělují úložiště, ale ukládají počet použitých prvků pole, nazývaný počet nebo velikost. Díky tomu je pole dynamickým polem s pevnou maximální velikostí nebo kapacitou; Pascalovy řetězce jsou toho příkladem.

Nelineární vzorce

Občas se používají složitější (nelineární) vzorce. Například pro kompaktní dvourozměrné trojúhelníkové pole je adresovací vzorec polynom stupně 2.

Účinnost

Oba ukládají a vybírají konstantní čas (deterministický nejhorší případ) . Pole zabírají lineární ( O ( n )) prostor v počtu prvků n , které drží.

V poli s velikostí prvku k a na počítači s velikostí řádku mezipaměti B bytů vyžaduje iterace prostřednictvím pole n prvků minimum chyb mezipaměti stropu ( nk /B), protože jeho prvky zabírají souvislá paměťová místa. To je zhruba faktor B/ k lepší než počet chyb mezipaměti potřebných pro přístup k n prvkům na náhodných paměťových místech. V důsledku toho postupné iterace přes pole je výrazně rychlejší v praxi než iterace přes mnoho jiných datových struktur, vlastnost nazývá lokalitou odkazu (to však není neznamená však, že s použitím dokonalé hash nebo triviální hash ve stejném (lokálním) matice , nebude ještě rychlejší - a dosažitelné v konstantním čase ). Knihovny poskytují nízkoúrovňové optimalizované zařízení pro kopírování rozsahů paměti (například memcpy ), které lze použít k přesouvání souvislých bloků prvků pole výrazně rychleji, než je možné dosáhnout prostřednictvím přístupu k jednotlivým prvkům. Zrychlení takto optimalizovaných rutin se liší podle velikosti prvku pole, architektury a implementace.

Z hlediska paměti jsou pole kompaktní datové struktury bez režie na prvek . Může existovat režie na pole (např. Pro uložení mezí indexu), ale to závisí na jazyce. Může se také stát, že prvky uložené v poli vyžadují méně paměti než stejné prvky uložené v jednotlivých proměnných, protože do jednoho slova lze uložit několik prvků pole ; taková pole se často nazývají zabalená pole. Extrémním (ale běžně používaným) případem je bitové pole , kde každý bit představuje jeden prvek. Jeden oktet tak může pojmout až 256 různých kombinací až 8 různých podmínek, v té nejkompaktnější formě.

Array přístupy se staticky předvídatelnými přístupovými vzory jsou hlavním zdrojem datového paralelismu .

Porovnání s jinými datovými strukturami

Porovnání struktur datových seznamů
Nahlédnout Mutovat (vložit nebo smazat) v ... Přebytečný prostor,
průměr
Začátek Konec Střední
Spojový seznam Θ ( n ) Θ (1) Θ (1), známý koncový prvek;
Θ ( n ), neznámý koncový prvek
Čas
nakouknutí + Θ (1)
Θ ( n )
Pole Θ (1) N/A N/A N/A 0
Dynamické pole Θ (1) Θ ( n ) Θ (1) amortizováno Θ ( n ) Θ ( n )
Vyrovnaný strom Θ (log n) Θ (log n) Θ (log n ) Θ (log n ) Θ ( n )
Seznam náhodného přístupu Θ (log n) Θ (1) N/A N/A Θ ( n )
Hašovaný strom pole Θ (1) Θ ( n ) Θ (1) amortizováno Θ ( n ) Θ (√ n )

Dynamická pole nebo rozšiřitelná pole jsou podobná maticím, ale přidávají možnost vkládat a odstraňovat prvky; zvláště účinné je přidání a odstranění na konci. Vyhrazují si však lineární ( Θ ( n )) dodatečné úložiště, zatímco pole nevyhrazují další úložiště.

Asociativní pole poskytují mechanismus pro funkce podobné poli bez velkých režijních nákladů na úložiště, když jsou hodnoty indexu řídké. Například pole, které obsahuje hodnoty pouze na indexech 1 a 2 miliardy, může mít z použití takové struktury prospěch. Specializovaná asociativní pole s celočíselnými klíči zahrnují Patricia try , Judy arra a van Emde Boas stromy .

Vyvážené stromy vyžadují čas O (log n ) pro indexovaný přístup, ale také umožňují vkládání nebo odstraňování prvků v čase O (log n ), zatímco rozšiřitelná pole vyžadují lineární (Θ ( n )) čas pro vložení nebo odstranění prvků na libovolné pozici.

Propojené seznamy umožňují odebírání a vkládání ve středu konstantní, ale pro indexovaný přístup vyžadují lineární čas. Jejich využití paměti je obvykle horší než pole, ale stále je lineární.

Dvourozměrné pole uložené jako jednorozměrné pole jednorozměrných polí (řádků).

Iliffe vektor je alternativou k vícerozměrné struktury pole. Používá jednorozměrné pole odkazů na pole o jednu dimenzi méně. Zejména pro dvě dimenze by tato alternativní struktura byla vektorem ukazatelů na vektory, jedním pro každý řádek (ukazatel na c nebo c ++). K prvku v řádku i a sloupci j pole A by se tedy přistupovalo dvojitým indexováním ( A [ i ] [ j ] v typickém zápisu). Tato alternativní struktura umožňuje zubatá pole , kde každý řádek může mít jinou velikost - nebo obecně kde platný rozsah každého indexu závisí na hodnotách všech předchozích indexů. Ušetří také jedno násobení (přírůstkem adresy sloupce) a jeho nahrazení bitovým posunem (pro indexování vektoru ukazatelů řádků) a jeden další přístup do paměti (načtení adresy řádku), což se v některých architekturách může vyplatit.

Dimenze

Dimenze pole je počet indexů potřebných k výběru prvku. Pokud je tedy pole chápáno jako funkce na sadě možných kombinací indexů, je to rozměr prostoru, jehož doménou je diskrétní podmnožina. Jednorozměrné pole je tedy seznam dat, dvourozměrné pole je obdélník dat, trojrozměrné pole je blok dat atd.

To by nemělo být zaměňováno s dimenzí sady všech matic s danou doménou, tj. S počtem prvků v poli. Například pole s 5 řádky a 4 sloupci je dvourozměrné, ale takové matice tvoří 20-rozměrný prostor. Podobně může být trojrozměrný vektor reprezentován jednorozměrným polem o velikosti tři.

Viz také

Reference