1. 홈
  2. 질의 응답
  3. 인덱싱 된 크기 복잡함

인덱싱 된 크기 복잡함

2015-01-21 3 views
2

인덱싱 된 컬렉션 (대개는 immutable Vectors)으로 작업 할 때 나는 coll(coll.size-1)에 대한 편리한 바로 가기로 사용되는 것으로 종종 coll.last을 사용하고 있습니다. 무작위로 소스를 조사 할 때 last 구현을 보았고 IntelliJ IDE에서 TraversableLike.last 구현으로 이동했습니다. 구현은 결국 모든 요소를 ​​통과하여 결국 마지막 요소에 도달합니다.인덱싱 된 크기 복잡함

이것은 나에게는 놀라운 것이 었으며, 지금이 이유가 무엇인지 확신 할 수 없습니다. last이 실제로이 방법으로 구현 되었습니까? 어떤 이유로 last을 IndexedSeq (또는 아마 IndexedSeqLike)에 대해 구현하지 못하게 할 수 있습니까? 특정 순서가 반드시 인덱스 조회 빠르게 순회 이상하지 않는 인덱스 액세스를 지원한다는 사실을 -

(그것은 단지 TraversableLike에서 상속) last를 대체하지 않습니다

출처

2015-01-21 Suma

답변

1

IndexedSeq은 임의 요소에 대해 일정한 액세스 시간을가집니다. LinearSeq에는 선형 시간이 있습니다. TraversableLike은 공통 인터페이스이며, 당신은 IndexedSeqOptimized 특성 내부 오버라이드 (override)이야 찾을 수 있습니다 :

빠른 랜덤 액세스의 가정하에 여러 가지 방법의 구현을 최적화 유형 IndexedSeq[A]의 인덱스 시퀀스 템플릿의 특성을.

def last: A = if (length > 0) this(length - 1) else super.last

또한 Vector.getElem 내부의 빠른 랜덤 액세스 구현을 찾을 수는 - 그렇게 일반적으로는 (1) apply에 대한 O의 높은 분기 인자로 배열의 나무를 사용합니다. 그것은 IndexedSeqOptimized를 사용하지 않지만, last를 오버라이드 (override) 자신이 있습니다

override /*TraversableLike*/ def last: A = { 
    if (isEmpty) throw new UnsupportedOperationException("empty.last") 
    apply(length-1) 
}

는 그래서 스칼라 내부에 대한 매우 일반적인 스칼라 컬렉션, 내부에 약간의 혼란입니다. 어쨌든 last은 IndexedSeqs입니다. O (1) 사실과 같은 까다로운 콜렉션 아키텍처.

스칼라 컬렉션의 복잡함은 실제로 활성화 된 주제입니다. 스칼라의 콜렉션 프레임 워크 비판에 대한 이야기 ​​(및 슬라이드)는 Paul Phillips: Scala Collections: Why Not?에서 찾을 수 있으며 Paul Phillips는 his alternate version of std을 개발 중입니다.

출처

2015-01-21 16:36:50 dk14

관련 문제

 관련 문제