Udostępnij za pośrednictwem

Typy kolekcji języka F#

  • Artykuł

Przeglądając ten temat, możesz określić, który typ kolekcji języka F# najlepiej odpowiada określonej potrzebie. Te typy kolekcji różnią się od typów kolekcji na platformie .NET, takich jak te w System.Collections.Generic przestrzeni nazw, ponieważ typy kolekcji języka F# są projektowane z perspektywy programowania funkcjonalnego, a nie perspektywy obiektowej. Mówiąc dokładniej, tylko kolekcja tablic zawiera elementy modyfikowalne. W związku z tym podczas modyfikowania kolekcji należy utworzyć wystąpienie zmodyfikowanej kolekcji zamiast zmieniać oryginalną kolekcję.

Typy kolekcji różnią się również typem struktury danych, w której są przechowywane obiekty. Struktury danych, takie jak tabele skrótów, listy połączone i tablice, mają różne właściwości wydajności i inny zestaw dostępnych operacji.

Tabela typów kolekcji

W poniższej tabeli przedstawiono typy kolekcji języka F#.

Type Opis Linki powiązane
Lista Uporządkowana, niezmienna seria elementów tego samego typu. Zaimplementowano jako połączoną listę. Listy

Moduł listy
Tablica Niezmienna kolekcja kolejnych elementów danych o stałym rozmiarze, opartym na zerowym rozmiarze, które są tego samego typu. Tablice

Moduł tablicy

Moduł Array2D

Moduł Array3D
Seq Logiczna seria elementów, które są jednym typem. Sekwencje są szczególnie przydatne, gdy masz dużą, uporządkowaną kolekcję danych, ale niekoniecznie należy oczekiwać użycia wszystkich elementów. Poszczególne elementy sekwencji są obliczane tylko zgodnie z wymaganiami, więc sekwencja może działać lepiej niż lista, jeśli nie są używane wszystkie elementy. Sekwencje są reprezentowane przez seq<'T> typ, który jest aliasem dla elementu IEnumerable<T>. W związku z tym każdy typ programu .NET Framework, który implementuje System.Collections.Generic.IEnumerable<'T> , może być używany jako sekwencja. Sekwencje

Moduł seq
Mapa Niezmienny słownik elementów. Dostęp do elementów jest uzyskiwany za pomocą klucza. Moduł mapy
Zestaw Niezmienny zestaw oparty na drzewach binarnych, gdzie porównanie jest funkcją porównywania strukturalnego języka F#, która potencjalnie używa implementacji interfejsu System.IComparable dla wartości kluczy. Ustawianie modułu

Tabela funkcji

Ta sekcja porównuje funkcje, które są dostępne w typach kolekcji języka F#. Podana jest złożoność obliczeniowa funkcji, gdzie N jest rozmiarem pierwszej kolekcji, a M jest rozmiarem drugiej kolekcji, jeśli istnieje. Kreska (-) wskazuje, że ta funkcja nie jest dostępna w kolekcji. Ponieważ sekwencje są obliczane z opóźnieniem, funkcja taka jak Seq.distinct może być O(1), ponieważ zwraca natychmiast, chociaż nadal wpływa na wydajność sekwencji podczas wyliczania.

Function Tablica List Sequence Mapowanie Zestaw opis
append O(N) O(N) O(N) - - Zwraca nową kolekcję zawierającą elementy pierwszej kolekcji, a następnie elementy drugiej kolekcji.
add - - - O(log(N)) O(log(N)) Zwraca nową kolekcję z dodanym elementem.
Średnia O(N) O(N) O(N) - - Zwraca średnią elementów w kolekcji.
averageBy O(N) O(N) O(N) - - Zwraca średnią wyników podanej funkcji zastosowanej do każdego elementu.
blit O(N) - - - - Kopiuje sekcję tablicy.
cache - - O(N) - - Oblicza i przechowuje elementy sekwencji.
rzutowanie - - O(N) - - Konwertuje elementy na określony typ.
Wybierz O(N) O(N) O(N) - - Stosuje daną funkcję f do każdego elementu x listy. Zwraca listę zawierającą wyniki dla każdego elementu, w którym funkcja zwraca wartość Some(f(x)).
Zbierać O(N) O(N) O(N) - - Stosuje daną funkcję do każdego elementu kolekcji, łączy wszystkie wyniki i zwraca połączoną listę.
compareWith - - O(N) - - Porównuje dwie sekwencje przy użyciu danej funkcji porównania, element by, element.
concat O(N) O(N) O(N) - - Łączy podane wyliczenia-of-enumerations jako pojedyncze połączone wyliczenie.
zawiera - - - - O(log(N)) Zwraca wartość true, jeśli zestaw zawiera określony element.
Containskey - - - O(log(N)) - Sprawdza, czy element znajduje się w domenie mapy.
count - - - - O(N) Zwraca liczbę elementów w zestawie.
countBy - - O(N) - - Stosuje funkcję generowania kluczy do każdego elementu sekwencji i zwraca sekwencję, która zwraca unikatowe klucze i ich liczbę wystąpień w oryginalnej sekwencji.
kopiowanie O(N) - O(N) - - Kopiuje kolekcję.
create O(N) - - - - Tworzy tablicę całych elementów, które są początkowo daną wartością.
opóźnienie - - O(1) - - Zwraca sekwencję utworzoną na podstawie danej opóźnionej specyfikacji sekwencji.
różnica - - - - O(M*log(N)) Zwraca nowy zestaw z elementami drugiego zestawu usuniętym z pierwszego zestawu.
distinct O(1)* Zwraca sekwencję, która nie zawiera zduplikowanych wpisów zgodnie z ogólnymi porównaniami skrótów i równości w pozycjach. Jeśli element występuje wiele razy w sekwencji, późniejsze wystąpienia zostaną odrzucone.
distinctBy O(1)* Zwraca sekwencję, która nie zawiera zduplikowanych wpisów zgodnie z ogólnymi porównaniami skrótów i równości dla kluczy zwracanych przez daną funkcję generowania kluczy. Jeśli element występuje wiele razy w sekwencji, późniejsze wystąpienia zostaną odrzucone.
empty O(1) O(1) O(1) O(1) O(1) Tworzy pustą kolekcję.
istnieje O(N) O(N) O(N) O(log(N)) O(log(N)) Sprawdza, czy dowolny element sekwencji spełnia dany predykat.
istnieje2 O(min(N,M)) - O(min(N,M)) Sprawdza, czy dowolna para odpowiednich elementów sekwencji wejściowych spełnia dany predykat.
fill O(N) Ustawia zakres elementów tablicy na daną wartość.
filtr O(N) O(N) O(N) O(N) O(N) Zwraca nową kolekcję zawierającą tylko elementy kolekcji, dla których dany predykat zwraca wartość true.
find O(N) O(N) O(N) O(log(N)) - Zwraca pierwszy element, dla którego dana funkcja zwraca wartość true. Zwraca wartość System.Collections.Generic.KeyNotFoundException , jeśli taki element nie istnieje.
Findindex O(N) O(N) O(N) - - Zwraca indeks pierwszego elementu w tablicy, który spełnia dany predykat. System.Collections.Generic.KeyNotFoundException Podnosi, jeśli żaden element nie spełnia predykatu.
findKey - - - O(log(N)) - Oblicza funkcję na każdym mapowaniu w kolekcji i zwraca klucz pierwszego mapowania, w którym funkcja zwraca wartość true. Jeśli taki element nie istnieje, ta funkcja zgłasza System.Collections.Generic.KeyNotFoundExceptionwartość .
Złożyć O(N) O(N) O(N) O(N) O(N) Stosuje funkcję do każdego elementu kolekcji, wątkując argument akumulacyjny za pomocą obliczeń. Jeśli funkcja input ma wartość f, a elementy są i0... iN, ta funkcja oblicza f (... (f s i0)...) Cala.
fold2 O(N) O(N) - - - Stosuje funkcję do odpowiednich elementów dwóch kolekcji, wątkowanie argumentu akumulatorowego za pomocą obliczeń. Kolekcje muszą mieć identyczne rozmiary. Jeśli funkcja input ma wartość f, a elementy są i0... iN i j0... jN, ta funkcja oblicza f (... (f s i0 j0)...) iN jN.
foldBack O(N) O(N) - O(N) O(N) Stosuje funkcję do każdego elementu kolekcji, wątkując argument akumulacyjny za pomocą obliczeń. Jeśli funkcja input ma wartość f, a elementy są i0... iN, ta funkcja oblicza f i0 (... (f iN s)).
foldBack2 O(N) O(N) - - - Stosuje funkcję do odpowiednich elementów dwóch kolekcji, wątkowanie argumentu akumulatorowego za pomocą obliczeń. Kolekcje muszą mieć identyczne rozmiary. Jeśli funkcja input ma wartość f, a elementy są i0... iN i j0... jN, ta funkcja oblicza f i0 j0 (... (f iN jN s)).
Forall O(N) O(N) O(N) O(N) O(N) Sprawdza, czy wszystkie elementy kolekcji spełniają dany predykat.
forall2 O(N) O(N) O(N) - - Sprawdza, czy wszystkie odpowiednie elementy kolekcji spełniają określony predykat parowania.
get /nth O(1) O(N) O(N) - - Zwraca element z kolekcji, biorąc pod uwagę jego indeks.
Głowy - O(1) O(1) - - Zwraca pierwszy element kolekcji.
init O(N) O(N) O(1) - - Tworzy kolekcję, biorąc pod uwagę wymiar i funkcję generatora, aby obliczyć elementy.
initInfinite - - O(1) - - Generuje sekwencję, która po iterated zwraca kolejne elementy przez wywołanie danej funkcji.
intersect - - - - O(log(N)*log(M)) Oblicza przecięcie dwóch zestawów.
intersectMany - - - - O(N1*N2...) Oblicza przecięcie sekwencji zestawów. Sekwencja nie może być pusta.
isEmpty O(1) O(1) O(1) O(1) - Zwraca wartość true , jeśli kolekcja jest pusta.
isProperSubset - - - - O(M*log(N)) Zwraca wartość true , jeśli wszystkie elementy pierwszego zestawu znajdują się w drugim zestawie, a co najmniej jeden element drugiego zestawu nie znajduje się w pierwszym zestawie.
isProperSuperset - - - - O(M*log(N)) Zwraca wartość true , jeśli wszystkie elementy drugiego zestawu znajdują się w pierwszym zestawie, a co najmniej jeden element pierwszego zestawu nie znajduje się w drugim zestawie.
isSubset - - - - O(M*log(N)) Zwraca wartość true , jeśli wszystkie elementy pierwszego zestawu znajdują się w drugim zestawie.
isSuperset - - - - O(M*log(N)) Zwraca wartość true , jeśli wszystkie elementy drugiego zestawu znajdują się w pierwszym zestawie.
Iter O(N) O(N) O(N) O(N) O(N) Stosuje daną funkcję do każdego elementu kolekcji.
iteri O(N) O(N) O(N) - - Stosuje daną funkcję do każdego elementu kolekcji. Liczba całkowita przekazana do funkcji wskazuje indeks elementu.
iteri2 O(N) O(N) - - - Stosuje daną funkcję do pary elementów, które są pobierane z pasujących indeksów w dwóch tablicach. Liczba całkowita przekazana do funkcji wskazuje indeks elementów. Dwie tablice muszą mieć taką samą długość.
iter2 O(N) O(N) O(N) - - Stosuje daną funkcję do pary elementów, które są pobierane z pasujących indeksów w dwóch tablicach. Dwie tablice muszą mieć taką samą długość.
ostatni O(1) O(N) O(N) - - Zwraca ostatni element w odpowiedniej kolekcji.
length O(1) O(N) O(N) - - Zwraca liczbę elementów w kolekcji.
map O(N) O(N) O(1) - - Tworzy kolekcję, której elementy są wynikami zastosowania danej funkcji do każdego elementu tablicy.
map2 O(N) O(N) O(1) - - Tworzy kolekcję, której elementy są wynikami zastosowania danej funkcji do odpowiednich elementów dwóch kolekcji w parze. Dwie tablice wejściowe muszą mieć taką samą długość.
map3 - O(N) - - - Tworzy kolekcję, której elementy są wynikami zastosowania danej funkcji do odpowiednich elementów trzech kolekcji jednocześnie.
Mapi O(N) O(N) O(N) - - Tworzy tablicę, której elementy są wynikami zastosowania danej funkcji do każdego elementu tablicy. Indeks liczb całkowitych przekazany do funkcji wskazuje indeks przekształcanego elementu.
mapi2 O(N) O(N) - - - Tworzy kolekcję, której elementy są wynikami zastosowania danej funkcji do odpowiadających im elementów dwóch kolekcji, przekazując również indeks elementów. Dwie tablice wejściowe muszą mieć taką samą długość.
max O(N) O(N) O(N) - - Zwraca największy element w kolekcji w porównaniu z użyciem operatora max .
maxBy O(N) O(N) O(N) - - Zwraca największy element w kolekcji w porównaniu z użyciem wartości maksymalnej w wyniku funkcji.
maxElement - - - - O(log(N)) Zwraca największy element w zestawie zgodnie z kolejnością używaną dla zestawu.
min O(N) O(N) O(N) - - Zwraca najmniejszy element w kolekcji w porównaniu przy użyciu operatora min .
minBy O(N) O(N) O(N) - - Zwraca najmniejszy element w kolekcji, w porównaniu przy użyciu operatora min w wyniku funkcji.
minElement - - - - O(log(N)) Zwraca najniższy element w zestawie zgodnie z kolejnością używaną dla zestawu.
ofArray - O(N) O(1) O(N) O(N) Tworzy kolekcję zawierającą te same elementy co dana tablica.
ofList O(N) - O(1) O(N) O(N) Tworzy kolekcję zawierającą te same elementy co dana lista.
ofSeq O(N) O(N) - O(N) O(N) Tworzy kolekcję zawierającą te same elementy co dana sekwencja.
Parowania - - O(N) - - Zwraca sekwencję każdego elementu w sekwencji wejściowej i jego poprzednika z wyjątkiem pierwszego elementu, który jest zwracany tylko jako poprzednik drugiego elementu.
partycji O(N) O(N) - O(N) O(N) Dzieli kolekcję na dwie kolekcje. Pierwsza kolekcja zawiera elementy, dla których dany predykat zwraca truewartość , a druga kolekcja zawiera elementy, dla których dany predykat zwraca wartość false.
permute O(N) O(N) - - - Zwraca tablicę ze wszystkimi elementami permutowanych zgodnie z określoną permutacją.
Wybrać O(N) O(N) O(N) O(log(N)) - Stosuje daną funkcję do kolejnych elementów, zwracając pierwszy wynik, w którym funkcja zwraca część. Jeśli funkcja nigdy nie zwraca wartości Niektóre, System.Collections.Generic.KeyNotFoundException zostanie podniesiona.
readonly - - O(N) - - Tworzy obiekt sekwencji, który deleguje do danego obiektu sekwencji. Ta operacja gwarantuje, że rzutowanie typu nie może ponownie odnaleźć i zmutować oryginalnej sekwencji. Jeśli na przykład dana tablica, zwrócona sekwencja zwróci elementy tablicy, ale nie można rzutować zwróconego obiektu sekwencji na tablicę.
Zmniejszyć O(N) O(N) O(N) - - Stosuje funkcję do każdego elementu kolekcji, wątkując argument akumulacyjny za pomocą obliczeń. Ta funkcja rozpoczyna się od zastosowania funkcji do dwóch pierwszych elementów, przekazuje ten wynik do funkcji wraz z trzecim elementem itd. Funkcja zwraca wynik końcowy.
reduceBack O(N) O(N) - - - Stosuje funkcję do każdego elementu kolekcji, wątkując argument akumulacyjny za pomocą obliczeń. Jeśli funkcja input ma wartość f, a elementy są i0... iN, ta funkcja oblicza f i0 (... (f iN-1 iN)).
remove - - - O(log(N)) O(log(N)) Usuwa element z domeny mapy. Nie jest zgłaszany wyjątek, jeśli element nie jest obecny.
Replikować - O(N) - - - Tworzy listę określonej długości z każdym elementem ustawionym na daną wartość.
Rev O(N) O(N) - - - Zwraca nową listę z elementami w odwrotnej kolejności.
skanowanie O(N) O(N) O(N) - - Stosuje funkcję do każdego elementu kolekcji, wątkując argument akumulacyjny za pomocą obliczeń. Ta operacja stosuje funkcję do drugiego argumentu i pierwszego elementu listy. Następnie operacja przekazuje ten wynik do funkcji wraz z drugim elementem i tak dalej. Na koniec operacja zwraca listę wyników pośrednich i końcowy wynik.
scanBack O(N) O(N) - - - Przypomina operację foldBack, ale zwraca wyniki pośrednie i końcowe.
Singleton - - O(1) - O(1) Zwraca sekwencję, która zwraca tylko jeden element.
set O(1) - - - - Ustawia element tablicy na określoną wartość.
skip - - O(N) - - Zwraca sekwencję, która pomija N elementów podstawowej sekwencji, a następnie zwraca pozostałe elementy sekwencji.
Skipwhile - - O(N) - - Zwraca sekwencję, która po iterated pomija elementy podstawowej sekwencji, gdy dany predykat zwraca true , a następnie zwraca pozostałe elementy sekwencji.
sort Średnia O(N*log(N))

