다른 데이터 구조 대신 어레이를 사용하는 이유는 무엇입니까?

다른 데이터 구조 대신 어레이를 사용하는 이유는 무엇입니까?

프로그래밍을 하다 보니 배열이 정보를 저장하는 데 다른 형식보다 더 나은 경우를 본 적이 없습니다.저는 프로그래밍 언어에 추가된 "기능"이 이것을 개선하고 그것들을 대체했다고 정말로 생각했습니다.나는 이제 그들이 교체된 것이 아니라, 말하자면 새로운 생명을 부여받은 것을 봅니다.

그렇다면 기본적으로 어레이를 사용하는 이유는 무엇입니까?

이것은 컴퓨터 관점에서 어레이를 사용하는 이유라기보다는 프로그래밍 관점에서 어레이를 사용하는 이유입니다(미묘한 차이).컴퓨터가 어레이를 사용하여 수행하는 작업은 문제의 핵심이 아니었습니다.

수업 시간으로 돌아갈 시간입니다.오늘날 우리의 고급 관리 언어에서는 이러한 것들에 대해 많이 생각하지 않지만, 동일한 기반 위에 구축되어 있으므로 C에서 메모리가 어떻게 관리되는지 살펴보겠습니다.

시작하기 전에 "포인터"라는 용어가 무엇을 의미하는지 간략하게 설명합니다.포인터는 단순히 메모리의 위치를 "포인트"하는 변수입니다.메모리 영역의 실제 값이 아니라 메모리 주소가 포함되어 있습니다.메모리 블록을 사서함으로 생각합니다.포인터는 해당 사서함의 주소입니다.

C에서 배열은 단순히 오프셋이 있는 포인터이며, 오프셋은 메모리에서 찾을 거리를 지정합니다.O(1) 액세스 시간을 제공합니다.

  MyArray   [5]
     ^       ^
  Pointer  Offset

다른 모든 데이터 구조는 이를 기반으로 구축되거나 저장을 위해 인접 메모리를 사용하지 않으므로 랜덤 액세스 조회 시간이 부족합니다(순차 메모리를 사용하지 않는 것에는 다른 이점이 있음).

예를 들어, 6개의 숫자(6,4,2,3,1,5)가 있는 배열이 있다고 가정하면 메모리는 다음과 같습니다.

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================

배열에서, 우리는 각 요소가 메모리에서 서로 옆에 있다는 것을 알고 있습니다. 어레이 어레이라고 함)MyArray여기서)는 단순히 첫 번째 요소에 대한 포인터입니다.

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^
MyArray

만약 우리가 올려다보고 싶다면,MyArray[4]내부적으로는 다음과 같이 액세스할 수 있습니다.

   0     1     2     3     4 
=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
                           ^
MyArray + 4 ---------------/
(Pointer + Offset)

포인터에 오프셋을 추가하여 어레이의 모든 요소에 직접 액세스할 수 있으므로 어레이의 크기에 관계없이 동일한 시간 내에 모든 요소를 검색할 수 있습니다.이것은 다음을 의미합니다.MyArray[1000]그것을 얻는 것과 같은 시간이 걸릴 것입니다.MyArray[5].

대체 데이터 구조는 연결된 목록입니다.각 포인터가 다음 노드를 가리키는 선형 목록입니다.

========    ========    ========    ========    ========
| Data |    | Data |    | Data |    | Data |    | Data |
|      | -> |      | -> |      | -> |      | -> |      | 
|  P1  |    |  P2  |    |  P3  |    |  P4  |    |  P5  |        
========    ========    ========    ========    ========

P(X) stands for Pointer to next node.

각 "노드"를 자체 블록으로 만들었습니다.이는 메모리에 인접해 있을 가능성이 보장되지 않기 때문입니다.

제가 P3에 접속하고 싶다면, 메모리의 어디에 있는지 모르기 때문에 직접 접속할 수 없습니다.제가 아는 것은 루트(P1)가 어디에 있는지 뿐이므로, 대신 P1에서 시작하여 각 포인터를 따라 원하는 노드로 이동해야 합니다.

이것은 O(N) 조회 시간입니다(조회 비용은 각 요소가 추가됨에 따라 증가합니다).P1000으로 가는 것이 P4로 가는 것보다 훨씬 더 비쌉니다.

해시 테이블, 스택 및 대기열과 같은 상위 수준의 데이터 구조는 모두 내부적으로 배열(또는 여러 배열)을 사용할 수 있는 반면, Linked Lists 및 Binary Tree는 일반적으로 노드와 포인터를 사용합니다.

단순히 배열을 사용하는 대신 선형 트래버설이 필요한 데이터 구조를 사용하여 값을 조회하는 이유가 궁금할 수도 있지만, 용도는 있습니다.

우리의 배열을 다시 가져가세요.이번에는 '5'라는 값을 가진 배열 요소를 찾고 싶습니다.

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^     ^     ^     ^     ^   FOUND!

