Persistente und unveränderliche Java LinkedList

In diesem Artikel werden wir eine persistente und unveränderliche Variante der LinkedList in Java implementieren mit
teilweise strukturelle gemeinsame Nutzung für Zeit- und Raumeffizienzgewinne.

Einführung

Was ist eine LinkedList?

Eine verknüpfte Liste ist eine Datenstruktur, die aus einer Sammlung von Knoten besteht, wobei jeder Knoten einen Wert und einen Verweis auf den nächsten Knoten in der Sequenz enthält. Operationen wie das Hinzufügen eines Elements zum Kopf der Liste oder das Entfernen eines Elements aus dem Kopf sind O(1)-Operationen. Allerdings sind Operationen wie das Hinzufügen eines Elements am Ende der Liste oder das Entfernen eines Elements vom Ende O(n)-Operationen, wobei n die Anzahl der Elemente in der Liste ist.

Warum brauchen wir eine unveränderliche LinkedList?

In der funktionalen Programmierung ist Unveränderlichkeit ein Schlüsselkonzept. Unveränderlichkeit bedeutet, dass eine einmal erstellte Datenstruktur
ist kann nicht geändert werden. Stattdessen wird mit den Änderungen eine neue Datenstruktur erstellt und die ursprüngliche bleibt unverändert.

Diese Immobilie bietet uns mehrere Vorteile:

1. Thread-Sicherheit: Da die Datenstruktur unveränderlich ist, kann sie von mehreren Threads gemeinsam genutzt werden, ohne dass eine Synchronisierung erforderlich ist.
2. Vorhersagbarkeit: Da die Datenstruktur unveränderlich ist, können wir zu jedem Zeitpunkt Rückschlüsse auf den Zustand der Datenstruktur ziehen.
3. Rückgängigmachen: Da die Datenstruktur unveränderlich ist, können wir jederzeit zu einem früheren Zustand zurückkehren, indem wir die vorherige Version der Datenstruktur verwenden.
4. Debugging: Unveränderlichkeit erleichtert das Debuggen, da die Datenstruktur nicht geändert werden kann.

Java-Sammlungen sind jedoch standardmäßig veränderbar, da der Schwerpunkt dieses Artikels auf LinkedList liegt. Die Gründe können vielfältig sein
Das reicht von einem nicht nachträglichen Einfall bei der Gestaltung der Kollektionen bis hin zu Leistungsgründen, die inhärenten
zugrunde liegen unveränderliche Datenstrukturen.

Unterschied zwischen nicht veränderbaren JDK-Sammlungen und dieser LinkedList

Das JDK stellt unveränderliche Sammlungen bereit, die die Originalsammlungen umhüllen. Sie unterstützen Unveränderlichkeit, sind jedoch weder dauerhaft noch bieten sie eine wirklich typsichere Möglichkeit. Sie sind Hüllen um die Originalkollektionen und sie
löst eine Ausnahme aus, wenn eine Änderungsoperation aufgerufen wird. Dies ist nicht dasselbe wie Unveränderlichkeit, bei der die Datenstruktur überhaupt nicht geändert werden kann und gleichzeitig sichergestellt wird, dass es schwierig ist, zur Laufzeit eine UnsupportedOperationException zu erhalten.

Persistent vs. unveränderlich

Obwohl die Begriffe „beständig“ und „unveränderlich“ oft synonym verwendet werden, haben sie unterschiedliche Bedeutungen. Während Unveränderlichkeit keine Änderung der Datenstruktur zulässt, ermöglicht Persistenz die gemeinsame Nutzung der Datenstruktur, wenn diese geändert wird. Das bedeutet, dass bei der Änderung einer Datenstruktur, d. h. bei der Erstellung einer neuen Version, Teile der alten Datenstruktur mit der neuen gemeinsam genutzt werden können, was zu Zeit- und Platzeffizienzgewinnen führt. Diese Technik wird strukturelles Teilen genannt.

Es gibt mehrere Möglichkeiten, Persistenz in Datenstrukturen zu erreichen. Die Datenstrukturen reichen von einfach bis komplex, wie die Verwendung ausgeglichener Bäume wie AVL- oder Rot-Schwarz-Bäume, bis hin zu komplexeren wie Fingerbäumen und Radix-basierten ausgeglichenen Bäumen.

