Niejawna struktura danych

W informatyce niejawna struktura danych lub wydajna przestrzennie struktura danych to struktura danych , która przechowuje bardzo mało informacji poza głównymi lub wymaganymi danymi: struktura danych, która wymaga niskiego narzutu . Nazywa się je „niejawnymi”, ponieważ położenie elementów niesie ze sobą znaczenie i związek między elementami; kontrastuje to z użyciem wskaźników , aby dać wyraźne związek między elementami. Definicje „niskiego narzutu” są różne, ale ogólnie oznacza stały narzut; w dużym notacji O , O (1) narzut. Mniej restrykcyjną definicją jest zwięzła struktura danych , która pozwala na większy narzut.

Definicja

Niejawna struktura danych to taka ze stałym narzutem przestrzeni O (1) (powyżej dolnej granicy teorii informacji ).

Historycznie rzecz biorąc, Munro i Suwanda (1980) zdefiniowali niejawną strukturę danych (i działające na niej algorytmy) jako taką, „w której informacje strukturalne są ukryte w sposobie przechowywania danych, a nie jawne we wskaźnikach”. Są nieco niejasne w definicji, definiując ją najściślej jako pojedynczą tablicę, z zachowanym tylko rozmiarem (pojedyncza liczba narzutu) lub bardziej luźno jako strukturę danych ze stałym narzutem ( O (1 ) ) . Ta ostatnia definicja jest dziś bardziej standardowa, a wciąż luźniejsze pojęcie struktury danych z niestałymi, ale małymi o (n) narzut jest dziś znany jako zwięzła struktura danych , zgodnie z definicją Jacobsona (1988) ; Munro i Suwanda (1980) określili to jako półukryte .

Podstawowe rozróżnienie dotyczy statycznych struktur danych (tylko do odczytu) i dynamicznych struktur danych (które można modyfikować). Proste ukryte struktury danych, takie jak reprezentowanie posortowanej listy jako tablicy, mogą być bardzo wydajne jako statyczna struktura danych, ale nieefektywne jako dynamiczna struktura danych, ze względu na operacje modyfikacji (takie jak wstawianie w przypadku posortowanej listy) nieskuteczny.

Przykłady

Trywialnym przykładem niejawnej struktury danych jest tablicowa struktura danych , która jest niejawną strukturą danych dla listy i wymaga jedynie stałego narzutu długości; w przeciwieństwie do połączonej listy , która ma wskaźnik powiązany z każdym elementem danych, który wyraźnie podaje związek między jednym elementem a drugim. Podobnie łańcuch zakończony znakiem null jest niejawną strukturą danych dla ciągu (lista postaci). Są one uważane za bardzo proste, ponieważ są statycznymi strukturami danych (tylko do odczytu) i dopuszczają jedynie prostą operację iteracji elementów.

Podobnie proste jest reprezentowanie tablicy wielowymiarowej jako pojedynczej tablicy 1-wymiarowej wraz z jej wymiarami. Na przykład przedstawienie m × n jako pojedynczej listy o długości m·n wraz z liczbami m i n (zamiast jako jednowymiarową tablicę wskaźników do każdej jednowymiarowej podtablicy). Elementy nie muszą być tego samego typu, a tabela danych (lista rekordów ) może być podobnie niejawnie reprezentowana jako płaska (1-wymiarowa) lista, wraz z długością każdego pola , o ile każde pole ma jednakowy rozmiar (więc jeden rozmiar może być używany dla pola, a nie dla rekordu).

Mniej trywialnym przykładem jest reprezentacja posortowanej listy za pomocą posortowanej tablicy , która umożliwia wyszukiwanie w czasie logarytmicznym za pomocą wyszukiwania binarnego . Porównaj z drzewem wyszukiwania , w szczególności drzewem wyszukiwania binarnego , które również umożliwia wyszukiwanie w czasie logarytmicznym, ale wymaga wskaźników. Posortowana tablica jest wydajna tylko jako statyczna struktura danych, ponieważ modyfikacja listy jest powolna - w przeciwieństwie do drzewa wyszukiwania binarnego - ale nie wymaga narzutu miejsca na drzewo.

Ważnym przykładem niejawnej struktury danych jest reprezentacja doskonałego drzewa binarnego jako listy, w rosnącej kolejności głębokości, więc korzeń, pierwsze lewe dziecko, pierwsze prawe dziecko, pierwsze lewe dziecko pierwszego lewego dziecka itp. Takie drzewo występuje w szczególności dla wykresu przodków do określonej głębokości, a ukryta reprezentacja jest znana jako Ahnentafel (tabela przodków).

Można to uogólnić do pełnego drzewa binarnego (gdzie ostatni poziom może być niekompletny), co daje najbardziej znany przykład niejawnej struktury danych, a mianowicie stertę binarną , która jest niejawną strukturą danych dla kolejki priorytetowej . Jest to bardziej wyrafinowane niż wcześniejsze przykłady, ponieważ umożliwia wiele operacji i jest wydajną dynamiczną strukturą danych (pozwala na wydajną modyfikację danych): nie tylko top , ale także insert i pop .

Bardziej wyrafinowane ukryte struktury danych obejmują beap (sterta dwóch rodziców).

Historia

Trywialne przykłady list lub tabel wartości pochodzą z prehistorii, podczas gdy historycznie nietrywialne ukryte struktury danych pochodzą co najmniej z Ahnentafel, który został wprowadzony przez Michaëla Eytzingera w 1590 r. Do użytku w genealogii. W formalnej informatyce pierwszą niejawną strukturą danych jest ogólnie uważana posortowana lista używana do wyszukiwania binarnego, która została wprowadzona przez Johna Mauchly'ego w 1946 r . temat. Sterta binarna została wprowadzona w Williamsie (1964) , aby zaimplementować sortowanie sterty . Pojęcie niejawnej struktury danych zostało sformalizowane w Munro i Suwanda (1980) jako część wprowadzania i analizowania beapa .

Dalsza lektura

Zobacz publikacje Hervé Brönnimanna , J. Iana Munro i Grega Fredericksona .

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Implicit_data_structure&oldid=1036275140 ”