이전글
베열과 오브젝트 성능 평가 in JS - 1

배열과 오브젝트 성능 평가 - 2

배열을 빅오(Big O)를 통해 판단하고 객체와 비교했을 때 성능을 확인한다.

  • ex) Arrays ordered lists 
    1
2

    let names = ["Michael", "Melissa", "Andrea"];
let values = [true, {}, [], 2, "awesome"];

When To use Arrays

  • Whem you need order
    배열을 대부분 정렬되어 있는 데이터를 위해서 사용한다.
    정렬되어 있는 것이 필요가 없으면 배열을 사용하지 않는 것이 좋다.

    섞여있는 데이터를 저장하고 싶을 때 배열을 사용하면 되지만 성능을 최적화하고 싶다면 다른 선택권이 있다.
    정렬되어 있는 것이 필요하더라도, 싱글 링크 리스트와 더블 링크 리스트처럼 코드 안에 정렬된 구조가 있는 데이터도 있다.
    이것은 선형 리스트 구조이다.
    엘리먼트마다 특정한 위치에 있고 순서대로 연결되어 있으며 하는 작업에 따라서 배열보다 빠를 수 있다.

    정렬되어 있는 데이터 구조가 배열만 있는 것은 아니다.
    자바스크립트에 내장되어 있는 구조일 뿐이다.

  • When you need fast access / insertion and removal (sort of…)
    정렬되어 있는 데이터가 필요할 때 배열을 사용할 수 있지만, 성능을 희생해야 할 수 있다.
    (특히 입력과 제거를 할 때 복잡해질 수 있다.)

📁 Big O of Arrays

Insertion - It depends…
Removal - It depends…
Searching - $O(N)$
Access - $O(1)$

Access (접근)

배열에 있는 데이터를 접근하는 것은 매우 빠르다.
접근(Access)은 $O(1)$ 상수 시간이다. (객체와 같다)

배열이 있을 때 어떠한 데이터를 접근하는데 걸리는 상수시간이 있다.
만약 100개의 엘리먼트가 있는 배열에서 70번 째 엘리먼트를 요청했을 때, 자바스크립트는 모든 엘리먼트를 순서대로 하나씩 지나가면서 70번 째 엘리먼트에 도착했을 때 주는 것이 아니다.
(엘리먼트마다 바로 갈 수 있는 지름길이 있다고 생각하면 된다.)

그렇기 때문에 배열의 엘리먼트의 수가 얼마나 많든, 찾는 엘리먼트가 처음 아니면 마지막에 있던 간에 중요하지 않다.
이것이 접근의 $O(1)$ 상수 시간이다.

Insertion, Removal (입력, 제거)

1
2
3

let names = ["Michael", "Melissa", "Andrea"];
// "Michael"    "Melissa"   "Andrea"
//     0            1          2

입력(Insertion)은 엘리먼트들의 정렬과 관련이 있다.
위의 예제 코드를 보면 엘리먼트마다 붙어있는 인덱스가 있다.

  • 여기에 엘리먼트를 끝에다 추가한다면, 배열에 push 하게 된다.
    ex) [“Michael”, “Melissa”, “Andrea”, “Test”]
    배열 끝에 추가하고, 인덱스(3)를 주면 객체에 추가하는 것과 다를게 없다.
    이런 작업은 $O(1)$ 상수 시간이다.

  • 문제가 되는 것은 예제에 있는 배열들의 맨 앞에 추가하는 것이다.
    ex) [“Test”, “Michael”, “Melissa”, “Andrea”]
    맨 앞에 추가하면 Michael은 0번째 엘리먼트가 아니다. 나머지 엘리먼트들의 순서도 마찬가지이다.
    그렇기 때문에 배열에 있는 엘리먼트마다 새로운 인덱스를 배정해야 한다.
    엘리먼트가 수 천개가 있는 배열이라면 인덱스를 모두 새로 배정하는 것은 쉽지가 않다.
    엘리먼트마다 작업을 하나씩 해야하기 때문이다. N의 크기에 따라서 시간이 커지게 된다.
    이렇게 배열 앞에 추가하는 작업은 $O(n)$ 선형 시간이다.

마찬가지로 제거(Removal)도 앞에서 제거한다면, 배열을 pop 하게 된다.
ex) [“Melissa”, “Andrea”]
그러면 인덱스를 반대 방향으로 다시 배정해야 한다.

입력과 제거는 어디에서 작업을 하는지에 따라 달라진다.

배열 앞에 추가하고 제거하는 것은 끝에서 작업하는 것보다 효율적이지 않다.
push, pop 작업은 shift 와 unshift 작업보다 빠르다.
(비어있는 배열일 때는 제외한다. 앞에 추가하는 것과, 뒤에 추가하는 것이 똑같아진다)

Searching (탐색)

탐색은 가장 빨라도 $O(N)$ 선형시간이다. 배열에 엘리먼트가 100개가 있고 만약 “Test” 라는 이름이 포함되었는지 확인하고 싶다면
100개의 모든 엘리먼트들을 각각 확인해야 할 수 있다.
배열의 크기가 커질수록 탐색하는 시간이 그만큼 길어지게 된다.

데이터가 정렬되어 있다면 탐색을 최적화할 수 있는 방법에 대해 생각해볼 수 있다.

🌞 정보 : 공부 기록용 블로그입니다. 오타나 내용 오류가 있을 경우 알려주시면 감사하겠습니다.

댓글남기기

Recent posts