In diesem Artikel werden wir eine einfachere Version einer dauerhaften und unveränderlichen LinkedList mit teilweiser struktureller Freigabe implementieren. Der Grund dafür ist, dass LinkedList eine einfache Datenstruktur ist und uns hilft, die Konzepte der Unveränderlichkeit und Persistenz besser zu verstehen. Normalerweise ist die Implementierung komplexerer Datenstrukturen von Natur aus eine anspruchsvolle Aufgabe.

Durchführung

Im Folgenden werden wir Schritt für Schritt eine persistente und unveränderliche Single LinkedList in Java implementieren.

Eine vollständige Implementierung und zusätzliche Monaden und Dienstprogramme zur Unterstützung Ihrer funktionalen Programmiertour nach Java finden Sie in dieser tollen kleinen Bibliothek FunctionalUtils.

Der Name, den wir unserer LinkedList geben werden, wird SeqList sein und es wird eine generische Klasse sein.

Zunächst müssen wir über die Operationen nachdenken, die wir in unserer Liste unterstützen werden.

1. Hinzufügung zum Kopf der Liste, die eine O(1)-Operation sein wird.
2. Entfernung eines Elements aus der Liste, was im schlimmsten Fall eine O(n)-Operation ist, wenn sich das Element am Ende befindet.
3. Hinzufügung an einer beliebigen Position in der Liste.
4. Filteroperation zum Ein-/Ausfiltern von Elementen mit einem Prädikat.
5. Map- und FlatMap-Operationen, um unsere Liste zur einfacheren Funktionskomposition in eine Monade umzuwandeln.

Wir können uns eine LinkedList als eine Struktur vorstellen, die aus Knoten besteht, wobei jeder Knoten Folgendes umfasst:

1. Kopf, der einen Wert hält.
2. tail enthält den Rest der Liste, die wiederum eine LinkedList ist, die bis zum Ende der Liste aus head und tail besteht.
3. Das Ende der Liste wird durch eine leere LinkedList dargestellt, was bedeutet, dass sowohl Kopf als auch Ende null sind.

Die vollständige Umsetzung finden Sie hier

Angesichts der Tatsache, dass das letzte Element der Liste eine leere LinkedList ist und jedes Element ein Knoten mit einem Kopf und einem Ende ist, können wir unsere LinkedList als rekursive Datenstruktur darstellen, die aus zwei Klassen besteht:

public record Empty<T>() implements SeqList<T> {
}

public record Cons<T>(T head, SeqList<T> tail) implements SeqList<T> {
}

wobei Cons ein funktionaler Programmierbegriff mit dem Namen Construct ist, der auf die Programmiersprache Lisp zurückgeht.

Angesichts des oben Gesagten können wir die SeqList-Schnittstelle wie folgt implementieren:

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);
  }
}

Lassen Sie uns zusammenfassen, was wir oben geschrieben haben:

1. Wir haben eine versiegelte Schnittstelle SeqList erstellt, die als Schnittstelle für unsere LinkedList dienen wird.
2. Die Methode empty() erstellt eine leere Liste, die eine Instanz der Klasse Empty ist.
3. Die Methode add() stellt der Liste ein Element voran. Die Komplexität dieser Methode beträgt O(1), da wir lediglich einen neuen Knoten mit dem angegebenen Element und der aktuellen Liste erstellen. Diese Methode verwendet Strukturelle gemeinsame Nutzung, da die neue Liste das Ende der aktuellen Liste teilt.
4. Die Methode of() erstellt eine neue Liste mit den angegebenen Elementen. Die Komplexität dieser Methode beträgt O(n), wobei n die Anzahl der Elemente ist. Wie es offensichtlich ist, beginnen wir mit dem letzten Element und fügen es der Liste hinzu. Dies liegt daran, dass wir die Reihenfolge der Elemente beibehalten möchten.

Wir müssen den Rest unserer Operationen umsetzen. Beginnen wir mit dem Entfernungsvorgang:

