Partage via


Types de collection F#

En consultant cette rubrique, vous pouvez déterminer quel type de collection F# convient le mieux à un besoin particulier. Ces types de collection diffèrent des types de collection dans .NET, tels que ceux de l’espace de noms System.Collections.Generic, dans la mesure où les types de collection F# sont conçus du point de vue de la programmation fonctionnelle plutôt que du point de vue de l’objet. Plus précisément, seule la collection d'arrays contient des éléments mutables. Par conséquent, lorsque vous modifiez une collection, vous créez une instance de la collection modifiée au lieu de modifier la collection d’origine.

Les types de collection diffèrent également dans le type de structure de données dans lequel les objets sont stockés. Les structures de données telles que les tables de hachage, les listes liées et les tableaux ont des caractéristiques de performances différentes et un ensemble différent d’opérations disponibles.

Table des types de collection

Le tableau suivant montre les types de collection F#.

Type Description Liens connexes
Liste Série ordonnée et immuable d’éléments du même type. Implémentée en tant que liste liée. Listes

Module de liste
Array Collection mutable de taille fixe, de base zéro, d’éléments de données consécutifs qui sont tous du même type. Arrays

Module Array

Module Array2D

Module Array3D
seq Série logique d’éléments qui sont tous d’un type. Les séquences sont particulièrement utiles lorsque vous disposez d’une collection de données volumineuse et ordonnée, mais n’attendez pas nécessairement à utiliser tous les éléments. Les éléments de séquence individuels sont calculés uniquement en fonction des besoins, de sorte qu’une séquence peut s’effectuer mieux qu’une liste si tous les éléments ne sont pas utilisés. Les séquences sont représentées par le type seq<'T>, qui est un alias pour IEnumerable<T>. Par conséquent, tout type .NET Framework qui implémente System.Collections.Generic.IEnumerable<'T> peut être utilisé comme séquence. Séquences

Module Seq
Mapper Dictionnaire immuable d’éléments. Les éléments sont accessibles par clé. Module Cartographique
Définir Ensemble immuable basé sur des arborescences binaires, où la comparaison est la fonction de comparaison structurelle F#, qui utilise potentiellement les implémentations de l’interface System.IComparable sur les valeurs de clé. Configurer le module

Table des fonctions

Cette section compare les fonctions disponibles sur les types de collection F#. La complexité de calcul de la fonction est donnée, où N est la taille de la première collection, et M est la taille de la deuxième collection, le cas échéant. Un tiret (-) indique que cette fonction n’est pas disponible sur la collection. Étant donné que les séquences sont évaluées lentement, une fonction comme Seq.distinct peut correspondre à O(1) car elle est immédiatement retournée, même si elle affecte toujours les performances de la séquence lorsqu’elle est énumérée.

Fonction Array Liste Séquence Carte Définissez Description
append O(N) O(N) O(N) - - Retourne une nouvelle collection qui contient les éléments de la première collection suivie d’éléments de la deuxième collection.
ajouter - - - O(log(N)) O(log(N)) Retourne une nouvelle collection avec l’élément ajouté.
moyenne O(N) O(N) O(N) - - Retourne la moyenne des éléments de la collection.
averageBy O(N) O(N) O(N) - - Retourne la moyenne des résultats de la fonction fournie appliquée à chaque élément.
blit O(N) - - - - Copie une section d’un tableau.
cache - - O(N) - - Calcule et stocke les éléments d’une séquence.
Caster - - O(N) - - Convertit les éléments en type spécifié.
choose O(N) O(N) O(N) - - Applique la fonction donnée f à chaque élément x de la liste. Retourne la liste qui contient les résultats de chaque élément où la fonction retourne Some(f(x)).
collect O(N) O(N) O(N) - - Applique la fonction donnée à chaque élément de la collection, concatène tous les résultats et retourne la liste combinée.
compareWith - - O(N) - - Compare deux séquences à l’aide de la fonction de comparaison donnée, élément par élément.
concat O(N) O(N) O(N) - - Combine l’énumération des énumérations donnée en tant qu’énumération concaténée unique.
contient - - - - O(log(N)) Retourne vrai si l’ensemble contient l’élément spécifié.
containsKey - - - O(log(N)) - Teste si un élément se trouve dans le domaine d’une carte.
count - - - - O(N) Retourne le nombre d’éléments dans l’ensemble.
countBy - - O(N) - - Applique une fonction de génération de clés à chaque élément d’une séquence et retourne une séquence qui génère des clés uniques et leur nombre d’occurrences dans la séquence d’origine.
copy O(N) - O(N) - - Copie la collection.
create O(N) - - - - Crée un tableau d’éléments entiers qui sont tous initialement la valeur donnée.
delay - - O(1) - - Retourne une séquence créée à partir de la spécification différée donnée d’une séquence.
différence - - - - O(M*log(N)) Retourne un nouvel ensemble avec les éléments du deuxième ensemble retirés du premier ensemble.
distinct O(1)* Retourne une séquence qui ne contient aucune entrée en double en fonction des comparaisons de hachage et d’égalité génériques sur les entrées. Si un élément se produit plusieurs fois dans la séquence, les occurrences ultérieures sont ignorées.
distinctBy O(1)* Retourne une séquence qui ne contient aucune entrée en double en fonction des comparaisons de hachage et d’égalité génériques sur les clés retournées par la fonction de génération de clés donnée. Si un élément se produit plusieurs fois dans la séquence, les occurrences ultérieures sont ignorées.
empty O(1) O(1) O(1) O(1) O(1) Crée une collection vide.
Existe O(N) O(N) O(N) O(log(N)) O(log(N)) Teste si un élément de la séquence satisfait au prédicat donné.
exists2 O(min(N,M)) - O(min(N,M)) Teste si une paire d’éléments correspondants des séquences d’entrée satisfait le prédicat donné.
fill O(N) Définit une plage d’éléments du tableau sur la valeur donnée.
filter O(N) O(N) O(N) O(N) O(N) Retourne une nouvelle collection contenant uniquement les éléments de la collection pour lesquels la condition spécifiée retourne true.
find O(N) O(N) O(N) O(log(N)) - Retourne le premier élément pour lequel la fonction donnée retourne true. Retourne System.Collections.Generic.KeyNotFoundException si aucun élément de ce type n’existe.
findIndex O(N) O(N) O(N) - - Retourne l’index du premier élément du tableau qui satisfait le prédicat donné. Déclenche System.Collections.Generic.KeyNotFoundException si aucun élément ne satisfait le prédicat.
findKey - - - O(log(N)) - Évalue la fonction sur chaque mappage dans la collection et retourne la clé du premier mappage où la fonction retourne true. Si aucun élément de ce type n’existe, cette fonction déclenche System.Collections.Generic.KeyNotFoundException.
fold O(N) O(N) O(N) O(N) O(N) Applique une fonction à chaque élément de la collection, en passant un argument accumulateur à travers le calcul. Si la fonction d'entrée est f et que les éléments sont i0...iN, cette fonction calcule f (... (f s i0)...) iN.
fold2 O(N) O(N) - - - Applique une fonction aux éléments correspondants de deux collections, faisant passer un argument d’accumulation au cours du calcul. Les collections doivent avoir des tailles identiques. Si la fonction d’entrée est f et que les éléments sont i0... iN et j0... jN, cette fonction calcule f (... (f s i0 j0)...) iN jN.
foldBack O(N) O(N) - O(N) O(N) Applique une fonction à chaque élément de la collection, par le threading d’un argument d’accumulateur dans le calcul. Si la fonction d’entrée est f et que les éléments sont i0... iN, cette fonction calcule f i0 (... (f iN s)).
foldBack2 O(N) O(N) - - - Applique une fonction aux éléments correspondants de deux collections, en passant un argument d'accumulation à travers le calcul. Les collections doivent avoir des tailles identiques. Si la fonction d’entrée est f et que les éléments sont i0... iN et j0... jN, cette fonction calcule f i0 j0 (... (f iN jN s)).
forall O(N) O(N) O(N) O(N) O(N) Teste si tous les éléments de la collection répondent au prédicat donné.
forall2 O(N) O(N) O(N) - - Teste si tous les éléments correspondants de la collection répondent à la paire de prédicats donné.
get / nth O(1) O(N) O(N) - - Retourne un élément de la collection en fonction de son index.
head - O(1) O(1) - - Retourne le premier élément de la collection.
init O(N) O(N) O(1) - - Crée une collection en fonction de la dimension et d’une fonction de générateur pour calculer les éléments.
initInfinite - - O(1) - - Génère une séquence qui, lorsqu’elle est itérée, retourne des éléments successifs en appelant la fonction donnée.
intersection - - - - O(log(N)*log(M)) Calcule l’intersection de deux ensembles.
intersectMany - - - - O(N1*N2...) Calcule l’intersection d’une séquence d’ensembles. La séquence ne doit pas être vide.
isEmpty O(1) O(1) O(1) O(1) - Retourne true si la collection est vide.
isProperSubset - - - - O(M*log(N)) Retourne true si tous les éléments du premier jeu se trouvent dans le deuxième jeu et qu’au moins un élément du deuxième jeu n’est pas dans le premier jeu.
isProperSuperset - - - - O(M*log(N)) Retourne true si tous les éléments du deuxième jeu se trouvent dans le premier jeu et qu’au moins un élément du premier jeu n’est pas dans le deuxième jeu.
isSubset - - - - O(M*log(N)) Retourne true si tous les éléments du premier jeu se trouvent dans le deuxième jeu.
isSuperset - - - - O(M*log(N)) Retourne true si tous les éléments du deuxième jeu se trouvent dans le premier jeu.
iter O(N) O(N) O(N) O(N) O(N) Applique la fonction donnée à chaque élément de la collection.
iteri O(N) O(N) O(N) - - Applique la fonction donnée à chaque élément de la collection. L’entier passé à la fonction indique l’index de l’élément.
iteri2 O(N) O(N) - - - Applique la fonction donnée à une paire d’éléments dessinés à partir d’index correspondants dans deux tableaux. L’entier passé à la fonction indique l’index des éléments. Les deux tableaux doivent avoir la même longueur.
iter2 O(N) O(N) O(N) - - Applique la fonction donnée à une paire d’éléments dessinés à partir d’index correspondants dans deux tableaux. Les deux tableaux doivent avoir la même longueur.
Dernier O(1) O(N) O(N) - - Retourne le dernier élément de la collection applicable.
length O(1) O(N) O(N) - - Retourne le nombre d’éléments de la collection.
carte O(N) O(N) O(1) - - Génère une collection dont les éléments sont les résultats de l’application de la fonction donnée à chaque élément du tableau.
carte2 O(N) O(N) O(1) - - Génère une collection dont les éléments sont les résultats de l’application de la fonction donnée aux éléments correspondants des deux collections par paire. Les deux tableaux d’entrée doivent avoir la même longueur.
Carte3 - O(N) - - - Génère une collection dont les éléments sont les résultats de l’application de la fonction donnée aux éléments correspondants des trois collections simultanément.
mapi O(N) O(N) O(N) - - Génère un tableau dont les éléments sont les résultats de l’application de la fonction donnée à chaque élément du tableau. L’index entier passé à la fonction indique l’index de l’élément en cours de transformation.
mapi2 O(N) O(N) - - - Génère une collection dont les éléments sont les résultats de l’application de la fonction donnée aux éléments correspondants des deux collections, en passant également l’index des éléments. Les deux tableaux d’entrée doivent avoir la même longueur.
max O(N) O(N) O(N) - - Retourne le plus grand élément de la collection, comparé à l’aide de l’opérateur max.
maxBy O(N) O(N) O(N) - - Retourne le plus grand élément de la collection, comparé en utilisant max sur le résultat de la fonction.
maxElement - - - - O(log(N)) Retourne l'élément le plus grand de l'ensemble en fonction de l'ordre utilisé pour l'ensemble.
min O(N) O(N) O(N) - - Retourne l’élément le plus petit de la collection, comparé à l’aide de l’opérateur min.
minBy O(N) O(N) O(N) - - Retourne le plus petit élément de la collection, comparé en utilisant l'opérateur min sur le résultat de la fonction.
minElement - - - - O(log(N)) Retourne l’élément le plus bas dans l’ensemble en fonction de l’ordre utilisé pour l’ensemble.
ofArray - O(N) O(1) O(N) O(N) Crée une collection qui contient les mêmes éléments que le tableau donné.
ofList O(N) - O(1) O(N) O(N) Crée une collection qui contient les mêmes éléments que la liste donnée.
ofSeq O(N) O(N) - O(N) O(N) Crée une collection qui contient les mêmes éléments que la séquence donnée.
pairwise - - O(N) - - Retourne une séquence de chaque élément de la séquence d’entrée et de son prédécesseur, à l’exception du premier élément, qui est retourné uniquement comme prédécesseur du deuxième élément.
partition O(N) O(N) - O(N) O(N) Fractionne la collection en deux collections. La première collection contient les éléments pour lesquels le prédicat donné retourne true, et la deuxième collection contient les éléments pour lesquels le prédicat donné retourne false.
permute O(N) O(N) - - - Retourne un tableau avec tous les éléments permutés en fonction de la permutation spécifiée.
pick O(N) O(N) O(N) O(log(N)) - Applique la fonction donnée aux éléments successifs, en retournant le premier résultat où la fonction retourne Some. Si la fonction ne retourne jamais Some, System.Collections.Generic.KeyNotFoundException est déclenché.
choix aléatoire O(1) O(1) O(1) - - Retourne un élément aléatoire de la collection donnée.
randomChoiceBy O(1) O(1) O(1) - - Retourne un élément aléatoire de la collection donnée avec la fonction randomizer spécifiée.
randomChoiceWith O(1) O(1) O(1) - - Retourne un élément aléatoire de la collection donnée avec l’instance de Random spécifiée.
choix aléatoires O(nombre) O(nombre) O(nombre) - - Retourne une collection d’éléments aléatoires de la collection donnée, chaque élément peut être sélectionné plusieurs fois.
randomChoicesBy O(nombre) O(nombre) O(nombre) - - Retourne une collection d’éléments aléatoires de la collection donnée avec la fonction randomizer spécifiée, chaque élément peut être sélectionné plusieurs fois.
randomChoicesWith O(nombre) O(nombre) O(nombre) - - Retourne une collection d’éléments aléatoires de la collection donnée avec l’instance de Random spécifiée, chaque élément peut être sélectionné plusieurs fois.
échantillon aléatoire O(nombre) O(nombre) O(nombre) - - Retourne un échantillon aléatoire d’éléments de la collection donnée, chaque élément ne peut être sélectionné qu’une seule fois.
randomSampleBy O(nombre) O(nombre) O(nombre) - - Retourne un échantillon aléatoire d’éléments du colleciton donné avec la fonction randomizer spécifiée, chaque élément ne peut être sélectionné qu’une seule fois.
randomSampleWith O(nombre) O(nombre) O(nombre) - - Retourne un échantillon aléatoire d’éléments de la collection donnée avec l’instance de Random spécifiée, chaque élément ne peut être sélectionné qu’une seule fois.
randomShuffle O(N) O(N) O(N) - - Retourne une nouvelle collection mélangée dans un ordre aléatoire.
randomShuffleBy O(N) O(N) O(N) - - Retourne une nouvelle collection dans un ordre aléatoire en utilisant la fonction randomizer spécifiée.
randomShuffleWith O(N) O(N) O(N) - - Retourne une nouvelle collection dans un ordre aléatoire en utilisant l’instance Random spécifiée.
randomShuffleInPlace O(N) - - - - Trie le tableau d’entrée dans un ordre aléatoire en mutant le tableau sur place.
randomShuffleInPlaceBy O(N) - - - - Trie le tableau d’entrée dans un ordre aléatoire à l’aide de la fonction randomizer spécifiée en mutant le tableau sur place.
randomShuffleInPlaceWith O(N) - - - - Trie le tableau d’entrée dans un ordre aléatoire en utilisant l’instance de Random spécifiée, en le modifiant directement sur place.
readonly - - O(N) - - Crée un objet de séquence qui délègue à l’objet de séquence donné. Cette opération garantit qu’un cast de type ne peut pas redécouvrir et muter la séquence d’origine. Par exemple, si un tableau est donné, la séquence retournée retourne les éléments du tableau, mais vous ne pouvez pas convertir l’objet séquence retourné en tableau.
reduce O(N) O(N) O(N) - - Applique une fonction à chaque élément de la collection, par le threading d’un argument d’accumulateur dans le calcul. Cette fonction commence par appliquer la fonction aux deux premiers éléments, transmet ce résultat à la fonction avec le troisième élément, et ainsi de suite. La fonction retourne le résultat final.
reduceBack O(N) O(N) - - - Applique une fonction à chaque élément de la collection, utilisant un argument d'accumulation pendant le calcul. Si la fonction d’entrée est f et que les éléments sont i0... iN, cette fonction calcule f i0 (... (f iN-1 iN)).
remove - - - O(log(N)) O(log(N)) Supprime un élément du domaine de la carte. Aucune exception n’est levée si l’élément n’est pas présent.
répliquer - O(N) - - - Crée une liste d'une longueur spécifiée avec chaque élément défini à la valeur donnée.
rev O(N) O(N) - - - Retourne une nouvelle liste avec les éléments dans l’ordre inverse.
scan O(N) O(N) O(N) - - Applique une fonction à chaque élément de la collection, en transmettant un argument d’accumulation au travers du calcul. Cette opération applique la fonction au deuxième argument et au premier élément de la liste. L’opération transmet ensuite ce résultat à la fonction avec le deuxième élément, et ainsi de suite. Enfin, l’opération retourne la liste des résultats intermédiaires et le résultat final.
scanBack O(N) O(N) - - - Ressemble à l’opération foldBack, mais retourne les résultats intermédiaires et finaux.
singleton - - O(1) - O(1) Retourne une séquence qui ne génère qu’un seul élément.
set O(1) - - - - Définit un élément d’un tableau sur la valeur spécifiée.
skip - - O(N) - - Retourne une séquence qui ignore N éléments de la séquence sous-jacente, puis génère les éléments restants de la séquence.
skipWhile - - O(N) - - Retourne une séquence qui, lorsqu’elle est itérée, ignore les éléments de la séquence sous-jacente tandis que le prédicat donné retourne true, puis génère les éléments restants de la séquence.
trier Moyenne O(N*log(N))

