다이내믹 어레이

Dynamic array
기하학적 확장을 사용하여 동적 배열 끝에 여러 값이 삽입됩니다.회색 셀은 확장을 위해 예약된 공간을 나타냅니다.대부분의 삽입은 고속(정수 시간)이지만, 재할당의 필요성(δ(n) 시간, 거북이 라벨)으로 인해 속도가 느린 것도 있습니다.최종 어레이의 논리적 크기와 용량이 표시됩니다.

컴퓨터 과학에서 동적 배열, 확장 가능한 배열, 크기 조정 가능한 배열, 동적 테이블, 가변 배열 또는 배열 목록은 요소를 추가하거나 제거할 수 있는 랜덤 액세스의 가변 크기 목록 데이터 구조입니다.이것은 많은 현대 주류 프로그래밍 언어의 표준 라이브러리와 함께 제공됩니다.동적 어레이는 할당 시 지정해야 하는 고정 용량을 가진 정적 어레이의 한계를 극복합니다.

다이내믹 어레이는 동적으로 할당된 어레이와 동일하지 않습니다.다만, 다이내믹 어레이는 이러한 고정 사이즈의 어레이를 [1]백엔드로 사용할 수 있습니다.

한정된 크기의 동적 어레이 및 용량

일반적으로 즉시 필요한 요소의 수보다 큰 고정 크기의 배열을 할당함으로써 단순한 동적 배열을 구성할 수 있습니다.동적 배열의 요소는 기본 배열의 시작 부분에 인접하게 저장되며, 기본 배열의 끝에 있는 나머지 위치는 예약되거나 사용되지 않습니다.예약된 공간을 사용하여 동적 배열 끝에 이 공간이 완전히 사용될 때까지 일정 시간 내에 요소를 추가할 수 있습니다.모든 공간을 사용하고 요소를 추가해야 할 경우 기본 고정 크기 어레이의 크기를 늘려야 합니다.일반적으로 크기 조정에는 새로운 기본 어레이를 할당하고 원래 어레이에서 각 요소를 복사해야 하므로 비용이 많이 듭니다.크기를 조정할 필요가 없기 때문에 동적 배열의 끝에서 일정 시간 내에 요소를 제거할 수 있습니다.동적 어레이 컨텐츠에 사용되는 요소의 수는 논리적 크기 또는 크기이며, 기본 어레이의 크기는 동적 어레이의 용량 또는 물리적 크기라고 하며,[2] 이는 데이터를 재배치하지 않고 가능한 최대 크기입니다.

최대 논리 사이즈가 사양에 따라 고정되어 있거나 어레이를 할당하기 전에 계산할 수 있는 어플리케이션에서는 고정 크기 어레이로 충분합니다.다음과 같은 경우 동적 어레이가 선호될 수 있습니다.

  • 어레이가 할당되기 전에 최대 논리 크기를 알 수 없거나 계산하기 어렵습니다.
  • 사양에 의해 주어진 최대 논리 사이즈가 변경될 가능성이 있는 것으로 간주됩니다.
  • 동적 어레이 크기 변경에 따른 상각 비용은 성능 또는 응답성에 큰 영향을 미치지 않습니다.

기하학적 확장 및 상각 비용

여러 번 크기를 조정하는 데 드는 비용을 피하기 위해 동적 어레이는 크기가 두 배로 증가하는 등 큰 폭으로 크기를 조정하고 향후 확장을 위해 예약된 공간을 사용합니다.마지막에 요소를 추가하는 조작은 다음과 같이 동작할 수 있습니다.

기능. 삽입 종료(다이너레이 a, 요소 e)     한다면 (a.크기 == a.용량.)         // 현재 용량의 2배로 크기 조정:         a.용량. ← a.용량. * 2          // (여기서 내용을 새 메모리 위치에 복사)     a[a.크기] ← e     a.크기 ← a.크기 + 1

n개의 요소가 삽입되면 용량은 기하급수를 형성합니다.배열을 일정한 비율로 확장하면 n개의 요소를 삽입하는 데 전체적으로 O(n) 시간이 소요됩니다.즉, 각 삽입에는 상각된 상수 시간이 소요됩니다.또한 많은 동적 어레이는 기본 스토리지의 크기가 용량의 30%와 같은 특정 임계값 미만으로 떨어지면 일부 스토리지의 할당을 취소합니다.이 문턱값은 히스테리시스(반복적인 증가 및 축소를 방지하기 위한 안정적인 밴드 제공)를 제공하고 상각된 고정 비용과 함께 삽입 및 분리 시퀀스의 혼합을 지원하려면 1/a보다 엄격하게 작아야 합니다.