이런 상황에서는 포인터에 어떤 오프셋을 추가해야 찾을 수 있는지 모르기 때문에 0에서 시작하여 찾을 때까지 계속 작업해야 합니다.이것은 제가 6번의 점검을 수행해야 한다는 것을 의미합니다.

따라서 배열에서 값을 검색하는 것은 O(N)로 간주됩니다.검색 비용은 배열이 커질수록 증가합니다.

위에서 제가 가끔 비순차적인 데이터 구조를 사용하는 것이 장점이 될 수 있다고 말한 것을 기억하십니까?데이터 검색은 이러한 이점 중 하나이며 가장 좋은 예 중 하나는 이진 트리입니다.

이진 트리는 연결된 목록과 유사한 데이터 구조이지만 단일 노드에 연결하는 대신 각 노드가 두 개의 하위 노드에 연결할 수 있습니다.

         ==========
         |  Root  |         
         ==========
        /          \ 
  =========       =========
  | Child |       | Child |
  =========       =========
                  /       \
            =========    =========
            | Child |    | Child |
            =========    =========

 Assume that each connector is really a Pointer

이진 트리에 데이터를 삽입할 때 데이터는 여러 규칙을 사용하여 새 노드를 배치할 위치를 결정합니다.기본 개념은 새 값이 부모 값보다 크면 왼쪽에 삽입하고, 낮으면 오른쪽에 삽입합니다.

즉, 이진 트리의 값은 다음과 같습니다.

         ==========
         |   100  |         
         ==========
        /          \ 
  =========       =========
  |  200  |       |   50  |
  =========       =========
                  /       \
            =========    =========
            |   75  |    |   25  |
            =========    =========

이진 트리에서 값 75를 검색할 때 다음 구조 때문에 노드 3개(O(log N))만 방문하면 됩니다.

• 75는 100보다 작습니까?오른쪽 노드 보기
• 75는 50보다 큰가요?왼쪽 노드 보기
• 75가 나왔습니다!

트리에 5개의 노드가 있지만 나머지 2개는 살펴볼 필요가 없었습니다. 왜냐하면 그들(및 그들의 자녀)이 우리가 찾고 있는 가치를 포함할 수 없다는 것을 알고 있었기 때문입니다.이를 통해 검색 시간을 확보할 수 있으므로 최악의 경우 모든 노드를 방문해야 하지만 최상의 경우에는 노드의 일부만 방문하면 됩니다.

여기서 어레이는 O(1) 액세스 시간에도 불구하고 선형 O(N) 검색 시간을 제공합니다.

이것은 메모리의 데이터 구조에 대한 믿을 수 없을 정도로 높은 수준의 개요로, 많은 세부 사항을 건너뛰지만, 다른 데이터 구조에 비해 어레이의 강점과 약점을 보여주기를 바랍니다.

O(1) 랜덤 액세스의 경우, 이길 수 없습니다.

모든 프로그램이 동일한 작업을 수행하거나 동일한 하드웨어에서 실행되는 것은 아닙니다.

이것이 일반적으로 다양한 언어 기능이 존재하는 이유입니다.배열은 컴퓨터 과학의 핵심 개념입니다.어레이를 목록/매트릭스/벡터/고급 데이터 구조로 대체하면 성능에 심각한 영향을 미치고 많은 시스템에서 실행 불가능합니다.해당 프로그램 때문에 이러한 "고급" 데이터 수집 개체 중 하나를 사용해야 하는 경우가 많습니다.

우리 대부분이 하는 비즈니스 프로그래밍에서는 상대적으로 강력한 하드웨어를 대상으로 할 수 있습니다.C#의 목록 또는 Java의 벡터를 사용하는 것이 이러한 상황에서 올바른 선택입니다. 이러한 구조를 통해 개발자는 목표를 더 빨리 달성할 수 있고, 결과적으로 이러한 유형의 소프트웨어를 더 많이 사용할 수 있기 때문입니다.

임베디드 소프트웨어나 운영 체제를 작성할 때는 어레이가 더 나은 선택일 수 있습니다.어레이는 더 적은 기능을 제공하지만 RAM은 덜 차지하며 컴파일러는 어레이를 검색하기 위해 코드를 더 효율적으로 최적화할 수 있습니다.

이러한 경우에 대한 여러 가지 이점을 생략하고 있는 것은 확실하지만, 요점을 이해하기를 바랍니다.

어레이의 이점을 살펴볼 수 있는 한 가지 방법은 어레이의 O(1) 액세스 기능이 필요하고 이에 따라 자본화되는 위치를 확인하는 것입니다.

1. 응용프로그램의 조회 테이블(특정 범주형 응답에 액세스하기 위한 정적 배열)

2. 메모화(함수 값을 다시 계산하지 않도록 이미 계산된 복잡한 함수 결과, 예를 들어 log x)

3. 이미지 처리가 필요한 고속 컴퓨터 비전 애플리케이션(https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing)

언급URL : https://stackoverflow.com/questions/392397/why-do-we-use-arrays-instead-of-other-data-structures