ArrayBuffer는 메모리에서 어떻게 작동합니까?

Question

내 프로그램에서 ArrayBuffer를 사용하여 숫자 목록을 유지하려고합니다. 대기열로 사용하고 싶습니다. 매번 목록의 첫 번째 항목을 삭제하고 사용하십시오. 그런 다음 첫 번째 항목을 삭제할 때마다 큐에있는 다른 모든 숫자가 한 자리 이동하는 지 궁금합니다. 다음에 다시 항목 (0)을 읽을 수 있습니까?

Answer 1

는 스칼라 source code 또는 ArrayBuffer로 보면 remove의 다음 구현 볼 수 있습니다 :

/** Removes the element on a given index position. It takes time linear in 
    * the buffer size. 
    * 
    * @param n  the index which refers to the first element to delete. 
    * @param count the number of elements to delete 
    * @throws Predef.IndexOutOfBoundsException if `n` is out of bounds. 
    */ 
    override def remove(n: Int, count: Int) { 
    require(count >= 0, "removing negative number of elements") 
    if (n < 0 || n > size0 - count) throw new IndexOutOfBoundsException(n.toString) 
    copy(n + count, n, size0 - (n + count)) 
    reduceToSize(size0 - count) 
    } 

그래서 제거 된 요소가 더 이상 배열에 참여할 수 있으나, 실제로 제거 수단 모든 요소를 ​​복사 (정의에서 "이동")하고, 더 긴 배열의 경우 속도가 느려집니다.

Answer 2

ArrayBuffer은 기본적으로 Buffer의 편리한 방법을 모두 구현하는 배열입니다.

설명대로 작동합니다. 요소를 제거하면 나머지 요소는 모두 "채우기"로 이동하고 문서에 명시된 것처럼 특히 첫 번째 요소를 제거하는 경우 다소 시간이 걸릴 수 있습니다.

추가, 업데이트 및 무작위 액세스에는 일정 시간 (상환 시간)이 소요됩니다. 앞부분과 뒤쪽은 버퍼 크기가 선형입니다.

따라서 ArrayBuffer을 큐로 사용하지 않는 것이 좋습니다.

실제로 최상의 옵션은 질문입니다. Queue을 사용하면됩니다. 그것은, 잘 ... 대기열로 설계되었습니다!

Answer 3

왜 대기열을 대기열로 사용하지 않습니까?Java Queue

그것은 좋은 방법은 설문 조사()라는 것이있다 (큐가 비어있는 경우 취득하고이 큐의 선두를 취득 해 삭제, 또는 null를 돌려줍니다.)

무엇을 그것 아닌가요 당신 필요한 것? 어레이 솔루션보다 성능이 좋습니다.

Answer 4

(예 : 런타임 (캐시 위치) 또는 저장 (다음 포인터 없음) 효율성 이유로 인해) 배열 기반 데이터 구조를 사용하려는 경우 java.util.ArrayDeque을 고려할 수 있습니다. 이 클래스는, 꽉 차있을 때 크기가 조정되는 원형 배열을 효과적으로 구현합니다. poll() (검색하고 첫 번째 요소를 제거) 방법은 간단하게 시작을 증가시켜 구현은

사용하지 수 있도록 단점은,이 클래스가 java.util.Queue 인터페이스를 구현하더라도, scala.collection.mutable.Queue에는 암시 적 변환이 없다는 것을,이다

오프셋 map과 같은 스칼라 컬렉션 메서드

참고 : 스칼라에는 2.11부터 Deque 인터페이스가없고 ArrayDeque 구현 만 남겨 둡니다.