Datový typ pole - Array data type

V počítačové vědy , An typ pole je typ dat , který představuje soubor prvků ( hodnoty nebo veličin ), každý se zvolí jeden nebo více indexů (identifikace klíče), které mohou být vypočteny v době běhu během provádění programu. Takový Collection se obvykle nazývá proměnné pole , hodnota pole , nebo jednoduše pole . Analogicky s matematickými pojmy vektor a matice se typy polí s jedním a dvěma indexy často nazývají vektorový typ a maticový typ, resp. Obecněji lze vícerozměrný typ pole nazývat tenzorový typ .

Jazyková podpora pro typy polí může zahrnovat určité vestavěné datové typy polí, některé syntaktické konstrukce (konstruktory typu pole ), které může programátor použít k definování takových typů a deklaraci proměnných pole a speciální notaci pro indexování prvků pole. Například v programovacím jazyce Pascal , deklarace type MyTable = array [1..4,1..2] of integer, definuje nový datový typ pole s názvem MyTable. Deklarace var A: MyTablepak definuje proměnnou Atohoto typu, což je agregát osmi prvků, z nichž každý je celočíselnou proměnnou identifikovanou dvěma indexy. V Pascal programu, tyto prvky jsou označeny A[1,1], A[1,2], A[2,1]..., A[4,2]. Speciální typy polí jsou často definovány standardními knihovnami jazyka .

Dynamické seznamy jsou také běžnější a snadněji implementovatelné než dynamická pole . Typy polí se odlišují od typů záznamů hlavně proto, že umožňují počítat indexy prvků za běhu , jako v Pascalově přiřazení A[I,J] := A[N-I,2*J] . Tato funkce mimo jiné umožňuje jednomu iteračnímu příkazu libovolně zpracovat mnoho prvků proměnné pole.

V teoretičtějších kontextech, zejména v teorii typů a v popisu abstraktních algoritmů , termíny „pole“ a „typ pole“ někdy odkazují na abstraktní datový typ (ADT) nazývaný také abstraktní pole nebo mohou odkazovat na asociativní pole , matematický model se základními operacemi a chováním typického typu pole ve většině jazyků-v podstatě kolekce prvků, které jsou vybírány pomocí indexů vypočítaných za běhu.

V závislosti na jazyce se typy polí mohou překrývat (nebo s nimi lze identifikovat) jiné datové typy, které popisují agregáty hodnot, například seznamy a řetězce . Typy polí jsou často implementovány datovými strukturami pole , ale někdy jinými prostředky, jako jsou hashovací tabulky , propojené seznamy nebo vyhledávací stromy .

Dějiny

Programovací jazyk Superplan Heinze Rutishausera (1949–1951) obsahoval vícerozměrná pole. Rutishauser, přestože popisuje, jak by měl být sestaven překladač pro jeho jazyk, neimplementoval jej.

Jazyky sestavení a jazyky nízké úrovně, jako je BCPL, obecně nemají žádnou syntaktickou podporu pro pole.

Vzhledem k důležitosti struktur polí pro efektivní výpočet poskytovaly podporu pro vícerozměrná pole nejstarší programovací jazyky na vysoké úrovni, včetně FORTRAN (1957), COBOL (1960) a Algol 60 (1960).

Abstraktní pole

Datovou strukturu pole lze matematicky modelovat jako abstraktní datovou strukturu ( abstraktní pole ) se dvěma operacemi

se ( , I ): data uložená v prvku matice A , jejichž indexy jsou celé číslo n-tice I .
set ( , I , V ): pole, že výsledky nastavením hodnoty tohoto prvku do V .

Tyto operace jsou nutné ke splnění axiomů

get ( set ( A , I , V ), I ) =  V
get ( set ( A , I , V ), J ) =  get ( A , J ) if I  ≠  J

pro jakýkoli stav pole A , jakoukoli hodnotu V a libovolné n -tice I , J, pro které jsou definovány operace.

První axiom znamená, že každý prvek se chová jako proměnná. Druhý axiom znamená, že prvky s odlišnými indexy se chovají jako disjunktní proměnné, takže uložení hodnoty do jednoho prvku neovlivní hodnotu žádného jiného prvku.

Tyto axiomy nekladou žádná omezení na množinu platných indexových n-tic I , proto lze tento abstraktní model použít pro trojúhelníkové matice a další zvláštně tvarovaná pole.

Implementace

Aby bylo možné efektivně implementovat proměnné takových typů, jako jsou maticové struktury (s indexováním prováděným aritmetikou ukazatele ), mnoho jazyků omezuje indexy na celočíselné datové typy (nebo jiné typy, které lze interpretovat jako celá čísla, například bajty a výčtové typy ), a vyžadují, aby všechny prvky měly stejný datový typ a velikost úložiště. Většina těchto jazyků také omezuje každý index na konečný interval celých čísel, který zůstává pevný po celou dobu životnosti proměnné pole. V některých kompilovaných jazycích mohou být rozsahy indexů ve skutečnosti známy v době kompilace .

