[SCALA] 언제 스칼라에 벡터를 선택해야합니까?

언제 스칼라에 벡터를 선택해야합니까?

이 벡터는 스칼라 컬렉션 파티에 늦었다, 모든 영향력있는 블로그 게시물은 이미 떠난 것으로 보인다.

자바에서는 ArrayList의 기본 모음입니다 - 나는 LinkedList의를 사용하지만이 알고리즘을 통해 생각하고 최적화 할 정도로 관심을 한 경우에만 있습니다. 스칼라에서 나는 내 기본 서열로 벡터를 사용하거나 목록이 실제로 더 적합한 경우 해결하려고 노력해야 하는가?

해결법

1. ==============================

   1.일반적으로 벡터를 사용하여 기본. 그것은 거의 모든 메모리 효율보다 큰 사소한 크기의 시퀀스 등을위한 목록보다 더 빠르다. 다른 컬렉션에 비해 벡터의 상대적 성능의 설명서를 참조하십시오. 벡터와 함께가는 몇 가지 단점이 있습니다. 특히 :

   일반적으로 벡터를 사용하여 기본. 그것은 거의 모든 메모리 효율보다 큰 사소한 크기의 시퀀스 등을위한 목록보다 더 빠르다. 다른 컬렉션에 비해 벡터의 상대적 성능의 설명서를 참조하십시오. 벡터와 함께가는 몇 가지 단점이 있습니다. 특히 :

   스칼라 2.10 전에 또 다른 단점은 지원 일치하는 패턴이 목록에 더이었다, 그러나 + 일반화와 함께이 2.10에 정류되었습니다 및 : + 추출기.

   당신이 개념적으로 시퀀스의 어떤 종류가 있습니까 :이 문제에 접근보다 추상적, 대수적 방법이있다? 또한, 당신은 개념적으로 그것으로 무엇을? 나는 [A] 옵션을 반환하는 함수를 참조하는 경우, 그 기능은 그 도메인의 일부 구멍이 있습니다 (따라서 부분입니다) 알고있다. 우리는 컬렉션에이 같은 논리를 적용 할 수 있습니다.

   I 유형 목록의 순서가있는 경우 [A], 나는 효과적으로 두 가지를 주장하고있다. 우선, 제 알고리즘 (및 데이터) 전체 스택 구성된다. 둘째, 내가이 컬렉션 할거야 유일한 일이 가득 것을 주장하고, O (n)을 순회. 이 두 사람은 정말 손에 손을 이동합니다. 내가 형 벡터의 무언가가 있다면 반대로, [A], 내가 주장하고있는 유일한 것은 내 데이터가 잘 정의 된 순서와 유한 길이를 가지고 있다는 것입니다. 따라서, 주장은 벡터와 약한, 이것은 그 유연성에 연결됩니다.

