Zestaw (abstrakcyjny typ danych) - Set (abstract data type)

W informatyce , wykorzystując zestaw jest abstrakcyjny typ danych , które można przechowywać unikalne wartości, bez żadnego konkretnego celu . Jest to komputerowa implementacja matematycznego pojęcia zbioru skończonego . W przeciwieństwie do większości innych typów kolekcji , zamiast pobierania określonego elementu z zestawu, zazwyczaj testuje się wartość członkostwa w zestawie.

Niektóre struktury danych zestawu są przeznaczone dla zestawów statycznych lub zamrożonych , które nie zmieniają się po ich skonstruowaniu. Zestawy statyczne umożliwiają tylko operacje zapytań na ich elementach — takie jak sprawdzanie, czy dana wartość znajduje się w zestawie lub wyliczanie wartości w dowolnej kolejności. Inne warianty, zwane zestawami dynamicznymi lub zmiennymi , pozwalają również na wstawianie i usuwanie elementów ze zbioru.

Multiset to specjalny rodzaj zestawu, w którym element może dowiedzieć się kilka razy.

Teoria typów

W teorii typów zbiory są na ogół utożsamiane z ich funkcją wskaźnika ( funkcją charakterystyczną): odpowiednio zbiór wartości typu może być oznaczony przez lub . (Podtypy i podzbiory mogą być modelowane przez typy uściślenia , a zbiory ilorazowe można zastąpić setoidami .) Charakterystyczną funkcję zbioru definiuje się jako: ${\ Displaystyle A}$ ${\ Displaystyle 2 ^ {A}}$ ${\ Displaystyle {\ Mathcal {P}} (A)}$ ${\ Displaystyle F}$ $S$

{\ Displaystyle F (x) = {\ zacząć {przypadki} 1 i {\ mbox {jeśli}} x \ w S \ \ 0 i {\ mbox {jeśli}} x \ nie \ w S \ koniec {przypadki }}}

Teoretycznie wiele innych abstrakcyjnych struktur danych można postrzegać jako struktury zbioru z dodatkowymi operacjami i/lub dodatkowymi aksjomatami nałożonymi na standardowe operacje. Na przykład abstrakcyjna sterta może być postrzegana jako struktura zestawu z operacją zwracającą element o najmniejszej wartości. min(S)

Operacje

Operacje na zbiorach podstawowych

Można zdefiniować działania algebry zbiorów :

union(S,T): zwraca sumę zbiorów S i T .
intersection(S,T): zwraca część wspólną zbiorów S i T .
difference(S,T): zwraca różnicę zbiorów S i T .
subset(S,T): predykat sprawdzający, czy zbiór S jest podzbiorem zbioru T .

Zestawy statyczne

Typowe operacje, które mogą być zapewnione przez statyczną strukturę zbioru S to:

is_element_of(x,S): sprawdza, czy wartość x znajduje się w zbiorze S .
is_empty(S): sprawdza, czy zbiór S jest pusty.
size(S)lub : zwraca liczbę elementów w S .cardinality(S)
iterate(S): zwraca funkcję, która zwraca jeszcze jedną wartość S przy każdym wywołaniu, w dowolnej kolejności.
enumerate(S): zwraca listę zawierającą elementy S w dowolnej kolejności.
build(x₁,x₂,…,x_n,): tworzy strukturę zbioru z wartościami x ₁ , x ₂ ,..., x _n .
create_from(collection): tworzy nową strukturę zbioru zawierającą wszystkie elementy danej kolekcji lub wszystkie elementy zwrócone przez dany iterator .

Zestawy dynamiczne

Struktury zestawów dynamicznych zazwyczaj dodają:

create(): tworzy nową, początkowo pustą strukturę zestawu.
- create_with_capacity(n): tworzy nową strukturę zestawu, początkowo pustą, ale zdolną pomieścić do n elementów.
add(S,x): dodaje element x do S , jeśli jeszcze go nie ma.
remove(S, x): usuwa element x z S , jeśli jest obecny.
capacity(S): zwraca maksymalną liczbę wartości, które S może przechowywać.

