Tablica struktura danych — Array data structure

W informatyce , w strukturze danych układowych , lub po prostu w tablicy , to struktura danych, składający się ze zbioru elementów ( wartości lub zmiennych ), każdy zidentyfikowany co najmniej jednego indeksu tablicy albo klucza . Tablica jest przechowywana w taki sposób, że pozycja każdego elementu może być obliczona z jego krotki indeksowej za pomocą formuły matematycznej. Najprostszym typem struktury danych jest tablica liniowa, zwana także tablicą jednowymiarową.

Na przykład tablica 10 32-bitowych (4-bajtowych) zmiennych całkowitych, o indeksach od 0 do 9, może być przechowywana jako 10 słów pod adresami pamięci 2000, 2004, 2008, ..., 2036 (w systemie szesnastkowym : 0x7D0, 0x7D4, 0x7D8, ..., 0x7F4), aby element o indeksie i miał adres 2000 + ( i × 4).

Adres pamięci pierwszego elementu tablicy nazywany jest adresem pierwszym, adresem podstawowym lub adresem bazowym.

Ponieważ matematyczną koncepcję macierzy można przedstawić jako dwuwymiarową siatkę, dwuwymiarowe tablice są również czasami nazywane macierzami. W niektórych przypadkach termin „wektor” jest używany w obliczeniach w odniesieniu do tablicy, chociaż krotki, a nie wektory, są bardziej matematycznie poprawnym odpowiednikiem. Tabele są często implementowane w postaci tablic, zwłaszcza tablic przeglądowych ; słowo tablica jest czasem używane jako synonim słowa tablica .

Tablice należą do najstarszych i najważniejszych struktur danych i są używane przez prawie każdy program. Służą również do implementacji wielu innych struktur danych, takich jak listy i łańcuchy . Skutecznie wykorzystują logikę adresowania komputerów. W większości nowoczesnych komputerów i wielu zewnętrznych pamięciach masowych pamięć jest jednowymiarową tablicą słów, których indeksami są ich adresy. Procesory , zwłaszcza procesory wektorowe , są często optymalizowane pod kątem operacji na tablicach.

Tablice są przydatne głównie dlatego, że indeksy elementów mogą być obliczane w czasie wykonywania . Między innymi ta funkcja pozwala pojedynczej instrukcji iteracyjnej na przetwarzanie dowolnie wielu elementów tablicy. Z tego powodu elementy struktury danych tablicowych muszą mieć ten sam rozmiar i powinny używać tej samej reprezentacji danych. Zestaw poprawnych krotek indeksowych i adresy elementów (a stąd formuła adresowania elementów) są zwykle, ale nie zawsze, ustalone, gdy tablica jest w użyciu.

Termin tablica jest często używany w znaczeniu tablicowy typ danych , rodzaj danych dostarczanych przez większość języków programowania wysokiego poziomu, który składa się ze zbioru wartości lub zmiennych, które można wybrać za pomocą jednego lub większej liczby indeksów obliczonych w czasie wykonywania. Typy tablic są często implementowane przez struktury tablic; jednak w niektórych językach mogą być zaimplementowane przez tablice mieszające , listy połączone , drzewa wyszukiwania lub inne struktury danych.

Termin ten jest również używany, zwłaszcza w opisie algorytmów , w znaczeniu tablicy asocjacyjnej lub „tablicy abstrakcyjnej”, teoretycznego modelu informatycznego ( abstrakcyjny typ danych lub ADT) przeznaczonego do przechwytywania podstawowych właściwości tablic.

Historia

Pierwsze komputery cyfrowe wykorzystywały programowanie w języku maszynowym do konfigurowania i uzyskiwania dostępu do struktur tablicowych dla tabel danych, obliczeń wektorowych i macierzowych oraz do wielu innych celów. John von Neumann napisał pierwszy program do sortowania tablic (sortowanie przez scalanie ) w 1945 roku, podczas budowy pierwszego komputera z programami przechowywanymi w pamięci . ^{P. 159} Indeksowanie tablicy było pierwotnie wykonywane przez samomodyfikujący się kod , a później przy użyciu rejestrów indeksowych i adresowania pośredniego . Niektóre komputery mainframe zaprojektowane w latach 60., takie jak Burroughs B5000 i jego następcy, wykorzystywały segmentację pamięci do sprawdzania granic indeksów w sprzęcie.