O(N^2) pire cas
O(N*log(N)) O(N*log(N)) - - Trie la collection par valeur d’élément. Les éléments sont comparés à l’aide de comparer.
sortBy Moyenne O(N*log(N))

O(N^2) pire cas
O(N*log(N)) O(N*log(N)) - - Trie la liste donnée à l’aide de clés fournies par la projection donnée. Les clés sont comparées à l’aide de compare.
sortInPlace Moyenne O(N*log(N))

O(N^2) pire cas
- - - - Trie les éléments d’un tableau en le mutant en place et en utilisant la fonction de comparaison donnée. Les éléments sont comparés à l’aide de comparer.
sortInPlaceBy Moyenne O(N*log(N))

O(N^2) pire cas
- - - - Trie les éléments d’un tableau en le mutant sur place et en utilisant la projection donnée pour les clés. Les éléments sont comparés à l’aide de comparer.
sortInPlaceWith Moyenne O(N*log(N))

O(N^2) pire cas
- - - - Trie les éléments d’un tableau en le mutant en place et en utilisant la fonction de comparaison donnée comme ordre.
sortWith Moyenne O(N*log(N))

O(N^2) pire cas
O(N*log(N)) - - - Trie les éléments d’une collection à l’aide de la fonction de comparaison donnée comme ordre et retourne une nouvelle collection.
sous O(N) - - - - Construit un tableau qui contient le sous-intervalle donné, spécifié par l'indice de départ et la longueur.
somme O(N) O(N) O(N) - - Retourne la somme des éléments de la collection.
sumBy O(N) O(N) O(N) - - Retourne la somme des résultats générés en appliquant la fonction à chaque élément de la collection.
tail - O(1) - - - Retourne la liste sans son premier élément.
take - - O(N) - - Retourne les éléments de la séquence jusqu’à un nombre spécifié.
takeWhile - - O(1) - - Retourne une séquence qui, lorsqu’elle est itérée, génère des éléments de la séquence sous-jacente tandis que le prédicat donné retourne true, puis ne retourne plus d’éléments.
toArray - O(N) O(N) O(N) O(N) Crée un tableau à partir de la collection donnée.
toList O(N) - O(N) O(N) O(N) Crée une liste à partir de la collection donnée.
toSeq O(1) O(1) - O(1) O(1) Crée une séquence à partir de la collection donnée.
truncate - - O(1) - - Retourne une séquence qui, lorsqu’elle est énumérée, ne retourne pas plus d’éléments N.
tryFind O(N) O(N) O(N) O(log(N)) - Recherche un élément qui satisfait à un prédicat donné.
tryFindIndex O(N) O(N) O(N) - - Recherche le premier élément qui satisfait à un prédicat donné et retourne l’index de l’élément correspondant, ou None s’il n’existe aucun élément de ce type.
tryFindKey - - - O(log(N)) - Retourne la clé du premier mappage de la collection qui satisfait le prédicat donné, ou retourne None si aucun élément de ce type n’existe.
tryPick O(N) O(N) O(N) O(log(N)) - Applique la fonction donnée aux éléments successifs, retournant le premier résultat où la fonction retourne Some pour une valeur. Si aucun élément de ce type n’existe, l’opération retourne None.
unfold - - O(N) - - Retourne une séquence qui contient les éléments générés par le calcul donné.
union - - - - O(M*log(N)) Calcule l’union des deux ensembles.
unionMany - - - - O(N1*N2...) Calcule l’union d’une séquence d’ensembles.
décompresser O(N) O(N) O(N) - - Fractionne une liste de paires en deux listes.
unzip3 O(N) O(N) O(N) - - Fractionne une liste de triples en trois listes.
windowed - - O(N) - - Retourne une séquence qui génère des fenêtres glissantes contenant des éléments dessinés à partir de la séquence d’entrée. Chaque fenêtre est retournée sous la forme d’un tableau actualisé.
zip O(N) O(N) O(N) - - Combine les deux collections dans une liste de paires. Les deux listes doivent avoir des longueurs égales.
zip3 O(N) O(N) O(N) - - Combine les trois collections dans une liste de triples. Les listes doivent avoir des longueurs égales.

Voir aussi