Maison >Java >javaDidacticiel >LinkedList Java persistante et immuable

LinkedList Java persistante et immuable

PHPz
PHPzoriginal
2024-07-24 11:44:21590parcourir

Persistent and Immutable Java LinkedList

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.

Introduction

Qu'est-ce qu'une LinkedList

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.

Pourquoi avons-nous besoin d'une LinkedList immuable

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 :

  1. Sécurité des threads : la structure des données étant immuable, elle peut être partagée sur plusieurs threads sans avoir besoin de synchronisation.
  2. Prévisibilité : Puisque la structure des données est immuable, nous pouvons raisonner sur l'état de la structure des données à tout moment.
  3. Annuler : La structure de données étant immuable, nous pouvons toujours revenir à un état antérieur en utilisant la version précédente de la structure de données.
  4. Débogage : L'immuabilité facilite le débogage puisque la structure des données ne peut pas être modifiée.

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.

Différence entre les collections JDK non modifiables et cette LinkedList

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.

Persistant vs Immuable

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.

Mise en œuvre

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.

  1. Ajout en tête de liste qui va être une opération O(1).
  2. Suppression d'un élément de la liste qui sera au pire une opération O(n) si l'élément est situé vers la fin.
  3. Ajout à une position arbitraire dans la liste.
  4. Opération de filtrage pour filtrer/filtrer les éléments à partir d'un prédicat.
  5. Opérations Map et FlatMap pour transformer notre liste en monade pour une composition de fonctions plus facile.

Nous pouvons considérer une LinkedList comme une structure composée de nœuds où chaque nœud comprend :

  1. tête détenant une valeur.
  2. queue contenant le reste de la liste qui à son tour est une LinkedList composée de la tête et de la queue jusqu'à la fin de la liste.
  3. La fin de la liste est représentée par une LinkedList vide, ce qui signifie que la tête et la queue sont nulles.

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 :

  1. Nous avons créé une interface scellée SeqList qui sera l'interface de notre LinkedList.
  2. La méthode empty() crée une liste vide qui est une instance de la classe Empty.
  3. La méthode add() ajoute un élément au début de la liste. La complexité de cette méthode est O(1) car nous créons simplement un nouveau nœud avec l'élément donné et la liste actuelle. Cette méthode utilise le Partage structurel car la nouvelle liste partage la queue de la liste actuelle.
  4. La méthode of() crée une nouvelle liste avec les éléments donnés. La complexité de cette méthode est O(n) où n est le nombre d’éléments. Comme il est évident, nous partons du dernier élément et l’ajoutons à la liste. C'est parce que nous voulons préserver l'ordre des éléments.

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.

Exemples d'utilisation

Voyons quelques exemples d'utilisation de notre SeqList.

  • Imaginez que nous avons une liste d'entiers et que nous voulons filtrer les nombres pairs puis les multiplier à la puissance deux mais avec immuabilité et persistance.
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));
  • Imaginez que nous ayons une liste de chaînes et que nous souhaitions les concaténer avec un préfixe et un suffixe.
SeqList<String> list = SeqList.of("a", "b", "c", "d", "e");
SeqList<String> updatedList = list
   .map(letter -> "prefix" + letter + "suffix");
  • Imaginez que nous avons une liste de listes et que nous voulons les aplatir.
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);
  • Un autre exemple est la correspondance de modèles utilisant des expressions de commutateur JDK 21 et tirant parti des vérifications du compilateur.
SeqList<Integer> list = SeqList.of(1, 2, 3, 4, 5, 6);
switch (list) {
  case Empty() -> {
    // do something
  }
  case Cons<Integer> cons -> {
    //do something else
  }
}

Inconvénients

  1. Performance : Si la liste est utilisée principalement pour ajouter des éléments au début ou obtenir des éléments de la tête de liste, alors les performances sont bonnes. Dans tous les autres cas, O(n) est requis au moins avec cette implémentation.
  2. Complexité : La mise en œuvre d'une LinkedList persistante et immuable est plus complexe que son homologue mutable.
  3. Mémoire : L'implémentation d'une LinkedList persistante et immuable nécessite plus de mémoire que son homologue mutable en raison de la création de nouvelles listes pour chaque opération. Avec le partage structurel, cela est atténué mais pas éliminé.

Conclusion

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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn