object와 array의 성능 평가

2021.12.10

객체(object)

객체는 모든 것이 키-값 쌍으로 저장되는 정렬되지 않은 데이터 구조이다. 학생부를 예로 들자면, 객체의 key가 학생의 이름이고, value가 학생의 정보인 것이다.
익명의로 정보를 저장하는 것이 아니라 학생들의 이름을 각각 기입하기 때문에 찾기 쉽다.

객체를 사용해야할 때

순서가 필요없을 때
- 정확히는 아예 순서가 없는 것은 아니다.
- javascript의 object는 순서가 없을까??
빠른 시간으로 데이터 접근과 삽입, 제거를 원할 때
- 여기서 빠르다는 것은 데이터 삽입이나 제거나 접근에 거의 일정한, 상수의 시간이 걸린다는 말이다.

객체에서 Big O

접근 - O(1)
javascript에서 객체는 얼마나 많은 속성을 가지고 있는지에 상관없이 객체에 속성을 접근할 수 있다.
앞서 예시로 든 학생부에서 선생님이 어떤 학생에 대한 정보를 찾고 싶다면 해당 학생의 이름을 알면 바로 찾을 수 있을 것이다.
때문에 해당 키로 접근하는 것은 O(1)이다.
삽입, 대체 - O(1)
객체는 배열처럼 명확히 들어온 순서대로 열거하지 않기 때문에 값이 들어온다면 그대로 저장 혹은 대체를 하게 된다.
제거 - O(1)
삽입과 마찬가지로 입력한 키와 그에 해당하는 값을 바로 삭제해주기 때문에 O(1)이다.
탐색 - O(N)
하지만 탐색은 좀 다르다.
모든 항목들을 살펴보고 확인해야 하므로 O(N)이 된다.
아래의 탐색 메서드들을 보자.

객체 메서드의 Big O

let instructor = {
  firstName: "Kelly",
  isInstructor: true,
  favoriteNumbers: [1, 2, 3, 4]
};

Object.keys - O(N)
```
Object.keys(instructor); // ['firstName', 'isInstructor', 'favoriteNumbers']
```
key들을 배열로 반환해주는 메서드이다.
객체의 길이인 n과 같은 배열을 반환시켜주므로, 시간복잡도는 O(N)이다.
Object.values - O(N)
```
Object.values(instructor); // ['Kelly', true, [1, 2, 3, 4]]
```
객체의 vlaue들을 배열로 반환해주는 메서드이다.
객체의 길이인 n과 같은 배열을 반환시켜주므로, 시간복잡도는 O(N)이다.
Object.entries - O(N)
```
Object.entries(instructor); // [['firstName', 'Kelly'], ['isInstructor', true], ['favoriteNumbers', [1, 2, 3, 4]]]
```
객체에 key와 value들을 배열로 짝짓고 그 배열들을 전체 배열에 푸쉬하여 반환해주는 메서드이다.
정확히는 Object.key보다 약간 더 많은 작업을 수행해야 한다. 빈 배열을 만들어 키와 값을 푸쉬하고 그 배열을 또 푸쉬해야 하지만 Big O로 단순화해서 O(N)이다.
hasOwnProperty - O(1)
```
instructor.hasOwnProperty("firstName") // true
```
해당 키가 객체에 있는지를 확인하고 boolean값을 반환해주는 메서드이다.
위의 메서드들과 달리 해당 키로 접근을 하고 값이 있는지 없는지 여부에 따라 반환해주기 때문에 O(1)이다.

결론: object는 빠르다!

배열(array)

엄밀히 말하자면 배열도 사실을 객체이다.
위에 예시로 들었던 출석부에서 객체는 값들의 정확한 이름을 정해서 정보를 저장하지만, 배열은 학생의 이름 대신 입학한 순서를 사용해서 정보를 저장하는 것이다.
배열의 삽입 순서대로 열거하게 되고 그 열거 순서인 index를 key로 사용하게 된다.

베열을 사용해야 할 때

순서가 필요할 때 - 정확히 말해 순서가 저장되는 타입이 배열만 있는 것은 아니다. (Map이나 link list 등)
- 차례대로 배열에 삽입한다면 열거 순서가 삽입 순서가 되지만, 맨 앞에 삽입을 하게 된다면 정확히는 열거 순서가 삽입 순서가 되지 않는다.
빠른 접근과 요소의 삽입, 제거가 필요한 경우(삽입과 제거의 경우 어떻게 하냐에 따라 달라진다.)

베열에서 Big O

접근 - O(1)
앞서 말했듯이 key와 같은 역할인 index로 접근하기 때문에 배열의 접근은 O(1)이다.
대체 - O(1)
해당 인덱스로 접근하여 값을 새로운 값으로 바꿔주면 되기 때문에 O(1)이다.
삽입 - 상황에 따라 다르다.
삽입을 할 때는 삽입의 위치가 어디냐에 따라 다르다.
삽입을 배열의 제일 끝에 하게 된다면 배열의 끝에 그냥 추가해주면 되지만, 제일 앞에 추가를 하게 된다면 맨 앞에 추가요소가 들어가게 되면서 기존의 0의 인덱스가 더 이상 0의 순서가 아니기 때문에 기존의 요소들을 하나씩 뒤로 밀어주어야 한다.
때문에 젤 끝에 요소를 삽입한다면 O(1) / 젤 앞에 요소를 삽입한다면 O(N)이 되는 것이다.
제거 - 상황에 따라 다르다.
제거도 삽입과 마찬가지이다.
젤 끝에 요소를 제거한다면 O(1) / 젤 앞에 요소를 제거한다면 O(N)이 되는 것이다.
탐색 - O(N)
배열의 탐색 또한 객체처럼 O(N)이다.
아래의 베열 메서드를 보자.

배열 메서드의 Big O

const array = ['a', 'b', 'c', 'd'];
        //    0    1    2    3

push - O(1)
```
array.push(e);
// ['a', 'b', 'c', 'd', 'e']
//   0    1    2    3    4
```
배열의 젤 끝에 요소를 삽입해주는 메서드이다.
위에 말했듯이 젤 끝에 요소를 삽입하는 것은 O(1)이다.
pop - O(1)
```
array.pop(e);
// ['a', 'b', 'c']
//   0    1    2
```
배열의 젤 끝에 요소를 제거해주는 메서드이다.
위에 말했듯이 젤 끝에 요소를 제거하는 것은 O(1)이다.
shift - O(N)
```
array.shift(A);
// ['A', 'a', 'b', 'c', 'd']
//   ?    0    1    2    3  => ?? 한칸 씩 뒤로 가자!
//   0    1    2    3    4
```
배열의 젤 앞에 요소를 삽입해주는 메서드이다.
위에 말했듯이 젤 앞에 요소를 삽입하는 것은 O(N)이다.
unshift - O(N)
```
array.unshift(A);
// ['b', 'c', 'd']
//   1    2    3  => ?? 한칸 씩 앞으로로 가자!
//   0    1    2
```
배열의 젤 앞에 요소를 제거해주는 메서드이다.
위에 말했듯이 젤 앞에 요소를 제거하는 것은 O(N)이다.
concat - O(N)
```
const conArray = ['A', 'B'];
array.concat(conArray);
// [] -> ['a'] -> ['a', 'b'] -> ... -> ['a', 'b', 'c', 'd', 'A', 'B']
// => O(N + M) => O(N)
```
여러 배열을 합쳐주는 메서드이다.
첫 번째 배열의 길이가 n이고 두번째 배열의 길이가 m이면, O(n+m)이므로 O(N)이다.
slice - O(N)
```
array.slice(1, 3);
// ['b'] -> ['b', 'c']
// => O(N/2) => O(N)
```
배열의 일부 또는 전체를 복사해주는 메서드이다.
복사하려는 요소의 갯수만큼 반복되므로 O(N)이다.
splice - O(N)
```
array.splice(1, 3, 'A');
// [] -> ['b'] -> ['b', 'c'] -> 'b', 'c', 'A']
// => O(N/2 + 1) => O(N)
```
원하는 시작지점부터 종료지점까지 제거하고 원한다면 새로운 요소를 추가할 수 있는 메서드이다.
배열의 처음이나 중간, 끝 중 어디에 제거하고 삽입하냐에 따라 O(N), O(N/2), O(1)이 될 수 있지만 간단히 말하자면 O(N)이다.
sort - O(N * log N)
정렬 알고리즘에서 다루겠다.
forEach / map / filter / reduce / ect… - O(N)
해당 메서드들은 배열을 처음부터 끝까지 돌면서 해당 메서드들의 기능들을 하기 때문에 O(N)이다.

Dony :)