/**
   * 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));
  }

Und implementieren Sie zusätzlich die Methode tail() und einige andere nützliche in unseren Unterklassen:

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();
  }
}

Wie wir anhand der Implementierung der Remove-Methode sehen können, verwenden wir rekursive Aufrufe, um das Element zu entfernen
die Liste. Dies ist ein typisches Muster in der funktionalen Programmierung, bei der wir Rekursion verwenden, um die Liste zu durchlaufen und
Entfernen Sie das Element. Bei unendlichen Listen sollte darauf geachtet werden, Stapelüberläufe zu vermeiden. Eine zukünftige Verbesserung könnte darin bestehen, die Tail-Rekursionsoptimierung zu verwenden, die in Java nicht unterstützt wird, aber durch Trampolining erreicht werden könnte.

Zuletzt implementieren wir die Operationen „map“ und „flatMap“, um unsere Liste in eine Monade umzuwandeln:

/**
   * 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));
  }

Wie wir aus der Implementierung der Methoden „map“ und „flatMap“ sehen können, verwenden wir rekursive Aufrufe, um die Liste zu durchlaufen und die Funktion auf jedes Element anzuwenden. Die flatMap-Methode ist etwas komplexer, da sie erfordert, dass die Funktion eine neue Liste zurückgibt, die wir mit dem Rest der Liste verketten müssen. Beide Methoden verwenden keine strukturelle gemeinsame Nutzung, da sie bekanntermaßen schwierig ist und die Verwendung fortgeschrittener Datenstrukturen wichtig ist. Eine zukünftige Verbesserung wird in einem zukünftigen Artikel untersucht.

Anwendungsbeispiele

Sehen wir uns einige Anwendungsbeispiele unserer SeqList an.

• Stellen Sie sich vor, wir haben eine Liste mit ganzen Zahlen und möchten die geraden Zahlen herausfiltern und sie dann mit der Zweierpotenz multiplizieren, aber mit Unveränderlichkeit und Beständigkeit.

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));

• Stellen Sie sich vor, wir haben eine Liste von Zeichenfolgen und möchten diese mit einem Präfix und einem Suffix verketten.

SeqList<String> list = SeqList.of("a", "b", "c", "d", "e");
SeqList<String> updatedList = list
   .map(letter -> "prefix" + letter + "suffix");

• Stellen Sie sich vor, wir haben eine Liste mit Listen und möchten diese reduzieren.

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);

• Ein weiteres Beispiel ist der Mustervergleich mit JDK 21-Schalterausdrücken und der Nutzung der Compilerprüfungen.

SeqList<Integer> list = SeqList.of(1, 2, 3, 4, 5, 6);
switch (list) {
  case Empty() -> {
    // do something
  }
  case Cons<Integer> cons -> {
    //do something else
  }
}

Nachteile

1. Leistung: Wenn die Liste hauptsächlich zum Voranstellen von Elementen oder zum Abrufen von Elementen aus dem Kopf der Liste verwendet wird, ist die Leistung gut. In allen anderen Fällen ist O(n) zumindest bei dieser Implementierung erforderlich.
2. Komplexität: Die Implementierung einer persistenten und unveränderlichen LinkedList ist komplexer als die ihres veränderlichen Gegenstücks.
3. Speicher: Die Implementierung einer persistenten und unveränderlichen LinkedList erfordert mehr Speicher als ihr veränderliches Gegenstück, da für jeden Vorgang neue Listen erstellt werden. Durch strukturelles Teilen wird dies gemildert, aber nicht beseitigt.

Abschluss

In diesem Artikel haben wir eine persistente und unveränderliche LinkedList in Java mit teilweiser struktureller Freigabe implementiert. Wir haben die Vorteile von Unveränderlichkeit und Persistenz demonstriert und wie wir sie in Java erreichen können. Wir haben auch gezeigt, wie wir unsere LinkedList zur einfacheren Funktionszusammenstellung in eine Monade umwandeln können. Wir haben die Vor- und Nachteile persistenter und unveränderlicher Datenstrukturen besprochen und wie sie in der Praxis eingesetzt werden können.

Das obige ist der detaillierte Inhalt vonPersistente und unveränderliche Java LinkedList. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!