구조 공유 목록 스칼라

Question

에 내가 스칼라에서 목록에서 구조 공유에 대한 질문이 있습니다. 나는 인터넷에서이 문장을 어디에서 읽었 는가?

List는 꼬리표의 구조적 공유를 구현한다. 이것은 많은 연산이 제로 또는 일정 메모리 비용이라는 것을 의미합니다.

그러나 목록에 대한 작업 시간과 메모리 비용이 얼마나 줄어 들었는지는 알지 못합니다.

val mainList = List(3, 2, 1) 
val with4 = 4 :: mainList // O(1) 

우리가 대신하지만,리스트의 작업 (1) 및 메모리 비용을 하나의 O 될 시간 with4 다른 목록을 만들려면 예를

를 들어 어떻게 다른 것입니까? 나는 length() 또는 reverse()를 사용하여 ... O (n)을 정상적으로 유지합니까? 아무도 나에게 설명해 주시겠습니까? 그리고 어쩌면 모범이 될 수 있다면 정말 도움이 될 것입니다. 고맙습니다!

Answer 1

(O (1))의 구조를 공유 앞에 추가되는 기인 (::), 머리와 꼬리 일정 시간 실행 목록 동작. 대부분의 다른 연산은 선형 시간 (O (n))입니다. length 및 reverse 같은 myList.head 및 mylist.tail, 다른 것들 선형 시간이되는만큼

당신의 예는, 4 :: myList가 일정 시간이 올바른 것입니다.

다른 모든 것들은 O (n)이기 때문에, List은 이러한 작업 만 사용하지 않는 한 대부분의 경우에 특히 유용한 모음이 아닙니다.

당신은 다른 컬렉션의 실행 특성의 개요 http://docs.scala-lang.org/overviews/collections/performance-characteristics.html를 참조 할 수 있습니다.