Języki asemblerowe generalnie nie mają specjalnego wsparcia dla tablic, poza tym, co zapewnia sama maszyna. Najwcześniejsze języki programowania wysokiego poziomu, w tym FORTRAN (1957), Lisp (1958), COBOL (1960) i ALGOL 60 (1960), obsługiwały tablice wielowymiarowe, podobnie jak C (1972). W C++ (1983) istnieją szablony klas dla tablic wielowymiarowych, których wymiar jest ustalony w czasie wykonywania, jak również dla tablic elastycznych w czasie wykonywania.

Aplikacje

Tablice służą do implementacji wektorów matematycznych i macierzy , a także innych rodzajów tabel prostokątnych. Wiele baz danych , małych i dużych, składa się (lub zawiera) jednowymiarowe tablice, których elementami są rekordy .

Tablice służą do implementowania innych struktur danych, takich jak listy, sterty , tablice mieszające , deques , kolejki , stosy , łańcuchy i VListy. Oparte na tablicach implementacje innych struktur danych są często proste i efektywne przestrzennie ( niejawne struktury danych ), wymagają niewielkiego narzutu miejsca , ale mogą mieć słabą złożoność przestrzeni, szczególnie po zmodyfikowaniu, w porównaniu ze strukturami danych opartymi na drzewach (porównaj posortowaną tablicę z drzewo wyszukiwania ).

Jedna lub więcej dużych tablic jest czasami używana do emulacji dynamicznej alokacji pamięci w programie , w szczególności alokacji puli pamięci . Historycznie rzecz biorąc, był to czasami jedyny sposób na przenośną alokację „pamięci dynamicznej”.

Tablice mogą służyć do określania częściowego lub całkowitego przepływu sterowania w programach, jako zwarta alternatywa dla (w przeciwnym razie powtarzalnych) wielu IFinstrukcji. Są one znane w tym kontekście jako tabele sterujące i są używane w połączeniu z specjalnie skonstruowanym interpreterem, którego przepływ sterowania jest zmieniany zgodnie z wartościami zawartymi w tablicy. Tablica może zawierać wskaźniki do podprogramów (lub względne numery podprogramów, na które mogą działać instrukcje SWITCH ), które kierują ścieżką wykonania.

Identyfikator elementu i formuły adresowania

Gdy obiekty danych są przechowywane w tablicy, poszczególne obiekty są wybierane za pomocą indeksu, który zwykle jest nieujemną skalarną liczbą całkowitą . Indeksy są również nazywane indeksami dolnymi. Indeks odwzorowuje wartość tablicy na przechowywany obiekt.

Istnieją trzy sposoby indeksowania elementów tablicy:

0 ( indeksowanie od zera )

Pierwszy element tablicy jest indeksowany indeksem dolnym równym 0.

1 ( indeksowanie oparte na jedynce )

Pierwszy element tablicy jest indeksowany indeksem dolnym równym 1.

n ( indeksowanie oparte na n )

Bazowy indeks tablicy może być dowolnie wybrany. Zazwyczaj języki programowania umożliwiające indeksowanie oparte na liczbie n umożliwiają również ujemne wartości indeksów i inne skalarne typy danych, takie jak wyliczenia lub znaki, które mogą być używane jako indeks tablicy.

Korzystanie z indeksowania od zera jest wyborem wielu wpływowych języków programowania, w tym C , Java i Lisp . Prowadzi to do prostszej implementacji, w której indeks dolny odnosi się do przesunięcia od pozycji początkowej tablicy, więc pierwszy element ma przesunięcie równe zero.

Tablice mogą mieć wiele wymiarów, dlatego nie jest rzadkością dostęp do tablicy przy użyciu wielu indeksów. Na przykład dwuwymiarowa tablica Az trzema wierszami i czterema kolumnami może zapewniać dostęp do elementu w drugim wierszu i czwartej kolumnie za pomocą wyrażenia A[1][3]w przypadku systemu indeksowania od zera. Zatem dwa indeksy są używane dla tablicy dwuwymiarowej, trzy dla tablicy trójwymiarowej, a n dla tablicy n- wymiarowej.

Liczba indeksów potrzebnych do określenia elementu nazywana jest wymiarem, wymiarem lub rangą tablicy.

W standardowych tablicach każdy indeks jest ograniczony do pewnego zakresu kolejnych liczb całkowitych (lub kolejnych wartości jakiegoś wyliczeniowego typu ), a adres elementu jest obliczany przez „liniową” formułę na indeksach.

Tablice jednowymiarowe

Tablica jednowymiarowa (lub tablica jednowymiarowa) jest typem tablicy liniowej. Dostęp do jego elementów wymaga pojedynczego indeksu dolnego, który może reprezentować indeks wiersza lub kolumny.

Jako przykład rozważmy deklarację C, int anArrayName[10];która deklaruje jednowymiarową tablicę dziesięciu liczb całkowitych. Tutaj tablica może przechowywać dziesięć elementów typu int. Ta tablica ma indeksy od zera do dziewięciu. Na przykład wyrażenia anArrayName[0]i anArrayName[9]są odpowiednio pierwszym i ostatnim elementem.

W przypadku wektora z adresowaniem liniowym element o indeksie i znajduje się pod adresem B + c × i , gdzie B jest stałym adresem bazowym, a c stałą stałą, czasami nazywaną przyrostem adresu lub krokiem .

Jeśli prawidłowe indeksy elementów zaczynają się od 0, stała B jest po prostu adresem pierwszego elementu tablicy. Z tego powodu język programowania C określa, że ​​indeksy tablic zawsze zaczynają się od 0; i wielu programistów nazwie ten element „ zerowym ” zamiast „pierwszym”.

Można jednak wybrać indeks pierwszego elementu poprzez odpowiedni wybór adresu bazowego B . Na przykład, jeśli tablica ma pięć elementów o indeksach od 1 do 5, a adres bazowy B jest zastąpiony przez B + 30 c , indeksy tych samych elementów będą wynosić od 31 do 35. Jeśli numeracja nie zaczyna się od 0, stała B nie może być adresem żadnego elementu.

Tablice wielowymiarowe

W przypadku tablicy wielowymiarowej element o indeksach i , j miałby adres B + c · i + d · j , gdzie współczynniki c i d są odpowiednio przyrostami adresu wiersza i kolumny .

Bardziej ogólnie, w tablicy k- wymiarowej adres elementu o indeksach i ₁ , i ₂ , ..., i _k jest

B + c ₁ · i ₁ + c ₂ · i ₂ + … + c _k · i _k .

Na przykład: int a[2][3];

Oznacza to, że tablica a ma 2 wiersze i 3 kolumny, a tablica jest typu całkowitego. Tutaj możemy przechowywać 6 elementów, które będą przechowywane liniowo, ale zaczynając od pierwszego wiersza linearnie, a następnie kontynuując od drugiego wiersza. Powyższa tablica będzie przechowywana jako ₁₁ , a ₁₂ , a ₁₃ , a ₂₁ , a ₂₂ , a ₂₃ .

Ta formuła wymaga tylko k mnożenia i k dodawania dla dowolnej tablicy, która może zmieścić się w pamięci. Co więcej, jeśli dowolny współczynnik jest stałą potęgą 2, mnożenie można zastąpić przesunięciem bitowym .

Współczynniki c _k musi być wybrany tak, że co ważne krotka wskaźnik odwzorowuje adres odrębnego elementu.

Jeśli minimalna prawidłowa wartość każdego indeksu wynosi 0, to B jest adresem elementu, którego indeksy są równe zero. Podobnie jak w przypadku jednowymiarowym, indeksy elementów można zmienić poprzez zmianę adresu bazowego B . Tak więc, jeśli tablica dwuwymiarowa ma wiersze i kolumny indeksowane odpowiednio od 1 do 10 i od 1 do 20, to zastąpienie B przez B + c ₁ − 3 c ₂ spowoduje zmianę ich numeracji od 0 do 9 i od 4 do 23 , odpowiednio. Korzystając z tej funkcji, niektóre języki (takie jak FORTRAN 77) określają, że indeksy tablic zaczynają się od 1, tak jak w tradycji matematycznej, podczas gdy inne języki (takie jak Fortran 90, Pascal i Algol) pozwalają użytkownikowi wybrać minimalną wartość dla każdego indeksu.

Wektory narkotyków

Formuła adresowania jest całkowicie zdefiniowana przez wymiar d , adres bazowy B i przyrosty c ₁ , c ₂ , ..., c _k . Jest to często przydatne do pakowania tych parametrów w rejestrze zwanym tablicowej, która deskryptor lub biegowy wektor lub narkotyki wektor . Rozmiar każdego elementu oraz wartości minimalne i maksymalne dozwolone dla każdego indeksu mogą również być zawarte w wektorze dope. Wektor dope jest kompletnym uchwytem tablicy i jest wygodnym sposobem przekazywania tablic jako argumentów do procedur . Wiele przydatnych operacji wycinania tablicy (takich jak wybieranie podtablicy, zamiana indeksów lub odwracanie kierunku indeksów) można wykonać bardzo wydajnie, manipulując wektorem domieszki.

Kompaktowe układy

Często współczynniki są dobierane tak, aby elementy zajmowały ciągły obszar pamięci. Nie jest to jednak konieczne. Nawet jeśli tablice są zawsze tworzone z ciągłymi elementami, niektóre operacje wycinania tablic mogą tworzyć z nich nieciągłe podtablice.