Niektóre struktury zestawów mogą zezwalać tylko na niektóre z tych operacji. Koszt każdej operacji będzie zależał od implementacji, a być może także od poszczególnych wartości zapisanych w zestawie i kolejności ich wstawiania.

Dodatkowe operacje

Istnieje wiele innych operacji, które można (w zasadzie) zdefiniować w kategoriach powyższych, takich jak:

pop(S): zwraca dowolny element S , usuwając go z S .
pick(S): zwraca dowolny element S . Funkcjonalnie mutator popmożna interpretować jako parę selektorów, (pick, rest),gdzie restzwraca zestaw składający się ze wszystkich elementów z wyjątkiem dowolnego elementu. Można interpretować w kategoriach iterate.
map(F,S): zwraca zestaw odrębnych wartości wynikających z zastosowania funkcji F do każdego elementu S .
filter(P,S): zwraca podzbiór zawierający wszystkie elementy S, które spełniają dany predykat P .
fold(A₀,F,S): zwraca wartość A _{| S |}po zastosowaniu dla każdego elementu e z S, dla jakiejś operacji binarnej F. F musi być asocjacyjne i przemienne, aby było to dobrze zdefiniowane.A_i+1 := F(A_i, e)
clear(S): usuń wszystkie elementy S .
equal(S₁', S₂'): sprawdza, czy dwa podane zestawy są równe (tzn. zawierają wszystkie i tylko te same elementy).
hash(S): zwraca wartość skrótu dla statycznego zbioru S taką, że jeśli wtedyequal(S₁, S₂)hash(S₁) = hash(S₂)

Inne operacje można zdefiniować dla zestawów z elementami specjalnego typu:

sum(S): zwraca sumę wszystkich elementów S dla pewnej definicji "sumy". Na przykład nad liczbami całkowitymi lub rzeczywistymi może być zdefiniowany jako .fold(0, add, S)
collapse(S): dany zestaw zestawów, zwróć unię. Na przykład collapse({{1}, {2, 3}}) == {1, 2, 3}. Można uznać za rodzaj sum.
flatten(S): dany zestaw składający się z zestawów i elementów niepodzielnych (elementów, które nie są zestawami), zwraca zestaw, którego elementy są niepodzielnymi elementami oryginalnego zestawu najwyższego poziomu lub elementami zestawów, które zawiera. Innymi słowy, usuń poziom zagnieżdżenia – jak, collapse,ale zezwalaj na atomy. Można to zrobić jednorazowo lub rekursywnie spłaszczając, aby uzyskać zestaw tylko elementów atomowych. Na przykład flatten({1, {2, 3}}) == {1, 2, 3}.
nearest(S,x): zwraca element S, który jest najbliższy wartości x (według jakiejś metryki ).
min(S), : zwraca minimalny/maksymalny element S .max(S)

Realizacje

Zestawy mogą być implementowane przy użyciu różnych struktur danych , które zapewniają różne kompromisy czasowe i przestrzenne dla różnych operacji. Niektóre implementacje mają na celu poprawę wydajności bardzo wyspecjalizowanych operacji, takich jak nearestlub union. Implementacje opisane jako „ogólnego użytku” zazwyczaj starają się optymalizować element_of, addoraz deleteoperacje. Prostą implementacją jest użycie list , ignorując kolejność elementów i uważając, aby uniknąć powtarzających się wartości. Jest to proste, ale nieefektywne, ponieważ operacje takie jak przynależność do zestawu lub usuwanie elementów to O ( n ), ponieważ wymagają one skanowania całej listy. Zestawy są często implementowane przy użyciu bardziej wydajnych struktur danych, w szczególności różnych odmian drzew , prób lub tablic mieszających .

Ponieważ zbiory można interpretować jako rodzaj mapy (przez funkcję indykatora), zbiory są zwykle implementowane w taki sam sposób jak mapy (częściowe) ( tablice asocjacyjne ) – w tym przypadku, gdy wartość każdej pary klucz-wartość ma typ jednostki lub wartość wskaźnikowa (np. 1) – mianowicie samobalansujące drzewo binarne wyszukiwania dla posortowanych zbiorów (które ma O(log n) dla większości operacji) lub tablica haszująca dla nieposortowanych zbiorów (która ma O(1) średni przypadek, ale O(n) najgorszy przypadek, dla większości operacji). Posortowana liniowa tablica mieszająca może służyć do zapewnienia deterministycznie uporządkowanych zestawów.

Co więcej, w językach, które obsługują mapy, ale nie zestawy, zestawy można zaimplementować jako mapy. Na przykład popularnym idiomem programistycznym w Perlu, który konwertuje tablicę na hash, której wartości są wartością wartowniczą 1, do użycia jako zestaw, to:

my %elements = map { $_ => 1 } @elements;

Inne popularne metody to tablice . W szczególnym podzbiorze liczby całkowite 1 .. n może być skutecznie zaimplementowane w postaci n -bitowych tablica bitów , które także obsługuje bardzo wydajnego działania związków i przecięcia. Mapa Blooma implementuje zestaw probabilistycznie, używając bardzo zwartej reprezentacji, ale ryzykując małą szansę fałszywych trafień w zapytaniach.

Wartość logiczna zestaw działań może być realizowana w warunkach bardziej elementarnych operacji ( pop, cleari add), lecz wyspecjalizowane algorytmy mogą dawać niższy asymptotyczne granic czasowych. Jeśli zbiory są zaimplementowane jako posortowane listy, naiwny algorytm for zajmie czas proporcjonalny do długości m z S razy długość n z T ; natomiast wariant algorytmu scalania list wykona zadanie w czasie proporcjonalnym do m + n . Ponadto istnieją wyspecjalizowane struktury danych (takie jak union-find data structure ), które są zoptymalizowane pod kątem jednej lub więcej z tych operacji kosztem innych. union(S,T)

Wsparcie językowe

Jednym z najwcześniejszych języków obsługujących zestawy był Pascal ; wiele języków teraz go zawiera, czy to w języku podstawowym, czy w standardowej bibliotece .

W C ++ , Template Library Standardowy (STL) zapewnia setklasę szablonu, który jest zazwyczaj realizowane za pomocą drzewa przeszukiwania binarnego (np drzewo czerwono-czarne ); STL SGI dostarcza również hash_setklasę szablonu, która implementuje zestaw za pomocą tablicy mieszającej. C++11 posiada wsparcie dla unordered_setklasy szablonu, która jest zaimplementowana za pomocą tablicy mieszającej. W zestawach same elementy są kluczami, w przeciwieństwie do kontenerów sekwencjonowanych, w których dostęp do elementów odbywa się za pomocą ich (względnej lub bezwzględnej) pozycji. Elementy zestawu muszą mieć ściśle słabą kolejność.
Java oferuje Set interfejs do obsługi zestawów ( HashSetklasa implementująca to za pomocą tablicy mieszającej) oraz SortedSetpodinterfejs do obsługi posortowanych zestawów ( TreeSetklasa implementująca to za pomocą drzewa wyszukiwania binarnego).
Jabłko „s Fundacja ramy (część kakao ) zapewnia Objective-C klasy NSSet, NSMutableSet, NSCountedSet, NSOrderedSet, i NSMutableOrderedSet. W CoreFoundation API zapewnić CFSET i CFMutableSet rodzaju do stosowania w C .
Python ma wbudowane seti frozensettypy od wersji 2.4, a od wersji 3.0 i 2.7 obsługuje niepuste literały zestawów przy użyciu składni z nawiasami klamrowymi, np.: {x, y, z}; puste zestawy muszą być tworzone za pomocą set(), ponieważ Python używa {}do reprezentowania pustego słownika.
.NET Framework zapewnia rodzajowe HashSeti SortedSetklas, które implementują rodzajowy ISetinterfejs.
Biblioteka klas Smalltalk zawiera Seti IdentitySet, używając odpowiednio równości i tożsamości do testu włączenia. Wiele dialektów zapewnić wariacje na sprężone składowania ( NumberSet, CharacterSet), dla zamawiającego ( OrderedSet, SortedSetetc.) lub dla słabych referencji ( WeakIdentitySet).
Rubin średnia biblioteka jest zawiera setmoduł, który zawiera Seti SortedSetklasy implementujące zestawów z tabel mieszania, ten ostatni umożliwiający iteracji w uporządkowanej kolejności.
OCaml standardowa biblioteka „s zawiera Setmoduł, który implementuje funkcjonalną strukturę zestaw danych za pomocą binarne drzewo poszukiwań.
GHC realizacja Haskell zapewnia Data.Setmoduł, który implementuje niezmienne zestawy używając binarne drzewo poszukiwań.
Pakiet Tcl Tcllib zawiera moduł zestawu, który implementuje strukturę danych zestawu opartą na listach TCL.
Swift biblioteka standardowa zawiera Settyp, ponieważ Swift 1.2.
JavaScript wprowadzony Setjako standardowy obiekt wbudowany w standardzie ECMAScript 2015.
Standardowa biblioteka Erlanga zawiera setsmoduł.
Clojure ma dosłowną składnię dla zestawów mieszanych, a także implementuje posortowane zestawy.
LabVIEW posiada natywną obsługę zestawów od wersji 2019.

