Dans cet article nous allons implémenter une variante persistante et immuable de la LinkedList en Java avec
partage structurel partiel pour des gains d'efficacité temporelle et spatiale.
Une liste chaînée est une structure de données composée d'une collection de nœuds où chaque nœud contient une valeur et une référence au nœud suivant dans la séquence. Les opérations telles que l'ajout d'un élément en tête de la liste ou la suppression d'un élément de la tête sont des opérations O(1). Cependant, les opérations telles que l'ajout d'un élément à la fin de la liste ou la suppression d'un élément à la fin sont des opérations O(n) où n est le nombre d'éléments dans la liste.
En programmation fonctionnelle, l'immuabilité est un concept clé. L'immuabilité signifie qu'une fois qu'une structure de données est créée, elle
ne peut pas être modifié. Au lieu de cela, une nouvelle structure de données est créée avec les modifications et celle d'origine reste inchangée.
Cette propriété nous permet plusieurs avantages :
Cependant, les collections en Java et puisque cet article se concentre sur LinkedList, sont mutables par défaut. Les raisons peuvent être multiples
allant du fait de ne pas y avoir pensé après coup lors de la conception des collections jusqu'aux raisons de performance inhérentes à
structures de données immuables.
Le JDK fournit des collections non modifiables qui enveloppent les collections originales. Ils prennent en charge l'immuabilité mais ils ne sont pas persistants et ne fournissent pas de véritable méthode sécurisée de type. Ils enveloppent les collections originales et ils
lève une exception lorsqu'une opération de modification est appelée. Ce n'est pas la même chose que l'immuabilité où la structure des données ne peut pas être modifiée du tout tout en garantissant qu'il sera difficile d'obtenir une UnsupportedOperationException au moment de l'exécution.
Bien que les termes persistant et immuable soient souvent utilisés de manière interchangeable, ils ont des significations différentes. Si l'immuabilité ne permet pas la modification de la structure des données, la persistance permet le partage de la structure des données lorsqu'elle est modifiée. Cela signifie que lorsqu'une structure de données est modifiée, c'est-à-dire qu'une nouvelle version est créée, des parties de l'ancienne structure de données peuvent être partagées avec la nouvelle, permettant ainsi des gains d'efficacité en termes de temps et d'espace. Cette technique est appelée partage structurel.
Il existe plusieurs façons d’obtenir la persistance dans les structures de données. Les structures de données vont du simple au complexe, comme l'utilisation d'arbres équilibrés comme les arbres AVL ou Rouge-Noir, à des structures plus complexes comme les arbres Finger et les arbres équilibrés basés sur Radix.
Dans cet article, nous allons implémenter une version plus simple d'une LinkedList persistante et immuable avec partage structurel partiel. La raison en est que LinkedList est une structure de données simple et elle nous aidera à mieux comprendre les concepts d'immuabilité et de persistance et généralement la mise en œuvre de structures de données plus complexes est intrinsèquement une tâche difficile.
Ci-dessous, nous allons implémenter une LinkedList unique persistante et immuable en Java en utilisant une approche étape par étape.
Pour une implémentation complète et des monades et utilitaires supplémentaires pour vous aider dans votre visite de programmation fonctionnelle vers Java, vous pouvez consulter cette superbe petite bibliothèque FunctionalUtils.
Le nom que nous donnerons à notre LinkedList sera SeqList et ce sera une classe générique.
Dans un premier temps, nous devons réfléchir aux opérations que nous allons soutenir dans notre Liste.
Nous pouvons considérer une LinkedList comme une structure composée de nœuds où chaque nœud comprend :
La mise en œuvre complète peut être trouvée ici
Étant donné que le dernier élément de la liste est une LinkedList vide et que chaque élément est un nœud avec une tête et une queue, nous pouvons représenter notre LinkedList comme une structure de données récursive composée de deux classes :
public record Empty<T>() implements SeqList<T> {
}
public record Cons<T>(T head, SeqList<T> tail) implements SeqList<T> {
}
où Cons est un terme de programmation fonctionnelle nommé Construct qui remonte au langage de programmation Lisp.
Compte tenu de ce qui précède, nous pouvons implémenter l'interface SeqList comme suit :
public sealed interface SeqList<T> permits Empty, Cons {
/**
* Creates an empty list.
*
* @param <T> the type of the elements
* @return an empty list
*/
static <T> SeqList<T> empty() {
return new Empty<>();
}
/**
* Creates a new list with the given elements. The complexity of this method is O(n) where n is
* the number of elements.
*
* @param elements the elements to add
* @param <T> the type of the elements
* @return a new list with the elements added
*/
@SafeVarargs
static <T> SeqList<T> of(T... elements) {
SeqList<T> list = empty();
for (int i = elements.length - 1; i >= 0; i--) {
list = list.add(elements[i]);
}
return list;
}
/**
* Prepends the element to the list. The complexity of this method is O(1).
*
* @param element the element to add
* @return a new list with the element prepended
*/
default SeqList<T> add(T element) {
return new Cons<>(element, this);
}
}
Décomposons ce que nous avons écrit ci-dessus :
Nous devons mettre en œuvre le reste de nos opérations. Commençons par l'opération de suppression :
/**
* Removes the first occurrence of the element from the list. If the element is not found, the
* list is returned as is. The complexity of this method is O(n) where n is the number of
* elements. It uses structural sharing up to the element to remove. If the element is not found
* the structural sharing is not utilized.
*
* @param element the element to remove
* @return a new list with the element removed
* @throws StackOverflowError for infinite lists
*/
default SeqList<T> remove(T element) {
if (isEmpty()) {
return this;
}
if (head().equals(element)) {
return tail();
}
return new Cons<>(head(), tail().remove(element));
}
Et implémentez en plus la méthode tail() et quelques autres méthodes utiles dans nos sous-classes :
public record Cons<T>(T head, SeqList<T> tail) implements SeqList<T> {
@Override
public boolean isEmpty() {
return false;
}
@Override
public Optional<T> headOption() {
return Optional.ofNullable(head);
}
@Override
public Optional<T> last() {
if (tail.isEmpty()) {
return Optional.ofNullable(head);
}
return tail.last();
}
}
public record Empty<T>() implements SeqList<T> {
@Override
public boolean isEmpty() {
return true;
}
@Override
public T head() {
throw new UnsupportedOperationException("head() called on empty list");
}
@Override
public Optional<T> headOption() {
return Optional.empty();
}
@Override
public SeqList<T> tail() {
throw new UnsupportedOperationException("tail() called on empty list");
}
@Override
public Optional<T> last() {
return Optional.empty();
}
}
Comme nous pouvons le constater à partir de l'implémentation de la méthode Remove, nous utilisons des appels récursifs pour supprimer l'élément de
la liste. Il s'agit d'un modèle typique de la programmation fonctionnelle où nous utilisons la récursivité pour parcourir la liste et
supprimer l'élément. Des précautions doivent être prises pour éviter les débordements de pile en cas de listes infinies. Une amélioration future pourrait consister à utiliser l'optimisation de la récursion de queue qui n'est pas prise en charge en Java mais pourrait être réalisée à l'aide du trampoline.
Enfin, implémentons les opérations map et flatMap pour transformer notre liste en monade :
/**
* Applies a map function to the elements of the list. The complexity of this method is O(n) where
* n is the number of elements.
* <b>It does not use structural sharing</b> as it requires advanced data structures to achieve
* it.
*
* @param fn the map function
* @param <U> the type of the elements of the new list
* @return a new list with the elements mapped
* @throws StackOverflowError for infinite lists
*/
default <U> SeqList<U> map(Function<? super T, ? extends U> fn) {
if (isEmpty()) {
return empty();
}
return new Cons<>(fn.apply(head()), tail().map(fn));
}
/**
* Applies a flat map function to the elements of the list. The complexity of this method is O(n)
* where n is the number of elements.
* <b>It does not use structural sharing</b> as it requires advanced data structures to achieve
* it.
*
* @param fn the flat map function
* @param <U> the type of the elements of the new list
* @return a new list with the elements flat mapped
* @throws StackOverflowError for infinite lists
*/
default <U> SeqList<U> flatMap(Function<? super T, ? extends SeqList<U>> fn) {
if (isEmpty()) {
return empty();
}
SeqList<U> mappedHead = fn.apply(head());
SeqList<U> newTail = tail().flatMap(fn);
return concat(mappedHead, newTail);
}
/**
* Concatenates two lists. The complexity of this method is O(n) where n is the number of
* elements.
*
* @param list1 the first list
* @param list2 the second list
* @param <T> the type of the elements
* @return a new list with the elements of the two lists concatenated
* @throws StackOverflowError for infinite lists
*/
static <T> SeqList<T> concat(SeqList<T> list1, SeqList<T> list2) {
if (list1.isEmpty()) {
return list2;
}
return new Cons<>(list1.head(), concat(list1.tail(), list2));
}
Comme nous pouvons le voir grâce à l'implémentation des méthodes map et flatMap, nous utilisons des appels récursifs pour parcourir la liste et appliquer la fonction à chaque élément. La méthode flatMap est un peu plus complexe car elle nécessite que la fonction renvoie une nouvelle liste que nous devons concaténer avec le reste de la liste. Les deux méthodes n’utilisent pas le partage structurel en raison de sa difficulté de notoriété et de l’importance d’utiliser des structures de données avancées. Une future amélioration sera examinée dans un prochain article.
Voyons quelques exemples d'utilisation de notre SeqList.
SeqList<Integer> list = SeqList.of(1, 2, 3, 4, 5, 6); SeqList<Double> updatedList = list .filterOut(number -> number % 2 == 0) .map(number -> Math.pow(number, 2));
SeqList<String> list = SeqList.of("a", "b", "c", "d", "e");
SeqList<String> updatedList = list
.map(letter -> "prefix" + letter + "suffix");
SeqList<SeqList<Integer>> list = SeqList.of(SeqList.of(1, 2), SeqList.of(3, 4), SeqList.of(5, 6)); SeqList<Integer> updatedList = list .flatMap(seqList -> seqList);
SeqList<Integer> list = SeqList.of(1, 2, 3, 4, 5, 6);
switch (list) {
case Empty() -> {
// do something
}
case Cons<Integer> cons -> {
//do something else
}
}
Dans cet article, nous avons implémenté une LinkedList persistante et immuable en Java avec partage structurel partiel. Nous avons démontré les avantages de l'immuabilité et de la persistance et comment nous pouvons les réaliser en Java. Nous avons également montré comment transformer notre LinkedList en monade pour faciliter la composition des fonctions. Nous avons discuté des avantages et des inconvénients des structures de données persistantes et immuables et de la manière dont elles peuvent être utilisées dans la pratique.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Comment supprimer le verrou de sécurité de Firefox
Comment annuler le renouvellement automatique de la carte Taobao Money Saving
Que signifie le réseau Apple LTE ?
vscode crée une méthode de fichier HTML
Annuler le mot de passe de mise sous tension sous XP
cadre réseau
Introduction au document en JS
Quelles sont les commandes d'arrêt de Linux ?
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
