永続的かつ不変の Java LinkedList-＆＃＆チュートリアル-php.cn

Persistent and Immutable Java LinkedList

この記事では、
を使用して Java で LinkedList の永続的かつ不変のバリエーションを実装します。部分的な構造共有により時間と空間の効率が向上します。

導入

リンクリストとは何ですか

リンクリストは、各ノードに値とシーケンス内の次のノードへの参照が含まれるノードのコレクションで構成されるデータ構造です。リストの先頭に要素を追加したり、先頭から要素を削除したりするような操作は O(1) 操作です。ただし、リストの末尾に要素を追加したり、末尾から要素を削除したりするような操作は、O(n) 回の操作です (n はリスト内の要素の数です)。

不変の LinkedList が必要な理由

関数型プログラミングでは、不変性が重要な概念です。不変性とは、データ構造が一度作成されると、
変更することはできません。代わりに、変更を加えて新しいデータ構造が作成され、元のデータ構造は変更されません。

このプロパティにより、次のような利点が得られます。

スレッドの安全性: データ構造は不変であるため、同期を必要とせずに複数のスレッド間で共有できます。
予測可能性: データ構造は不変であるため、いつでもデータ構造の状態を推論できます。
元に戻す: データ構造は不変であるため、以前のバージョンのデータ構造を使用していつでも前の状態に戻すことができます。
デバッグ: データ構造は変更できないため、不変性によりデバッグが容易になります。

ただし、Java のコレクションは、この記事の焦点が LinkedList にあるため、デフォルトで変更可能です。理由はたくさんあるかもしれません
コレクションが設計されたときの思い付きではないことから、
に固有のパフォーマンス上の理由に至るまで、不変のデータ構造。

変更不可能な JDK コレクションとこの LinkedList の違い

JDK は、元のコレクションのラッパーである変更不可能なコレクションを提供します。これらは不変性をサポートしますが、永続的ではなく、真の型で安全な方法を提供しません。これらは元のコレクションのラッパーであり、
変更操作が呼び出されたときに例外をスローします。これは、実行時に UnsupportedOperationException が発生しにくくなる一方で、データ構造をまったく変更できない不変性とは異なります。

永続的 vs 不変的

永続的と不変という用語はしばしば同じ意味で使用されますが、意味は異なります。不変性ではデータ構造の変更は許可されませんが、永続性ではデータ構造が変更された場合にその構造を共有できます。これは、データ構造が変更されるとき、つまり新しいバージョンが作成されるときに、古いデータ構造の一部を新しいデータ構造と共有でき、時間とスペースの効率が向上することを意味します。この手法は構造共有と呼ばれます。

データ構造の永続性を実現するには複数の方法があります。データ構造は、単純なものから、AVL や赤黒ツリーなどのバランスツリーの使用などの複雑なもの、フィンガーツリーや基数ベースのバランスツリーなどのより複雑なものまで多岐にわたります。

この記事では、部分的な構造共有を備えた永続的かつ不変の LinkedList のより単純なバージョンを実装します。その理由は、LinkedList は単純なデータ構造であり、不変性と永続性の概念をより深く理解するのに役立ちますが、通常、より複雑なデータ構造の実装は本質的に困難な作業であるためです。

実装

以下では、段階的なアプローチを使用して、Java で永続的かつ不変の単独の LinkedList を実装します。

Java への関数型プログラミングのツアーを支援する完全な実装と追加のモナドとユーティリティについては、この素晴らしい小さなライブラリ FunctionalUtils をチェックしてください。

LinkedList に付ける名前は SeqList となり、汎用クラスになります。

最初に、リストでサポートする操作について考える必要があります。

O(1) 操作となるリストの先頭への追加。
リストからの要素の削除。要素が末尾の方にある場合、最悪でも O(n) 操作になります。
リスト内の任意の位置に追加します。
述語を指定して要素をフィルターイン/フィルターアウトするフィルター操作。
関数の合成を容易にするために、リストをモナドに変換する Map および FlatMap 操作。