Jak zauważono w poprzedniej sekcji, w językach, które nie obsługują bezpośrednio zestawów, ale obsługują tablice asocjacyjne , zestawy można emulować za pomocą tablic asocjacyjnych, używając elementów jako kluczy i używając fikcyjnej wartości jako wartości, które są ignorowane.

Multiset

Uogólnienie pojęciem zestawu jest to, że z MultiSet lub worka , który jest podobny do odbiornika, ale umożliwia wielokrotnym ( „równości”) wartości (duplikaty). Jest to używane w dwóch różnych znaczeniach: albo równe wartości są uważane za identyczne i są po prostu liczone, albo równe wartości są uważane za równoważne i są przechowywane jako odrębne elementy. Na przykład mając listę osób (według nazwiska) i wieku (w latach), można by skonstruować multizestaw wieków, który po prostu zlicza liczbę osób w danym wieku. Alternatywnie można skonstruować multizbiór osób, w którym dwie osoby są uważane za równoważne, jeśli ich wiek jest taki sam (ale mogą być różnymi osobami i mieć różne imiona), w którym to przypadku każda para (imię, wiek) musi być zapisana i wybierając w danym wieku daje wszystkim ludziom w danym wieku.

Formalnie możliwe jest, aby obiekty w informatyce były uważane za „równe” w pewnej relacji równoważności, ale nadal odrębne w innej relacji. Niektóre typy implementacji wielozestawowych będą przechowywać różne równe obiekty jako oddzielne elementy w strukturze danych; podczas gdy inni zwijają go do jednej wersji (pierwszej napotkanej) i zachowają dodatnią liczbę całkowitą krotności elementu.

Podobnie jak w przypadku zestawów, zestawy wielokrotne można naturalnie zaimplementować za pomocą tablicy mieszającej lub drzew, które dają różne charakterystyki wydajności.

Zbiór wszystkich toreb nad typem T jest określony wyrażeniem torebka T. Jeśli przez multiset uważa się równe pozycje za identyczne i po prostu je liczy, to multiset może być interpretowany jako funkcja od dziedziny wejściowej do nieujemnych liczb całkowitych ( naturalne liczb ), uogólniając identyfikację zbioru z jego funkcją wskaźnikową. W niektórych przypadkach multiset w tym sensie może być uogólniony, aby umożliwić wartości ujemne, tak jak w Pythonie.