Na druhou stranu některé programovací jazyky poskytují liberálnější typy polí, které umožňují indexování libovolnými hodnotami, jako jsou čísla s plovoucí desetinnou čárkou , řetězce , objekty , odkazy atd. Takové hodnoty indexu nelze omezit na interval, tím méně pevný interval. Tyto jazyky tedy obvykle umožňují kdykoli vytvořit libovolné nové prvky. Tato volba vylučuje implementaci typů polí jako datových struktur pole. To znamená, že tyto jazyky používají syntaxi podobnou matici k implementaci obecnější sémantiky asociativních polí , a proto musí být implementovány hashovací tabulkou nebo jinou strukturou dat vyhledávání .

Jazyková podpora

Vícerozměrná pole

Počet indexů potřebných k určení prvku se nazývá dimenze , rozměrnost nebo hodnost typu pole. (Tato nomenklatura je v rozporu s pojmem dimenze v lineární algebře, kde jde o počet prvků. Řada čísel s 5 řádky a 4 sloupci, tedy 20 prvky, má tedy ve výpočetních kontextech dimenzi 2, ale představuje matice s dimenzí 4 x 5 nebo 20. v matematice. Také význam „hodnosti“ v počítačové vědě je podobný jejímu významu v tenzorové algebře, ale nikoli v pojmu lineární algebry v pořadí matice .)

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

Mnoho jazyků podporuje pouze jednorozměrná pole. V těchto jazycích je vícerozměrné pole obvykle reprezentováno vektorem Iliffe , jednorozměrným polem odkazů na pole o jednu dimenzi méně. Zvláště dvojrozměrné pole by bylo implementováno jako vektor ukazatelů na jeho řádky. 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). Tento způsob emulace vícerozměrných polí umožňuje vytváření zubatých polí , 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ů.

Tato reprezentace pro vícerozměrná pole je poměrně rozšířená v softwaru C a C ++. C a C ++ však budou používat lineární indexovací vzorec pro vícerozměrná pole, která jsou deklarována s velikostí časové konstanty kompilace, např. int A[10][20]Nebo int A[m][n], namísto tradičního int **A.

Zápis indexování

Většina programovacích jazyků, které podporují pole, podporují operace úložiště a výběru a mají speciální syntaxi pro indexování. Rané jazyky používaly závorky, např A(i,j). Jako ve FORTRAN; ostatní volí hranaté závorky, např. A[i,j]nebo A[i][j], jako v Algol 60 a Pascal (pro odlišení od použití závorek pro volání funkcí ).

Typy indexů

Datové typy pole jsou nejčastěji implementovány jako maticové struktury: s indexy omezenými na celočíselné (nebo zcela seřazené) hodnoty, rozsahy indexů pevné v době vytváření pole a adresování víceřádkových prvků. To byl případ většiny jazyků „třetí generace“ a stále je to případ většiny systémových programovacích jazyků, jako je Ada , C a C ++ . V některých jazycích však datové typy polí mají sémantiku asociativních polí s indexy libovolného typu a vytváření dynamických prvků. To je případ některých skriptovacích jazyků, jako je Awk a Lua , a některých typů polí poskytovaných standardními knihovnami C ++ .

Kontrola mezí

Některé jazyky (jako Pascal a Modula) provádějí kontrolu hranic při každém přístupu, vyvolání výjimky nebo přerušení programu, pokud je jakýkoli index mimo platný rozsah. Kompilátory mohou povolit tyto kontroly vypnout, aby byla zajištěna bezpečnost obchodu kvůli rychlosti. Jiné jazyky (jako FORTRAN a C) důvěřují programátorovi a neprovádějí žádné kontroly. Dobří kompilátoři mohou také analyzovat program, aby určili rozsah možných hodnot, které index může mít, a tato analýza může vést k eliminaci mezní kontroly .

Původ indexu

Některé jazyky, například C, poskytují pouze typy polí založené na nule , pro které je minimální platná hodnota pro jakýkoli index 0. Tato volba je vhodná pro implementaci polí a výpočty adres. V jazyce, jako je C, lze definovat ukazatel na vnitřek libovolného pole, který bude symbolicky fungovat jako pseudo-pole, které pojme negativní indexy. To funguje pouze proto, že C při použití nekontroluje index proti hranicím.

Jiné jazyky poskytují pouze jedno typy polí, kde každý index začíná na 1; toto je tradiční konvence v matematice pro matice a matematické sekvence . Několik jazyků, jako je Pascal a Lua, podporuje typy polí na bázi n , jejichž minimální právní indexy volí programátor. Relativní zásluhy každé volby byly předmětem bouřlivé debaty. Indexování založené na nule může zabránit chybám typu off-by-one nebo plotpost , konkrétně 0 na základě (i = 0; i <5; i+= 1) opakuje (5-0) krát, zatímco v ekvivalentní polovině založené na 1 -otevřený rozsah (i = 1; i <6; i+= 1) 5; i+= 1) opakuje (5-1) +1krát.

Viz srovnání programovacích jazyků (pole) pro základní indexy používané různými jazyky.

Nejvyšší index