2. ==============================

   2.알고리즘은 전적으로 ::, 머리와 꼬리로 구현 될 수 있다면 음, 목록은 매우 빠르게 할 수 있습니다. 내가 배열 대신 목록을 생성하여 자바의 분할을 이길 때, 아주 최근에 그 객체 수업이 있고, 다른 아무것도 이길 수 없었다.

   알고리즘은 전적으로 ::, 머리와 꼬리로 구현 될 수 있다면 음, 목록은 매우 빠르게 할 수 있습니다. 내가 배열 대신 목록을 생성하여 자바의 분할을 이길 때, 아주 최근에 그 객체 수업이 있고, 다른 아무것도 이길 수 없었다.

   그러나 목록 근본적인 문제가있다 : 그것은 병렬 알고리즘 작동하지 않습니다. 여러 개의 세그먼트로 목록을 분할하거나 효율적인 방법으로 그것을 다시 연결할 수 없습니다.

   이 훨씬 더 병렬 처리를 처리 할 수있는 컬렉션의 다른 종류입니다 -와 벡터 중 하나입니다. 벡터는 또한 훌륭한 지역이있다 -하지 않는 목록 - 어떤 알고리즘을위한 진짜 플러스가 될 수있다.

   그래서, 모든 것을 고려, 벡터는 바람직 다른 컬렉션 중 하나 만들어 특정 고려 사항이없는 경우 최선의 선택 - 당신이 원하는 경우 예를 들어, 당신은 스트림을 선택할 수 있습니다 게으른 평가 및 캐싱 (반복자 캐시 빠르지 않지만 않습니다) 또는 목록 알고리즘은 자연스럽게 내가 언급 한 작업으로 구현됩니다.

   알고리즘을 병렬로 실행할 수있는 경우 :), 또는 GenSeq 또는 GenIndexedSeq : 그건 그렇고, 당신이 특정 같은 목록의 같은 API의 조각을 (원하는하지 않는 서열 또는 IndexedSeq을 사용하는 것이 바람직하다.

3. ==============================

   3.당신이 순서를 원하는 경우 불변의 컬렉션을 들어, 기본 결정은 성능에 대해 서로 다른 보장을 제공 IndexedSeq 또는 LinearSeq을 사용할지 여부입니다. IndexedSeq 요소와 빠른 길이 작업의 빠른 랜덤 액세스를 제공합니다. LinearSeq 머리를 통해 첫 번째 요소에 대한 빠른 액세스를 제공하지만, 또한 빠른 꼬리 작업이 있습니다. 합니다 (서열 번호 문서에서 발췌.)

   당신이 순서를 원하는 경우 불변의 컬렉션을 들어, 기본 결정은 성능에 대해 서로 다른 보장을 제공 IndexedSeq 또는 LinearSeq을 사용할지 여부입니다. IndexedSeq 요소와 빠른 길이 작업의 빠른 랜덤 액세스를 제공합니다. LinearSeq 머리를 통해 첫 번째 요소에 대한 빠른 액세스를 제공하지만, 또한 빠른 꼬리 작업이 있습니다. 합니다 (서열 번호 문서에서 발췌.)

   IndexedSeq 위해 당신은 일반적으로 벡터를 선택하는 것입니다. 범위 및 WrappedStrings도 IndexedSeqs 있습니다.

   LinearSeq 위해 당신은 일반적으로 목록 또는 게으른 해당 스트림을 선택합니다. 다른 예로는 대기열 및 스택입니다.

   그래서 자바 측면에서의 ArrayList는 스칼라의 벡터와 유사하게 사용하고, LinkedList의 유사 스칼라의 목록에. 스칼라 당신은 같은 목록을 조작하는이 기능을 사용하는 경향이 반복하는 등, 접이식, 매핑과 같은 순서의 통과를 포함 기능에 대한 더 나은 지원을 가지고 있기 때문에하지만 스칼라에서 나는, 벡터보다 더 자주 목록을 사용하는 경향이있다 전체가 아닌 임의의 개별 요소를 액세스.

4. ==============================

   4.여기에 문 중 일부는 스칼라에서 immutable.Vector는 ArrayList를 같은 어떤 것을 특히 생각 혼동하거나 잘못이다. 목록 및 벡터는 모두 불변, 지속적으로 (즉, "싼 수정 된 사본을 얻을") 데이터 구조입니다. 이 가변 데이터 구조에 대한 자신의 수도로 합리적인 기본 선택은 없지만, 오히려 알고리즘이 무엇을하고 있는지에 따라 달라집니다. 벡터는도 32의 노드 탐색 트리의 일종이다, 즉 기본-32 정수 트라이 동안 목록은 단일 연결 목록입니다. 이 구조를 이용하여, 벡터가 비교적 빠른 일반적인 동작을 제공 할 수있는, 즉 O에 (log_32 (N)). 즉 헤드 / 테일의 앞에 추가, 추가, 업데이트 랜덤 액세스, 분해 작동합니다. 순차적으로 반복 선형이다. 반면에 목록은 헤드 / 테일 선형 반복하고 일정 시간 앞에 추가, 분해를 제공합니다. 다른 모든 일반 선형 시간이 걸립니다.

   여기에 문 중 일부는 스칼라에서 immutable.Vector는 ArrayList를 같은 어떤 것을 특히 생각 혼동하거나 잘못이다. 목록 및 벡터는 모두 불변, 지속적으로 (즉, "싼 수정 된 사본을 얻을") 데이터 구조입니다. 이 가변 데이터 구조에 대한 자신의 수도로 합리적인 기본 선택은 없지만, 오히려 알고리즘이 무엇을하고 있는지에 따라 달라집니다. 벡터는도 32의 노드 탐색 트리의 일종이다, 즉 기본-32 정수 트라이 동안 목록은 단일 연결 목록입니다. 이 구조를 이용하여, 벡터가 비교적 빠른 일반적인 동작을 제공 할 수있는, 즉 O에 (log_32 (N)). 즉 헤드 / 테일의 앞에 추가, 추가, 업데이트 랜덤 액세스, 분해 작동합니다. 순차적으로 반복 선형이다. 반면에 목록은 헤드 / 테일 선형 반복하고 일정 시간 앞에 추가, 분해를 제공합니다. 다른 모든 일반 선형 시간이 걸립니다.

   때문에 벡터에 대한 높은이 벡터는 거의 모든 경우에 목록에 대한 좋은 대체 것처럼처럼 보일 수도 있지만, 앞에 추가, 분해 및 반복은 종종 기능 프로그램의 순서에 중요한 작업이며, 이러한 작업의 상수 (많이)입니다 그것의 더 복잡한 구조. 그래서 반복이 약 두 배 빠른 목록, 앞에 추가가 / 꼬리 약 2 배 빠른 벡터의 약 10 배 빠른 목록 및 생성에에 이동으로부터 약 100 배 빠른 목록에 머리에 분해하고, 몇 가지 측정을했다. (당신이 하나 빌더를 사용하는 대신에 붙이는 또는 요소 하나를 추가로 구축 할 때 벡터가 한 번에 32 개 개의 요소의 배열을 할당 할 수 있기 때문에, 아마). 물론 (랜덤 액세스 또는 추가) 벡터에 나열하지만, ​​효율적으로 일정 시간에 선형의 시간이 걸릴 모든 작업은 큰 목록에 엄청나게 느린 될 것입니다.

   그래서 우리는 어떤 데이터 구조를 사용 하는가? 기본적으로 네 가지 일반적인 경우가 있습니다 :

5. ==============================

   5.많은 랜덤 액세스 무작위 돌연변이, Vector를 포함하는 상황에서 (또는 - 문서가 말한대로 - 서열은) 좋은 타협 될 것으로 보인다. 이것은 성능 특성 제안에도 효과가있을 것이다.

   많은 랜덤 액세스 무작위 돌연변이, Vector를 포함하는 상황에서 (또는 - 문서가 말한대로 - 서열은) 좋은 타협 될 것으로 보인다. 이것은 성능 특성 제안에도 효과가있을 것이다.

   또한, 벡터 클래스는 완전한 객체에 대한 기록 중 복사를 할 필요가 없기 때문에 많은 데이터 중복없이 분산 환경에서 잘 놀 것 같다. (참조 : http://akka.io/docs/akka/1.1.3/scala/stm.html#persistent-datastructures)

6. ==============================

   6.당신은 변함 프로그램이고 랜덤 액세스해야하는 경우, 서열은 (당신이 종종 실제로 할 세트를 원하지 않는다면)가는 방법이다. 그것의 작업을 병렬화 할 수없는 것을 제외하고 그렇지 않으면 목록, 잘 작동합니다.

   당신은 변함 프로그램이고 랜덤 액세스해야하는 경우, 서열은 (당신이 종종 실제로 할 세트를 원하지 않는다면)가는 방법이다. 그것의 작업을 병렬화 할 수없는 것을 제외하고 그렇지 않으면 목록, 잘 작동합니다.

   당신은 불변의 데이터 구조를 필요로하지 않는 경우는 ArrayList의에 스칼라 상응이기 때문에, ArrayBuffer 스틱.

from https://stackoverflow.com/questions/6928327/when-should-i-choose-vector-in-scala by cc-by-sa and MIT license