LinkedList は、各ノードが以下を含むノードで構成される構造として考えることができます。

head は値を保持します。
tail はリストの残りを保持し、リストの最後までの head と tail で構成される LinkedList になります。
リストの末尾は空の LinkedList で表されます。これは、先頭と末尾の両方が null であることを意味します。

完全な実装はここにあります

リストの最後の要素が空の LinkedList で、各要素が先頭と末尾を持つノードであるとすると、LinkedList を 2 つのクラスで構成される再帰データ構造として表すことができます。

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

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

ログイン後にコピー

ここで、Cons は、Construct という名前の関数型プログラミング用語であり、その起源は Lisp プログラミング言語にまで遡ります。

上記を考慮すると、SeqList インターフェースを次のように実装できます:

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

ログイン後にコピー

上で書いたことを詳しく見てみましょう:

LinkedList のインターフェースとなるシールされたインターフェース SeqList を作成しました。
メソッド empty() は、クラス Empty のインスタンスである空のリストを作成します。
メソッド add() はリストの先頭に要素を追加します。指定された要素と現在のリストを使用して新しいノードを作成しているだけなので、このメソッドの複雑さは O(1) です。このメソッドは、新しいリストが現在のリストの末尾を共有するため、構造共有を使用します。
of() メソッドは、指定された要素を含む新しいリストを作成します。このメソッドの複雑さは O(n) です (n は要素の数です)。明らかなように、最後の要素から開始してリストに追加します。これは、要素の順序を維持したいためです。

残りの操作を実装する必要があります。削除操作から始めましょう:

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

ログイン後にコピー

さらに、tail() メソッドとその他の便利なメソッドをサブクラスに実装します。

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

ログイン後にコピー

remove メソッドの実装からわかるように、再帰呼び出しを使用して要素を削除しています
リスト。これは関数型プログラミングの典型的なパターンで、再帰を使用してリストを走査し、
要素を削除します。無限リストの場合はスタックオーバーフローを避けるように注意する必要があります。将来の改善としては、Java ではサポートされていない末尾再帰最適化を使用することが考えられますが、トランポリンを使用すると実現できる可能性があります。

最後に、map 操作と flatMap 操作を実装してリストをモナドに変換しましょう:

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

ログイン後にコピー

map メソッドと flatMap メソッドの実装からわかるように、再帰呼び出しを使用してリストを走査し、各要素に関数を適用しています。 flatMap メソッドは、リストの残りの部分と連結する必要がある新しいリストを返す関数を必要とするため、少し複雑です。どちらの方法でも、構造共有の難しさは有名であり、高度なデータ構造を使用することが重要であるため、構造共有は使用していません。今後の改善点については今後の記事で検討していきます。

使用例

SeqList の使用例をいくつか見てみましょう。

整数のリストがあり、偶数をフィルターで除外し、それらを不変性と永続性を持って 2 のべき乗で乗算したいと考えてください。

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

ログイン後にコピー

もう 1 つの例は、JDK 21 スイッチ式を使用し、コンパイラチェックを利用したパターンマッチングです。

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

ログイン後にコピー

短所

パフォーマンス: リストが主にリストの先頭から要素を取得する前に要素を追加するために使用される場合、パフォーマンスは良好です。他のすべてのケースでは、少なくともこの実装では O(n) が必要です。
複雑さ: 永続的で不変の LinkedList の実装は、変更可能な対応するものよりも複雑です。
メモリ: 永続的で不変の LinkedList の実装には、操作ごとに新しいリストが作成されるため、変更可能な対応するリストよりも多くのメモリが必要です。構造的な共有により、これは軽減されますが、排除されるわけではありません。

結論

この記事では、部分的な構造共有を備えた永続的で不変の LinkedList を Java に実装しました。不変性と永続性の利点と、Java でそれらを実現する方法を示しました。また、関数の合成を容易にするために、LinkedList をモナドに変換する方法も示しました。永続的および不変のデータ構造の長所と短所、およびそれらを実際に使用する方法について説明しました。

以上が永続的かつ不変の Java LinkedListの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。