그것은 Vector스칼라 컬렉션 파티에 늦었 던 것으로 보이며 모든 영향력있는 블로그 게시물은 이미 떠났습니다.
Java ArrayList에서는 기본 모음입니다 LinkedList. 알고리즘을 통해 생각하고 최적화하기에 충분히주의를 기울 였을 때만 사용할 수 있습니다 . 스칼라에서 Vector기본값 으로 사용 Seq하거나 List실제로 더 적절한 시기를 해결 해야합니까?
답변
일반적으로 기본값은을 사용 Vector합니다. 그것은보다 더 빨리이다 List에 대한 거의 보다 큰 사소한 크기의 시퀀스에 대한 모든 메모리 효율적이고. 다른 컬렉션과 비교하여 Vector의 상대적 성능에 대한 이 설명서 를 참조하십시오 . 와 함께 몇 가지 단점이 있습니다 Vector. 구체적으로 특별히:
- 헤드의 업데이트 속도가 느리다
List(생각할 수는 없지만)
Scala 2.10 이전의 또 다른 단점은 패턴 일치 지원이 더 List좋았지 만 일반화 +:및 :+추출기를 사용 하여 2.10에서 수정되었습니다 .
이 질문에 접근하는 더 추상적이고 대수적인 방법이 있습니다. 개념적으로 어떤 종류의 순서 가 있습니까? 또한 개념적으로 무엇 을하고 있습니까? 를 반환하는 함수를 보면 Option[A]해당 함수에 도메인에 약간의 구멍이 있음을 알 수 있습니다 (따라서 부분적 임). 이 같은 논리를 컬렉션에 적용 할 수 있습니다.
type의 시퀀스가 있으면 List[A]효과적으로 두 가지를 주장합니다. 첫째, 내 알고리즘 (및 데이터)은 완전히 스택 구조입니다. 두 번째로, 나는이 컬렉션과 함께 할 유일한 것은 O (n) 순회라고 주장합니다. 이 두 사람은 실제로 함께합니다. 반대로, type의 무언가가있는 경우 Vector[A], 내가 주장 하는 유일한 것은 데이터가 잘 정의 된 순서와 유한 길이를 가지고 있다는 것입니다. 따라서 어설 션은로 약해지고 Vector유연성이 향상됩니다.
답변
음,이 List알고리즘은 전적으로 구현 될 수있는 경우에 매우 빠르게 할 수있다 ::, head하고 tail. 나는 최근 split에 List대신을 생성하여 Java를 이길 때 객체에 대한 교훈을 얻었고 다른 것으로 그것을 이길 Array수 없었습니다.
그러나 List근본적인 문제가 있습니다. 병렬 알고리즘에서는 작동하지 않습니다. List효율적인 방식으로 여러 세그먼트로 분할 하거나 다시 연결할 수 없습니다 .
병렬 처리를 훨씬 더 잘 처리 할 수있는 다른 종류의 컬렉션이 있으며 그 Vector중 하나입니다. Vector또한 지역에 따라 다릅니다- List그렇지 않습니다-일부 알고리즘에는 실제로 도움이 될 수 있습니다.
그래서, 모든 것을 고려, Vector최선의 선택을 하지 않는 한 당신은 바람직 다른 컬렉션 중 하나 만들어 특정 고려 사항이 -, 당신이 선택할 수 있습니다 예를 들어 Stream당신이 게으른 평가 및 캐싱을 원하는 경우는 ( Iterator빠른하지만 캐시하지 않습니다), 또는 List경우 알고리즘은 언급 한 작업으로 자연스럽게 구현됩니다.
그런데, 그것을 사용하는 것이 바람직하다 Seq또는 IndexedSeq당신이 API의 특정 조각을 (예 : 원하지 않는다면 List의 ::), 또는 GenSeq또는 GenIndexedSeq경우 알고리즘은 병렬로 실행할 수 있습니다.
답변
여기의 문장 중 일부는 혼란 스럽거나 잘못되었습니다. 특히 스칼라의 불변. 벡터는 ArrayList와 같습니다. 리스트와 벡터는 모두 불변적이고 영구적이다 (즉, “수정 된 사본을 얻기 위해 저렴한”데이터 구조). 변경 가능한 데이터 구조에 대한 적절한 기본 선택은 없지만 알고리즘이 수행하는 작업에 따라 다릅니다. List는 단독으로 연결된 목록이며 Vector는 base-32 integer trie입니다. 즉, 등급이 32 인 노드를 가진 일종의 검색 트리입니다.이 구조를 사용하면 Vector는 가장 일반적인 작업을 합리적으로 빠르게 제공 할 수 있습니다 (예 : O (log_32 ( 엔)). 그것은 머리 / 꼬리에 추가, 추가, 업데이트, 임의 액세스, 분해에 작동합니다. 순차적 순서의 반복은 선형입니다. 반면에리스트는 선형 반복과 일정한 시간 프리 펜드, 헤드 / 테일의 분해를 제공합니다.
이것은 거의 모든 경우에 Vector가 List를 대체하는 것처럼 보일 수 있지만, prepend, decomposition 및 iteration은 종종 함수형 프로그램의 시퀀스에서 중요한 작업이며 이러한 연산의 상수는 벡터의 경우 훨씬 높습니다. 더 복잡한 구조로 몇 가지 측정을 수행했기 때문에 반복이 목록보다 약 두 배 빠르고, 선행은 목록에서 약 100 배 빠르며, 머리 / 꼬리의 분해는 목록에서 약 10 배 빠르며 트래 버블 가능한 생성은 벡터의 경우 약 2 배 빠릅니다. (이것은 아마도 요소를 하나씩 추가하거나 추가하는 대신 빌더를 사용하여 빌드 할 때 Vector가 32 요소의 배열을 한 번에 할당 할 수 있기 때문일 수 있습니다).
어떤 데이터 구조를 사용해야합니까? 기본적으로 네 가지 일반적인 경우가 있습니다.
- map, filter, fold 등과 같은 연산으로 만 시퀀스를 변환하면됩니다. 기본적으로 중요하지 않습니다. 알고리즘을 일반적으로 프로그래밍해야하며 병렬 시퀀스를 받아들이면 도움이 될 수도 있습니다. 순차적 작업의 경우 목록이 약간 더 빠릅니다. 그러나 최적화해야 할 경우 벤치마킹해야합니다.
- 우리는 많은 랜덤 액세스와 다른 업데이트가 필요하므로 벡터를 사용해야합니다.리스트는 엄청나게 느릴 것입니다.
- 우리는 고전적인 기능적인 방식으로 목록을 다루며 재귀 적 분해에 의해 선행하고 반복하여 목록을 만듭니다. 사용 목록, 벡터는 10-100 배 이상 느려질 것입니다.
- 우리는 기본적으로 필수적이며 목록에서 많은 무작위 액세스를 수행하는 성능 결정 알고리즘을 가지고 있습니다. 빠른 정렬과 같은 : 명령형 데이터 구조 (예 : ArrayBuffer)를 사용하고 로컬에서 데이터를 복사하십시오.
답변
당신이 순서를 원하는 경우 불변의 컬렉션을 들어, 당신의 주요 의사 결정은 사용 여부 IndexedSeq또는 LinearSeq성능에 대해 서로 다른 보증을 제공하는이. IndexedSeq는 요소에 대한 빠른 임의 액세스 및 빠른 길이 작업을 제공합니다. LinearSeq는를 통해 첫 번째 요소에만 빠르게 액세스 할 수 head있지만 빠른 tail작동도 제공합니다. (Seq 문서에서 가져온 것입니다.)
의 경우 IndexedSeq일반적으로을 선택합니다 Vector. Ranges 및 WrappedStrings도 IndexedSeq입니다.
a를 위해 LinearSeq당신은 일반적으로 List또는 그것의 게으른 동등 물을 선택할 것 Stream입니다. 다른 예는 Queues 및 Stacks입니다.
자바 용어 ArrayList로 스칼라 Vector와 LinkedList비슷하게 , 스칼라 와 유사하게 사용됩니다 List. 그러나 Scala에서는 Vector보다 List를 더 자주 사용하는 경향이 있습니다. Scala는 매핑, 접기, 반복 등과 같은 시퀀스 순회를 포함하는 함수를 훨씬 더 잘 지원하기 때문입니다. 이러한 함수를 사용하여 목록을 개별 요소에 무작위로 액세스하지 않고 전체.
답변
많은 무작위 접근과 무작위 돌연변이가 관련된 상황에서 a Vector(또는 문서에서 말했듯이 a Seq)는 좋은 타협으로 보입니다. 이것은 또한 성능 특성이 제안하는 것입니다.
또한 Vector전체 객체에 대해 기록 중 복사를 수행 할 필요가 없으므로 많은 데이터 복제가없는 분산 환경에서 클래스가 훌륭하게 재생되는 것처럼 보입니다. ( http://akka.io/docs/akka/1.1.3/scala/stm.html#persistent-datastructures 참조 )
답변
프로그래밍이 불필요하고 임의 액세스가 필요한 경우 Seq를 사용하는 방법입니다 (실제로 실제로 수행하는 Set을 원하지 않는 한). 그렇지 않으면 List는 작업을 병렬화 할 수 없다는 점을 제외하고는 잘 작동합니다.
불변의 데이터 구조가 필요하지 않은 경우 ArrayBuffer는 ArrayList와 동일한 스칼라이므로 ArrayBuffer를 사용하십시오.