다른 데이터 구조 대신 배열을 사용하는 이유는 무엇입니까?

다른 데이터 구조 대신 배열을 사용하는 이유는 무엇입니까?

---

프로그래밍 할 때 배열이 다른 형식보다 정보를 저장하는 것이 더 좋은 인스턴스를 보지 못했습니다. 나는 실제로 프로그래밍 언어에서 추가 된 "기능"이 이것에 대해 개선되었고 그것들로 대체되었다고 생각했다. 나는 이제 그들이 대체되지 않고 오히려 새로운 삶을 얻었음을 알 수 있습니다.

기본적으로 배열 사용의 요점은 무엇입니까?

이것은 컴퓨터 관점에서 배열을 사용하는 이유가 아니라 프로그래밍 관점에서 배열을 사용하는 이유입니다 (미묘한 차이). 컴퓨터가 배열을 사용하는 것은 문제의 핵심이 아닙니다.

---

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

내가 들어가기 전에 "포인터"라는 용어의 의미에 대한 간단한 설명. 포인터는 단순히 메모리의 위치를 ​​"가리키는"변수입니다. 이 메모리 영역의 실제 값은 포함하지 않으며 메모리 주소도 포함됩니다. 메모리 블록을 사서함으로 생각하십시오. 포인터는 해당 사서함의 주소입니다.

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

  MyArray   [5]
     ^       ^
  Pointer  Offset

다른 모든 데이터 구조는이를 기반으로하거나 스토리지에 인접한 메모리를 사용하지 않으므로 무작위 액세스 조회 시간이 줄어 듭니다 (순차 메모리를 사용하지 않으면 다른 이점이 있음).

예를 들어, 6 개의 숫자 (6,4,2,3,1,5)를 가진 배열이 메모리에 있다고 가정 해 봅시다.

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

배열에서 우리는 각 요소가 메모리에서 서로 옆에 있다는 것을 알고 있습니다. AC 배열 (여기서는 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에 액세스하려면 메모리의 어디에 있는지 모르기 때문에 P3에 직접 액세스 할 수 없습니다. 내가 아는 것은 루트 (P1)가있는 곳이므로 P1에서 시작하여 원하는 노드에 대한 각 포인터를 따라야합니다.

이것은 O (N) 조회 시간입니다 (각 요소가 추가 될 때 조회 비용이 증가합니다). P4에 비해 P1000에 도착하는 것이 훨씬 비쌉니다.

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

왜 누군가가 배열을 사용하는 대신 값을 찾아보기 위해 선형 순회가 필요한 데이터 구조를 사용해야하는지 궁금해 할 수 있습니다.

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

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

이 상황에서 포인터를 찾기 위해 포인터에 추가 할 오프셋을 모르므로 0에서 시작하여 찾을 때까지 진행해야합니다. 이것은 내가 6 점검을 수행해야 함을 의미합니다.

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

때때로 비 순차적 데이터 구조를 사용하면 이점이있을 수 있다고 말한 것을 기억하십시오. 데이터 검색은 이러한 장점 중 하나이며 가장 좋은 예 중 하나는 이진 트리입니다.

A Binary Tree is a data structure similar to a linked list, however instead of linking to a single node, each node can link to two children nodes.

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

 Assume that each connector is really a Pointer

When data is inserted into a binary tree, it uses several rules to decide where to place the new node. The basic concept is that if the new value is greater than the parents, it inserts it to the left, if it is lower, it inserts it to the right.

This means that the values in a binary tree could look like this:

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

When searching a binary tree for the value of 75, we only need to visit 3 nodes ( O(log N) ) because of this structure:

• Is 75 less than 100? Look at Right Node
• Is 75 greater than 50? Look at Left Node
• There is the 75!

Even though there is 5 nodes in our tree, we did not need to look at the remaining two, because we knew that they (and their children) could not possibly contain the value we were looking for. This gives us a search time that at worst case means we have to visit every node, but in the best case we only have to visit a small portion of the nodes.

That is where arrays get beat, they provide a linear O(N) search time, despite O(1) access time.

This is an incredibly high level overview on data structures in memory, skipping over a lot of details, but hopefully it illustrates an array's strength and weakness compared to other data structures.

---

For O(1) random access, which can not be beaten.

---

Not all programs do the same thing or run on the same hardware.

This is usually the answer why various language features exist. Arrays are a core computer science concept. Replacing arrays with lists/matrices/vectors/whatever advanced data structure would severely impact performance, and be downright impracticable in a number of systems. There are any number of cases where using one of these "advanced" data collection objects should be used because of the program in question.

In business programming (which most of us do), we can target hardware that is relatively powerful. Using a List in C# or Vector in Java is the right choice to make in these situations because these structures allow the developer to accomplish the goals faster, which in turn allows this type of software to be more featured.

When writing embedded software or an operating system an array may often be the better choice. While an array offers less functionality, it takes up less RAM, and the compiler can optimize code more efficiently for look-ups into arrays.

I am sure I am leaving out a number of the benefits for these cases, but I hope you get the point.

---

A way to look at advantages of arrays is to see where is the O(1) access capability of arrays is required and hence capitalized:

1. In Look-up tables of your application (a static array for accessing certain categorical responses)

2. Memoization (already computed complex function results, so that you don't calculate the function value again, say log x)

3. High Speed computer vision applications requiring image processing (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