Standardowa biblioteka szablonów C++ implementuje zarówno posortowane, jak i nieposortowane zestawy wielokrotne. Udostępnia multisetklasę dla posortowanego zbioru multiset, jako rodzaj kontenera asocjacyjnego , który implementuje ten multiset za pomocą samobalansującego binarnego drzewa wyszukiwania . Dostarcza unordered_multisetklasę dla unsorted multiset, jako rodzaj nieuporządkowanych kontenerów asocjacyjnych , które implementują ten multiset za pomocą tablicy mieszającej . Niesortowany multiset jest standardem od C++11 ; poprzednio SGI dostarcza hash_multisetklasę, która została skopiowana i ostatecznie ustandaryzowana.
W przypadku Java , biblioteki innych firm zapewniają funkcjonalność wielu zestawów:
- Apache Commons kolekcje zapewnia łatwy Bagi SortedBaginterfejsy z realizacji zajęć jak HashBagi TreeBag.
- Google Guava udostępnia Multisetinterfejs z implementacją klas takich jak HashMultiseti TreeMultiset.
Apple udostępnia NSCountedSetklasę jako część Cocoa , CFBaga CFMutableBagtypy i jako część CoreFoundation .
Standardowa biblioteka Pythona zawiera collections.Counter, która jest podobna do multisetu.
Smalltalk zawiera Bagklasę, która może być skonkretyzowana w celu użycia tożsamości lub równości jako predykatu dla testu włączenia.

Tam, gdzie wielozestawowa struktura danych nie jest dostępna, obejściem jest użycie zwykłego zestawu, ale zastąpienie predykatu równości jego elementów, aby zawsze zwracać „nie równe” dla różnych obiektów (jednak takie nadal nie będą w stanie przechowywać wielu wystąpień tego samego obiektu) lub użyj tablicy asocjacyjnej mapującej wartości na ich wielokrotności liczb całkowitych (nie będzie to w ogóle w stanie odróżnić równych elementów).

Typowe operacje na workach:

contains(B, x): sprawdza, czy element x jest obecny (co najmniej raz) w torbie B
is_sub_bag(B₁, B₂): sprawdza, czy każdy element w torbie B ₁ występuje w B ₁ nie częściej niż w torbie B ₂ ; czasami oznaczane jako B ₁ ⊑ B ₂ .
count(B, x): zwraca ile razy element x wystąpił w torbie B ; czasami oznaczane jako B # x .
scaled_by(B, n): podana liczba naturalna n , zwraca worek, który zawiera te same elementy co worek B , z tym wyjątkiem, że każdy element, który występuje m razy w B występuje n * m razy w wynikowym woreczku; czasami określane jako n ⊗ B .
union(B₁, B₂): zwraca worek zawierający tylko te wartości, które występują w torbie B ₁ lub torbie B ₂ , z wyjątkiem tego, że liczba wystąpień wartości x w otrzymanym torbie jest równa ( B ₁ # x) + ( B ₂ # x); czasami oznaczane jako B ₁ ⊎ B ₂ .

Wielozbiory w SQL

W relacyjnych bazach danych tabela może być zbiorem (matematycznym) lub wielozbiorem, w zależności od obecności ograniczeń jedności w niektórych kolumnach (co zamienia ją w klucz kandydujący ).

SQL pozwala na wybór wierszy z tabeli relacyjnej: ta operacja generalnie da multiset, chyba że słowo kluczowe DISTINCTjest używane do wymuszenia, aby wszystkie wiersze były różne, lub wybór zawiera klucz główny (lub kandydujący).

W ANSI SQLMULTISET kluczowe mogą być wykorzystane do przekształcenia podkwerenda do ekspresji kolekcji:

SELECT expression1, expression2... FROM table_name...

jest ogólnym wyborem, który może być użyty jako wyrażenie podzapytania innego bardziej ogólnego zapytania, podczas gdy

MULTISET(SELECT expression1, expression2... FROM table_name...)

przekształca podzapytanie w wyrażenie kolekcji, którego można użyć w innym zapytaniu lub w przypisaniu do kolumny o odpowiednim typie kolekcji.

Languages

In other projects