Ilustracja kolejności wierszy i kolumn głównych

Istnieją dwa systematyczne, kompaktowe układy dla tablicy dwuwymiarowej. Rozważmy na przykład macierz

${\ Displaystyle A = {\ zacząć {bmatrix} 1 i 2 i 3 \ \ 4 i 5 i 6 \ \ 7 i 8 i 9 \ koniec {bmatrix}}.}$

W układzie wiersz-główny porządek (przyjęty przez C dla tablic deklarowanych statycznie) elementy w każdym wierszu są przechowywane na kolejnych pozycjach, a wszystkie elementy wiersza mają niższy adres niż którykolwiek z elementów kolejnego wiersza:

1

2

3

4

5

6

7

8

9

W kolejności głównej kolumny (tradycyjnie używanej przez Fortran), elementy w każdej kolumnie są kolejne w pamięci, a wszystkie elementy kolumny mają niższy adres niż którykolwiek z elementów kolejnej kolumny:

1

4

7

2

5

8

3

6

9

W przypadku tablic z trzema lub większą liczbą indeksów „wiersz major order” umieszcza w kolejnych pozycjach dowolne dwa elementy, których krotki indeksu różnią się tylko o jeden w ostatnim indeksie. „Porządek główny kolumny” jest analogiczny w odniesieniu do pierwszego indeksu.

W systemach wykorzystujących pamięć podręczną procesora lub pamięć wirtualną skanowanie tablicy jest znacznie szybsze, jeśli kolejne elementy są przechowywane w kolejnych pozycjach w pamięci, a nie są rozproszone. Wiele algorytmów wykorzystujących tablice wielowymiarowe skanuje je w przewidywalnej kolejności. Programista (lub wyrafinowany kompilator) może wykorzystać te informacje do wyboru między głównymi układami wierszy lub kolumn dla każdej tablicy. Na przykład, podczas obliczania iloczynu A · B dwóch macierzy, najlepiej byłoby przechowywać A w kolejności wiersz-główny, a B w kolejności kolumnowej-głównej.

Zmiana rozmiaru

Tablice statyczne mają rozmiar, który jest ustalony podczas ich tworzenia i w konsekwencji nie pozwalają na wstawianie ani usuwanie elementów. Jednak przydzielając nową tablicę i kopiując do niej zawartość starej tablicy, można efektywnie zaimplementować dynamiczną wersję tablicy; zobacz tablica dynamiczna . Jeśli ta operacja jest wykonywana rzadko, wstawienia na końcu tablicy wymagają tylko zamortyzowanego stałego czasu.

Niektóre struktury danych tablicowych nie przydzielają pamięci ponownie, ale przechowują liczbę używanych elementów tablicy, zwaną liczbą lub rozmiarem. Dzięki temu tablica staje się dynamiczną macierzą o ustalonym maksymalnym rozmiarze lub pojemności; Przykładami tego są łańcuchy Pascala .

Formuły nieliniowe

Czasami stosuje się bardziej skomplikowane (nieliniowe) formuły. Na przykład dla zwartej dwuwymiarowej tablicy trójkątnej formuła adresowania jest wielomianem stopnia 2.

Efektywność

Zarówno przechowywanie, jak i wybieranie przyjmują (deterministyczny najgorszy przypadek) stały czas . Tablice zajmują liniową ( O ( n )) przestrzeń w liczbie n elementów , które przechowują.

W tablicy z rozmiarem elementu k i na maszynie z rozmiarem linii pamięci podręcznej B bajtów, iteracja przez tablicę n elementów wymaga minimum chybień pamięci podręcznej pułapu( nk /B), ponieważ jej elementy zajmują ciągłe miejsca w pamięci. Jest to mniej więcej współczynnik B/ k lepszy niż liczba braków w pamięci podręcznej potrzebnych do uzyskania dostępu do n elementów w losowych lokalizacjach pamięci. W konsekwencji iteracja sekwencyjna po tablicy jest w praktyce zauważalnie szybsza niż iteracja po wielu innych strukturach danych, właściwość nazywana lokalnością odniesienia ( nie oznacza to jednak, że użycie idealnego lub trywialnego skrótu w ramach tej samej (lokalnej) tablicy , nie będzie jeszcze szybszy - i osiągalny w stałym czasie ). Biblioteki zapewniają niskopoziomowe zoptymalizowane funkcje do kopiowania zakresów pamięci (takich jak memcpy ), które mogą być używane do przenoszenia ciągłych bloków elementów tablicy znacznie szybciej niż można to osiągnąć poprzez dostęp do poszczególnych elementów. Przyspieszenie takich zoptymalizowanych procedur zależy od rozmiaru elementu tablicy, architektury i implementacji.

Pod względem pamięci tablice to kompaktowe struktury danych bez narzutu na element . Może występować narzut na tablicę (np. do przechowywania granic indeksu), ale jest to zależne od języka. Może się również zdarzyć, że elementy przechowywane w tablicy wymagają mniej pamięci niż te same elementy przechowywane w poszczególnych zmiennych, ponieważ kilka elementów tablicy może być przechowywanych w jednym słowie ; takie tablice są często nazywane tablicami upakowanymi . Skrajnym (ale powszechnie używanym) przypadkiem jest tablica bitów , gdzie każdy bit reprezentuje pojedynczy element. Pojedynczy oktet może zatem pomieścić do 256 różnych kombinacji do 8 różnych warunków, w najbardziej kompaktowej formie.

Dostęp do tablicy ze statycznie przewidywalnymi wzorcami dostępu jest głównym źródłem równoległości danych .

Porównanie z innymi strukturami danych

Tablice dynamiczne lub tablice rozwijalne są podobne do tablic, ale dodają możliwość wstawiania i usuwania elementów; dodawanie i usuwanie na końcu jest szczególnie wydajne. Rezerwują jednak liniową ( Θ ( n )) dodatkową pamięć, podczas gdy tablice nie rezerwują dodatkowej pamięci.

Tablice asocjacyjne zapewniają mechanizm zapewniający funkcjonalność podobną do tablicy bez ogromnych kosztów pamięci masowej, gdy wartości indeksów są rzadkie. Na przykład tablica, która zawiera wartości tylko o indeksach 1 i 2 miliardy, może skorzystać z zastosowania takiej struktury. Wyspecjalizowane tablice asocjacyjne z kluczami całkowitymi obejmują próby Patricia , tablice Judy i drzewa van Emde Boas .

Zrównoważone drzewa wymagają czasu O(log n ) dla dostępu indeksowanego, ale pozwalają również na wstawianie lub usuwanie elementów w czasie O(log n ), podczas gdy tablice z możliwością wzrostu wymagają czasu liniowego (Θ( n )), aby wstawić lub usunąć elementy w dowolnej pozycji.

Połączone listy umożliwiają usuwanie i wstawianie stałego czasu w środku, ale zaindeksowany dostęp zajmuje liniowy czas. Ich wykorzystanie pamięci jest zazwyczaj gorsze niż w przypadku tablic, ale nadal jest liniowe.

Iliffe wektor jest alternatywą dla konstrukcji wielowymiarowej tablicy. Używa jednowymiarowej tablicy odniesień do tablic o jeden wymiar mniej. W szczególności dla dwóch wymiarów ta alternatywna struktura byłaby wektorem wskaźników do wektorów, po jednym dla każdego wiersza (wskaźnik na c lub c++). W ten sposób element w wierszu i i kolumnie j tablicy A byłby dostępny przez podwójne indeksowanie ( A [ i ][ j ] w typowej notacji). Ta alternatywna struktura dopuszcza tablice postrzępione , w których każdy wiersz może mieć inny rozmiar — lub ogólnie, gdzie prawidłowy zakres każdego indeksu zależy od wartości wszystkich poprzednich indeksów. Zapisuje również jedno mnożenie (przez przyrost adresu kolumny) zastępując je przesunięciem bitowym (aby zindeksować wektor wskaźników wiersza) i jeden dodatkowy dostęp do pamięci (pobranie adresu wiersza), co może być opłacalne w niektórych architekturach.

Wymiar

Wymiar tablicy to liczba indeksów potrzebnych do wybrania elementu. Tak więc, jeśli tablica jest postrzegana jako funkcja na zbiorze możliwych kombinacji indeksów, jest to wymiar przestrzeni, której jej domena jest dyskretnym podzbiorem. Tak więc tablica jednowymiarowa to lista danych, tablica dwuwymiarowa to prostokąt danych, tablica trójwymiarowa to blok danych itp.

Nie należy tego mylić z wymiarem zbioru wszystkich macierzy z daną domeną, czyli liczbą elementów w tablicy. Na przykład tablica z 5 wierszami i 4 kolumnami jest dwuwymiarowa, ale takie macierze tworzą przestrzeń 20-wymiarową. Podobnie trójwymiarowy wektor może być reprezentowany przez jednowymiarową tablicę o rozmiarze trzy.

Zobacz też

Bibliografia