스칼라에서 변경할 수없는 데이터 구조

Question

스칼라가 불변의 데이터 구조를 지원한다는 것을 알고 있습니다. 목록을 업데이트 할 때마다 힙에서 새로운 객체와 참조를 생성합니다. 내가 목록에 두 번째 요소를 추가 할 때

예

val xs:List[Int] = List.apply(22) 
val newList = xs ++ (33) 

는 그래서 모두 (22)를 포함하고 33.This 정확하게 자바에서 어떻게 작동하는지 불변 문자열처럼 작동하는 새로운 목록을 생성합니다. 그래서 질문은 목록에 요소를 추가 할 때마다 새로운 개체가 매번 생성 될 것입니다.이 방법은 효율적이지 않습니다. 거기에 영구 데이터 구조와 같은 몇 가지 특별한 데이터 구조가 있습니다.이 문제를 처리 할 때 사용됩니다.

Answer 1

목록에 추가하는 것은 복잡성이 O (n)이며 비효율적입니다. 일반적인 방법은 목록을 작성하는 동안 목록 앞에 추가하고 마지막으로이를 취소하는 것입니다.

이제 새 개체 만들기에 대한 질문이 앞자리에도 적용됩니다. xs은 불변이므로 newList은 앞 뒤의 나머지 데이터에 대해 xs를 가리 키기 만합니다.

Answer 2

@manojlds가 그의 분석에서 옳은 반면, 원래 게시물은 작업을 수행 할 때마다 목록 노드를 복제하는 효율성에 대해 질문했습니다.

@manojlds가 말한 것처럼, 목록을 구성하려면 종종 역방향으로 생각해야합니다. 즉, 목록을 작성한 다음이를 뒤집어 야합니다. 목록 건물에는 "불필요한"복사가 필요한 여러 가지 상황이 있습니다. 그러나

val xsa = ListBuffer[Int](22) 
xsa += 33 
val newList = xsa.toList 

, 사실 그 :이를 위해

는 스칼라에서 사용할 수있는 가변 데이터 구조는 당신이 당신의 목록을 구축하고 불변의리스트로 결과를 추출하는 데 사용할 수있는 ListBuffer라고있다 목록 데이터 구조는 일반적으로 불변이므로 목록을 분석, 작성 및 재구성하는 데 매우 유용한 도구가 있습니다. 많은 내장 명령은 불변성을 이용합니다. 확장을 통해, 여러분 자신의 프로그램 또한 이러한 불변성을 이용할 수 있습니다.