이 기사에서는
을 사용하여 Java에서 LinkedList의 지속적이고 불변적인 변형을 구현할 것입니다.
시간과 공간 효율성 향상을 위한 부분적인 구조적 공유.
소개
LinkedList 란 무엇입니까?
연결된 목록은 각 노드가 값과 시퀀스의 다음 노드에 대한 참조를 포함하는 노드 모음으로 구성된 데이터 구조입니다. 목록의 헤드에 요소를 추가하거나 헤드에서 요소를 제거하는 것과 같은 작업은 O(1) 작업입니다. 그러나 목록 끝에 요소를 추가하거나 끝에서 요소를 제거하는 등의 작업은 O(n) 작업입니다. 여기서 n은 목록에 있는 요소 수입니다.
불변의 LinkedList가 필요한 이유
함수형 프로그래밍에서는 불변성이 핵심 개념입니다. 불변성은 일단 데이터 구조가 생성되면
수정할 수 없습니다. 대신 수정 사항이 포함된 새로운 데이터 구조가 생성되며 원본은 변경되지 않은 상태로 유지됩니다.
이 속성은 다음과 같은 여러 가지 이점을 제공합니다.
-
스레드 안전성: 데이터 구조는 불변이므로 동기화할 필요 없이 여러 스레드에서 공유할 수 있습니다.
-
예측 가능성: 데이터 구조는 불변이므로 언제든지 데이터 구조의 상태를 추론할 수 있습니다.
-
실행 취소: 데이터 구조는 불변이므로 이전 버전의 데이터 구조를 사용하여 언제든지 이전 상태로 되돌릴 수 있습니다.
-
디버깅: 불변성은 데이터 구조를 수정할 수 없으므로 디버깅을 더 쉽게 만듭니다.
그러나 이 기사의 초점이 LinkedList에 있으므로 Java의 컬렉션은 기본적으로 변경 가능합니다. 이유는 다양할 수 있습니다
컬렉션을 디자인할 때 나중에 고려하지 않는 것부터 컬렉션에 내재된 성능상의 이유까지
불변의 데이터 구조.
수정 불가능한 JDK 컬렉션과 이 LinkedList의 차이점
JDK는 원본 컬렉션을 감싸는 수정 불가능한 컬렉션을 제공합니다. 불변성을 지원하지만 지속성이 없으며 진정한 유형의 안전한 방법을 제공하지도 않습니다. 이는 원래 컬렉션의 포장지이며
수정 작업이 호출되면 예외가 발생합니다. 이는 런타임에 UnsupportedOperationException을 발생시키기 어렵게 하면서 데이터 구조를 전혀 수정할 수 없는 불변성과는 다릅니다.
지속성 대 불변성
영속성과 불변성이라는 용어는 종종 같은 의미로 사용되지만 의미는 다릅니다. 불변성은 데이터 구조의 수정을 허용하지 않지만 지속성은 수정 시 데이터 구조의 공유를 허용합니다. 이는 데이터 구조가 수정되면(즉, 새 버전이 생성됨) 이전 데이터 구조의 일부를 새 데이터 구조와 공유하여 시간 및 공간 효율성을 높일 수 있음을 의미합니다. 이 기술을 구조적 공유라고 합니다.
데이터 구조의 지속성을 달성하는 방법에는 여러 가지가 있습니다. 데이터 구조는 AVL 또는 Red-Black 트리와 같은 균형 트리를 사용하는 단순한 것부터 핑거 트리 및 기수 기반 균형 트리와 같은 보다 복잡한 구조까지 다양합니다.
이 기사에서는 부분적인 구조 공유를 통해 지속적이고 불변적인 LinkedList의 더 간단한 버전을 구현할 것입니다. 그 이유는 LinkedList가 단순한 데이터 구조이고 불변성과 지속성의 개념을 더 잘 이해하는 데 도움이 되며 일반적으로 더 복잡한 데이터 구조의 구현은 본질적으로 어려운 작업이기 때문입니다.
구현
아래에서는 단계별 접근 방식을 사용하여 Java에서 지속적이고 불변적인 단일 LinkedList를 구현하겠습니다.
Java에 대한 함수형 프로그래밍 둘러보기에 도움이 되는 완전한 구현과 추가 모나드 및 유틸리티를 보려면 이 멋진 작은 라이브러리 FunctionalUtils를 확인하세요.
LinkedList에 지정할 이름은 SeqList이며 일반 클래스가 됩니다.
먼저 목록에서 지원할 작업에 대해 생각해 봐야 합니다.
- O(1) 작업이 될 목록의 선두에 추가됩니다.
- 목록에서 요소를 제거하면 요소가 끝에 있을 경우 최악의 경우 O(n) 연산이 발생하게 됩니다.
- 목록의 임의 위치에 추가됩니다.
- 조건어에 따라 요소를 필터링/필터링하는 필터링 작업
- 더 쉬운 함수 구성을 위해 List를 Monad로 변환하는 Map 및 FlatMap 작업.
LinkedList는 각 노드가 다음과 같이 구성된 노드로 구성된 구조로 생각할 수 있습니다.
-
머리값을 담고 있습니다.
-
tail 목록의 끝까지 head와 tail로 구성된 LinkedList인 나머지 목록을 보유합니다.
- 목록의 끝은 빈 LinkedList로 표시됩니다. 이는 head와 tail이 모두 null임을 의미합니다.
전체 구현은 여기
에서 확인할 수 있습니다.
목록의 마지막 요소가 빈 LinkedList이고 각 요소가 머리와 꼬리가 있는 노드라는 점을 고려하면 LinkedList를 두 클래스로 구성된 재귀 데이터 구조로 나타낼 수 있습니다.
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() 메소드는 빈 클래스의 인스턴스인 빈 목록을 생성합니다.
- 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();
}
}
로그인 후 복사
제거 메소드의 구현을 검토할 수 있듯이 재귀 호출을 사용하여 요소를 제거하고 있습니다.
목록. 이는 재귀를 사용하여 목록을 탐색하고
요소를 제거하십시오. 목록이 무한할 경우 스택 오버플로를 방지하도록 주의해야 합니다. 향후 개선 사항은 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);
로그인 후 복사
- 또 다른 예는 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의 구현에는 각 작업에 대한 새 목록 생성으로 인해 변경 가능한 대응 항목보다 더 많은 메모리가 필요합니다. 구조적 공유를 통해 이러한 문제는 완화되지만 제거되지는 않습니다.
결론
이 기사에서는 부분 구조 공유를 통해 Java에서 지속적이고 불변적인 LinkedList를 구현했습니다. 불변성과 지속성의 이점과 Java에서 이를 달성할 수 있는 방법을 시연했습니다. 또한 더 쉬운 함수 구성을 위해 LinkedList를 Monad로 변환하는 방법도 보여주었습니다. 지속적이고 불변적인 데이터 구조의 장점과 단점, 그리고 실제로 어떻게 사용할 수 있는지에 대해 논의했습니다.
위 내용은 지속적이고 불변적인 Java LinkedList의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