동적 배열은 상각 [3][4]분석을 가르칠 때 흔히 볼 수 있는 예입니다.

성장률

동적 어레이의 성장 인자는 시공간 균형 및 메모리 할당 장치 자체에 사용되는 알고리즘 등 여러 요소에 따라 달라집니다.성장인자 a에 대해 삽입 동작당 평균 시간은 a/(a-1) 정도이며, 낭비 셀 수는 (a-1)n[citation needed] 이상으로 제한된다.메모리 할당기가 First-Fit 할당 알고리즘을 사용하는 경우, a=2와 같은 성장 요인 값으로 인해 상당한 양의 메모리를 사용할 [5]수 있더라도 동적 어레이 확장의 메모리가 부족해질 수 있습니다.이상적인 성장요인치에 대해서는 1.5의 [6]가치뿐만 아니라 황금비율 제안도 포함해 다양한 논의가 있었다.그러나 대부분의 교과서에서는 단순성과 분석 목적으로 [3][4]a = 2를 사용합니다.

다음은 일반적인 몇 가지 구현에서 사용되는 성장 요인입니다.

실행 성장률(a)
Java 어레이[1] 리스트 1.5 (3/2)
Python PyListObject[7] 최대 1.125 (n + (n >> 3)
Microsoft Visual C++ 2013[8] 1.5 (3/2)
G++ 5.2.0[5] 2
쨍그랑 3[5].6 2
페이스북의 어리석음/FBVector[9] 1.5 (3/2)
러스트벡[10] 2
슬라이스[11] 이동 1.25 ~ 2 사이
Nim[12] 시퀀스 2

성능

목록 데이터 구조 비교
훔쳐보다
(인덱스)		 변환(삽입 또는 삭제) 여유 공간,
평균
시작 끝. 가운데
링크 리스트 θ(n) θ(1) δ(1), 알려진 엔드 요소
δ(n), 알 수 없는 엔드 요소		 Peek 시간 +
θ(1)[13][14] 		θ(n)
어레이 θ(1) — — — 0
다이내믹 어레이 θ(1) θ(n) θ(1)상각 θ(n) θ([15]n)
밸런스 트리 δ(로그 n) δ(로그 n) δ(로그 n) δ(로그 n) θ(n)
랜덤 액세스리스트 δ([16]로그 n) θ(1) --[16] --[16] θ(n)
해시 어레이 트리 θ(1) θ(n) θ(1)상각 θ(n) θ(nn)

동적 어레이는 어레이와 유사한 성능을 가지며 요소를 추가 및 제거하는 새로운 작업을 추가합니다.

  • 특정 인덱스에서 값 가져오기 또는 설정(정수 시간)
  • 요소 순서대로 반복(선형 시간, 캐시 성능 우수)
  • 배열 중간에 요소 삽입 또는 삭제(선형 시간)
  • 배열 끝에 요소 삽입 또는 삭제(상각된 일정 시간)

동적 어레이는 참조 및 데이터 캐시 사용률, 콤팩트성(메모리 사용량이 적음), 랜덤 액세스 등 어레이의 많은 이점을 누릴 수 있습니다.일반적으로 크기 및 용량에 대한 정보를 저장하기 위해 약간의 추가 오버헤드만 고정됩니다.따라서 동적 어레이는 캐시에 적합한 데이터 구조를 구축하기 위한 매력적인 도구가 됩니다.그러나 Python이나 Java와 같은 참조 시멘틱스를 적용하는 언어에서는 동적 배열은 일반적으로 실제 데이터를 저장하지 않고 메모리의 다른 영역에 있는 데이터에 대한 참조를 저장합니다.이 경우 어레이 내의 항목에 순차적으로 액세스하려면 실제로 메모리의 여러 비인접 영역에 액세스해야 합니다.따라서 이 데이터 구조의 캐시 친화성은 많은 이점을 잃게 됩니다.

링크 리스트에 비해 다이내믹 어레이는 인덱싱(시간 대 선형 시간)이 빨라지고 참조 인접성이 향상되어 일반적으로 반복이 빨라집니다.다이나믹 어레이는 다음 요소를 모두 이동해야 하지만 링크 리스트는 일정 시간에 이 작업을 수행할 수 있기 때문에 임의의 위치에 삽입 또는 삭제하기 위해 선형 시간이 필요합니다.이 단점은 다음 Variants에서 설명하는 갭버퍼와 계층형 벡터에 의해 완화됩니다.또, 고도로 단편화된 메모리 영역에서는, 큰 다이나믹 어레이를 위한 인접 공간을 찾는 것이 비싸거나 불가능할 수 있지만, 링크 리스트는 데이터 구조 전체를 인접해 격납할 필요가 없다.

밸런스 트리는 동적 어레이와 링크드 리스트의 모든 조작을 합리적으로 효율적으로 제공하면서 리스트를 격납할 수 있지만 이론적으로나 실제로는 비인접 스토리지와 트리 트래버설/조작 오버헤드에 의해 말미에 삽입 및 목록 상에서의 반복 모두 동적 어레이보다 느리다.

변종

갭 버퍼는 동적 어레이와 비슷하지만 동일한 임의 위치 근처에서 클러스터된 삽입 및 삭제 작업을 효율적으로 수행할 수 있습니다.일부 디큐 구현에서는 어레이 디큐를 사용합니다.이것에 의해, 한쪽 끝만이 아니고, 양쪽 끝에서 상각된 일정한 시간 삽입/탈부착이 가능하게 됩니다.

Goodrich는[17] 계층형 벡터라고 불리는 동적 어레이 알고리즘을 제시했습니다.이 알고리즘은 어레이 내의 임의의 장소에서 삽입 및1/k 삭제 시 O(n) 퍼포먼스를 제공하며 O(k) get 및 set을 제공합니다.여기서 k † 2는 상수 파라미터입니다.

Hashed Array Tree(HAT; 해시 어레이 트리)는 [18]Sitarski가 1996년에 발표한 다이내믹 어레이 알고리즘입니다.해시된 배열 트리는 n개의 저장 공간을1/2 낭비합니다. 여기서 n은 배열 내의 요소 수입니다.이 알고리즘은 해시 어레이 트리의 끝에 일련의 개체를 추가할 때 O(1)의 상각된 성능을 가집니다.

Brodnik 등은 1999년 [19]논문에서 계층형 다이내믹 어레이 데이터 구조에 대해 설명하고 있습니다.이 데이터 구조는 어느 시점에서나 n개의 요소를 위한 공간만을1/2 낭비하고 있습니다.동적 어레이가 상각된 일정 시간을 유지하려면 이 많은 공간을 낭비해야 한다는 것을 보여줍니다.또한 버퍼의 증대와 축소가 상각되었을 뿐만 아니라 최악의 경우 고정시간인 변형을 제시합니다.

Bagwell(2002)[20]은 동적 어레이를 구현하기 위해 적응할 수 있는 VList 알고리즘을 제시했다.

크기 조정 가능한 어레이(크기 조정 가능한 어레이의 '최악의 구현'이라고도 함)는 어레이에 추가된 각 항목에 대해 재할당을 호출하여 어레이에 할당된 크기를 포함하는 모든 데이터에 대해 정확하게 유지합니다.크기 조정 가능한 어레이는 C에서 크기 조정 가능한 어레이를 구현하는 가장 간단한 방법입니다.메모리 낭비는 없지만 어레이 끝에 추가하는 데는 항상 Ω([18][21][22][23][24]n) 시간이 걸립니다.어레이의 사이즈를 변경할 때마다 어레이의 용량을 미리 할당("폐기")하여 크기가 조정 가능한 어레이보다 몇 배 고속화합니다. 어레이 끝에 추가하는 데 걸리는 시간은 여전히 Ω(n)이지만 상수는 훨씬 작습니다.공간 제약이 있는 애플리케이션으로 다수의 소형 크기 조정 가능한 어레이를 필요로 하는 경우에는 크기 조정 가능한 어레이와 선형 확장이 가능한 어레이가 없는 어레이가 유용할 수 있습니다.또, 이러한 어레이는, 다이나믹 어레이의 [25]비약적인 증가를 가져오는 교육적인 예로서도 많이 사용되고 있습니다.

언어 지원

C++와 Rust의std::vec::Vec다이나믹 어레이의 실장입니다.ArrayList[26] Java API 및 에 부속된 클래스입니다.NET [27]프레임워크

범용List<>의 버전 2.0과 함께 제공된 클래스입니다.NET Framework는 다이내믹 어레이에서도 구현됩니다.스몰톡스OrderedCollection는 다이내믹 스타트 인덱스와 엔드 인덱스를 가진 다이내믹 어레이로 첫 번째 요소의 삭제도 O(1)가 됩니다.

파이썬의list데이터형 실장은 증가 패턴이 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...인 [28]동적 어레이입니다.

Delphi와 D는 언어의 핵심에 동적 어레이를 구현합니다.

Ada의 범용 패키지는 특정 서브타입에 대한 동적 어레이 구현을 제공합니다.

Perl 및 Ruby와 같은 많은 스크립트 언어들은 기본 데이터 유형으로 동적 배열을 제공합니다.

C에는 다음과 같은 여러 크로스 플랫폼 프레임워크가 동적 어레이 구현을 제공합니다.CFArray그리고.CFMutableArray코어 파운데이션과GArray그리고.GPtrArrayGLIB로 설정합니다.

Common Lisp는 빌트인을 구성할 수 있도록 함으로써 크기 조정 가능한 벡터를 기본적으로 지원합니다.array조절 가능한 것으로 입력하고 주입구를 사용하여 삽입 위치를 입력합니다.

레퍼런스

  1. ^ a b 예를 들어 java.util의 소스 코드를 참조하십시오.OpenJDK 6의 ArrayList 클래스.
  2. ^ Lambert, Kenneth Alfred (2009), "Physical size and logical size", Fundamentals of Python: From First Programs Through Data Structures, Cengage Learning, p. 510, ISBN 978-1423902188
  3. ^ a b 를 클릭합니다Goodrich, Michael T.; Tamassia, Roberto (2002), "1.5.2 Analyzing an Extendable Array Implementation", Algorithm Design: Foundations, Analysis and Internet Examples, Wiley, pp. 39–41.
  4. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "17.4 Dynamic tables". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 416–424. ISBN 0-262-03293-7.
  5. ^ a b c "C++ STL vector: definition, growth factor, member functions". Archived from the original on 2015-08-06. Retrieved 2015-08-05.
  6. ^ "vector growth factor of 1.5". comp.lang.c++.moderated. Google Groups. Archived from the original on 2011-01-22. Retrieved 2015-08-05.
  7. ^ github.com/python/cpython/,에서 2020-03-23을 취득한 객체 구현을 나열합니다.
  8. ^ Brais, Hadi. "Dissecting the C++ STL Vector: Part 3 - Capacity & Size". Micromysteries. Retrieved 2015-08-05.
  9. ^ "facebook/folly". GitHub. Retrieved 2015-08-05.
  10. ^ "rust-lang/rust". GitHub. Retrieved 2020-06-09.
  11. ^ "golang/go". GitHub. Retrieved 2021-09-14.
  12. ^ "The Nim memory model". zevv.nl. Retrieved 2022-05-24.
  13. ^ 1일차 기조연설 - Bjarne Stroustrup : GoingNative 2012에서 C++11 Style on GoingNative 45분 또는 44일
  14. ^ 수치 계산: kjellkod에서 다시는 코드에 링크 리스트를 사용하지 않는 이유.wordpress.com
  15. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF), Department of Computer Science, University of Waterloo
  16. ^ a b c Chris Okasaki (1995). "Purely Functional Random-Access Lists". Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture: 86–95. doi:10.1145/224164.224187.
  17. ^ Goodrich, Michael T.; Kloss II, John G. (1999), "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences", Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 1663: 205–216, doi:10.1007/3-540-48447-7_21, ISBN 978-3-540-66279-2
  18. ^ a b Sitarski, Edward (September 1996), "HATs: Hashed array trees", Algorithm Alley, Dr. Dobb's Journal, 21 (11)
  19. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (PDF) (Technical Report CS-99-09), Department of Computer Science, University of Waterloo
  20. ^ Bagwell, Phil (2002), Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays, EPFL
  21. ^ 마이크 램."다이나믹 어레이"
  22. ^ '아모르티드 타임'
  23. ^ "해시 어레이 트리: 어레이의 효율적인 표현"
  24. ^ "복잡함의 다른 개념"
  25. ^ 피터 칸코프스키."C의 다이내믹 어레이"
  26. ^ Javadoc onArrayList
  27. ^ Array List 클래스
  28. ^ listobject.c(github.com)

외부 링크