Vztah mezi čísly uvedenými v deklaraci pole a indexem posledního prvku tohoto pole se také liší podle jazyka. V mnoha jazycích (například C) je třeba určit počet prvků obsažených v poli; zatímco v jiných (například Pascal a Visual Basic .NET ) je třeba zadat číselnou hodnotu indexu posledního prvku. Není nutné říkat, že toto rozlišení je v jazycích, kde indexy začínají na 1, jako je Lua, nepodstatné .

Array algebra

Některé programovací jazyky podporují programování pole , kde jsou operace a funkce definované pro určité datové typy implicitně rozšířeny na pole prvků těchto typů. Tak se může psát A + B pro přidání odpovídajících prvků dvou polí A a B . Obvykle se tyto jazyky poskytují jak prvek-za-prvku násobení a standardní matice produkt z lineární algebry , a který z nich je představována * operátor liší podle jazyka.

Od inovací v této oblasti APL se rozšířily jazyky poskytující možnosti programování polí . Toto jsou základní možnosti jazyků specifických pro doménu, jako jsou GAUSS , IDL , Matlab a Mathematica . Jsou základním zařízením v novějších jazycích, jako je Julia a nejnovější verze Fortranu . Tyto možnosti jsou také poskytovány prostřednictvím standardních knihoven rozšíření pro jiné programovací jazyky pro obecné účely (například široce používanou knihovnu NumPy pro Python ).

Typy řetězců a pole

Mnoho jazyků poskytuje vestavěný datový typ řetězce se specializovanou notací („ řetězcové literály “) pro vytváření hodnot tohoto typu. V některých jazycích (například C) je řetězec pouze řadou znaků nebo se s ním zachází v podstatě stejným způsobem. Jiné jazyky, například Pascal , mohou pro řetězce a pole poskytovat značně odlišné operace.

Dotazy na rozsah indexů pole

Některé programovací jazyky poskytují operace, které vracejí velikost (počet prvků) vektoru nebo obecněji rozsah každého indexu pole. V jazycích C a C ++ pole nepodporují funkci velikosti , takže programátoři často musí deklarovat samostatnou proměnnou, aby udrželi velikost, a předat ji procedurám jako samostatný parametr.

Prvky nově vytvořeného pole mohou mít nedefinované hodnoty (jako v C) nebo mohou být definovány tak, aby měly konkrétní „výchozí“ hodnotu, například 0 nebo nulový ukazatel (jako v Javě).

V C ++ objekt std :: vector podporuje operace úložiště , výběru a připojení s výše popsanými charakteristikami výkonu. Vektory lze dotazovat na jejich velikost a lze u nich měnit velikost. Podporovány jsou také pomalejší operace, jako je vložení prvku doprostřed.

Krájení

Operace krájení pole přebírá podmnožinu prvků entity typu pole (hodnota nebo proměnná) a poté je sestavuje jako jinou entitu typu pole, případně s jinými indexy. Pokud jsou typy polí implementovány jako struktury pole, lze mnoho užitečných operací krájení (jako je výběr dílčího pole, výměna indexů nebo obrácení směru indexů) provádět velmi efektivně manipulací s dopovým vektorem struktury. Možné krájení závisí na podrobnostech implementace: například FORTRAN umožňuje krájení jednoho sloupce maticové proměnné, ale nikoli řádku, a považuje to za vektor; vzhledem k tomu, že C umožňuje krájení řádku z matice, ale ne ze sloupce.

Na druhou stranu jsou možné další operace krájení, pokud jsou typy polí implementovány jinými způsoby.

Změna velikosti

Některé jazyky umožňují dynamické pole (nazývané také měnit velikost , growable nebo roztažitelný ): pole proměnné, jejichž index rozsahy mohou být kdykoliv rozšířit po vytvoření, aniž by se změnila hodnoty svých současných prvků.

U jednorozměrných polí může být toto zařízení poskytnuto jako operace " append( A , x )", která zvětší velikost pole A o jednu a poté nastaví hodnotu posledního prvku na x . Jiné typy polí (například řetězce Pascal) poskytují operátor zřetězení, který lze použít společně s krájením k dosažení tohoto efektu a dalších. V některých jazycích přiřazení hodnoty k prvku pole automaticky rozšíří pole, pokud je to nutné, o tento prvek zahrnout. V jiných typech polí může být řez nahrazen polem různé velikosti "s následným přečíslováním následujících prvků - jako v přiřazení seznamu v Pythonu" A [5: 5] = [10,20,30] ", které vloží tři nové prvky (10, 20 a 30) před prvkem „ A [5]“. Pole s možností změny velikosti jsou koncepčně podobné seznamům a tyto dva pojmy jsou v některých jazycích synonyma.

Rozšiřitelné pole lze implementovat jako pole pevné velikosti s čítačem, který zaznamenává, kolik prvků se skutečně používá. appendOperace pouze inkrementuje čítač; dokud není použito celé pole, kdy appendmůže být operace definována jako neúspěšná. Toto je implementace dynamického pole s pevnou kapacitou, jako u stringtypu Pascal. Alternativně může appendoperace znovu přidělit základní pole větší velikosti a zkopírovat staré prvky do nové oblasti.

Viz také

Související typy

Reference

externí odkazy