O(N^2) najgorszy przypadek		 O(N*log(N)) O(N*log(N)) - - Sortuje kolekcję według wartości elementu. Elementy są porównywane przy użyciu porównania.
sortBy Średnia O(N*log(N))

O(N^2) najgorszy przypadek		 O(N*log(N)) O(N*log(N)) - - Sortuje daną listę przy użyciu kluczy, które zapewnia dana projekcja. Klucze są porównywane przy użyciu porównania.
sortInPlace Średnia O(N*log(N))

O(N^2) najgorszy przypadek		 - - - - Sortuje elementy tablicy, modyfikując ją na miejscu i używając danej funkcji porównania. Elementy są porównywane przy użyciu porównania.
sortInPlaceBy Średnia O(N*log(N))

O(N^2) najgorszy przypadek		 - - - - Sortuje elementy tablicy, modyfikując ją na miejscu i używając danej projekcji dla kluczy. Elementy są porównywane przy użyciu porównania.
sortInPlaceWith Średnia O(N*log(N))

O(N^2) najgorszy przypadek		 - - - - Sortuje elementy tablicy, modyfikując ją na miejscu i używając danej funkcji porównania jako kolejności.
sortWith Średnia O(N*log(N))

O(N^2) najgorszy przypadek		 O(N*log(N)) - - - Sortuje elementy kolekcji przy użyciu danej funkcji porównania jako kolejności i zwraca nową kolekcję.
sub O(N) - - - - Tworzy tablicę zawierającą podane podwoje określone przez początkowy indeks i długość.
Suma O(N) O(N) O(N) - - Zwraca sumę elementów w kolekcji.
sumBy O(N) O(N) O(N) - - Zwraca sumę wyników generowanych przez zastosowanie funkcji do każdego elementu kolekcji.
Ogon - O(1) - - - Zwraca listę bez jej pierwszego elementu.
take - - O(N) - - Zwraca elementy sekwencji do określonej liczby.
Takewhile - - O(1) - - Zwraca sekwencję, która po iterated zwraca elementy bazowej sekwencji, gdy dany predykat zwraca true , a następnie nie zwraca więcej elementów.
Toarray - O(N) O(N) O(N) O(N) Tworzy tablicę z danej kolekcji.
Tolist O(N) - O(N) O(N) O(N) Tworzy listę z danej kolekcji.
toSeq O(1) O(1) - O(1) O(1) Tworzy sekwencję z danej kolekcji.
truncate - - O(1) - - Zwraca sekwencję, która po wyliczenie zwraca nie więcej niż N elementów.
tryFind O(N) O(N) O(N) O(log(N)) - Wyszukuje element spełniający określony predykat.
tryFindIndex O(N) O(N) O(N) - - Wyszukuje pierwszy element spełniający określony predykat i zwraca indeks pasującego elementu lub None jeśli taki element nie istnieje.
tryFindKey - - - O(log(N)) - Zwraca klucz pierwszego mapowania w kolekcji, który spełnia dany predykat lub zwraca None wartość, jeśli taki element nie istnieje.
tryPick O(N) O(N) O(N) O(log(N)) - Stosuje daną funkcję do kolejnych elementów, zwracając pierwszy wynik, w którym funkcja zwraca Some pewną wartość. Jeśli taki element nie istnieje, operacja zwraca wartość None.
Rozwijać - - O(N) - - Zwraca sekwencję zawierającą elementy generowane przez dane obliczenia.
unia - - - - O(M*log(N)) Oblicza związek dwóch zestawów.
unionMany - - - - O(N1*N2...) Oblicza związek sekwencji zestawów.
Rozpakuj O(N) O(N) O(N) - - Dzieli listę par na dwie listy.
rozpakuj 3 O(N) O(N) O(N) - - Dzieli listę trójek na trzy listy.
Okna - - O(N) - - Zwraca sekwencję, która daje przesuwane okna zawierające elementy, które są pobierane z sekwencji danych wejściowych. Każde okno jest zwracane jako nowa tablica.
Zip O(N) O(N) O(N) - - Łączy dwie kolekcje w listę par. Dwie listy muszą mieć równe długości.
zip3 O(N) O(N) O(N) - - Łączy trzy kolekcje w listę potrójnych. Listy muszą mieć równe długości.

Zobacz też