Data structure(자료 구조)
데이터에 적합한 자료 구조를 적절히 사용하는 것은, 시스템의 효율성에 큰 영향을 끼친다. Linux와 Git의 창시자인 Linus Torvalds 는 프로그래밍은 알고리즘과 자료구조로 이루어져 있다는 말도 했을 정도 라고. 따라서, 질 좋은 개발을 하기 위해서는 자료 구조를 이해하는 것이 중요하다.
자료형 구조를 쓸때는 항상 시간과 메모리의 balance를 생각하여 최적의 자료형을 선택해야 한다.
Primitive
우리가 자주 사용하는 int, float, string등도 자료 구조이며, 이들은 primitive data structure라고 불린다.
Non-primitive
통상 말하는 자료 구조들은 여기에 속한다. 프로그래밍을 조금이라도 접해본 사람들이 잘 아는 array,tuple, dictionary, set 등 의sequenece 자료형은 여기에 속한다.
Array (List)
list와 array는 다르지만, 자료 구조를 이야기 할 때는 interchangeable 하게 사용된다. 가장 많이 사용하는 자료 구조 이다.
list는 순서가 있다는 특징이 있다. 이는, 물리적으로 리스트의 요소들은 memory의 바로 옆에 저장되기 때문이다.
장점
- 순서가 있으므로, indexing이 가능하다. 즉, 특정 요소를 쉽게 읽어들일 수 있으며, slicing도 가능하므로, 원하는 요소들을 부르는데 용이하다.
단점
-
리스트의 중간에 있는 요소를 삭제하면, 삭제된 요소의 이후의 인덱스가 바뀌게 된다. 따라서, 요소의 삭제가 자주 일어나는 경우 사용하기 좋지 않는 자료형이다.
-
list를 사용하면 실제 저장되는 요소의 사이즈에 상관 없이, 선언하는 순간 고정된 용량의 메모리가 할당된다 (pre-allocation). 이는 list의 사이즈가 작을 때 비효율적으로 memory를 사용할 뿐만 아니라, list의 사이즈가 default 사이즈 이상으로 커지면, 다른 장소에 메모리를 재확보한 후, 원래 list들도 기존 장소에서 복사되어 새로운 장소에 옮겨지게 된다. 따라서, 사이즈 예측이 어려운 데이터들은 list를 쓰는것이 좋지만은 않다.
Linked List
list처럼 바로 옆에 물리적으로 저장하지 않고, 비어있는 다른 메모리 장소에 저장된다. 이전 요소가 다음 요소를 참조하고 있으므로, resizing에 문제가 없으나, 메모리를 많이 차지한다는 문제가 있다.
Tuple
List와 같이 순차열 자료구조이지만, list와 다르게 수정이 불가하다.
2~5개 사이의 바뀌지 않는 요소를 저장할 용도로 많이 쓰인다.
- 장점: list보다 빠르다,
- 단점: 각각의 값이 무엇을 의미하는지 알 수 없다 (Python에는 field명을 정하는 tuple도 존재하긴 한다.)
Set
set 또한 순차열 자료구조이다. 하지만 list와 달리 순서가 없으며, 중복된 요소를 저장할 수 없다.
왜 순서가 없을까? 역시 메모리 주소와 연관이 된다.
set은 집어넣는 값을 해싱하여 그 hash값(8bit)에 해당하는 메모리 주소(bucket)에 요소를 저장하게 된다.
hash값과 인덱스를 연결하는데는, 나누기의 나머지 값을 인덱스로 사용하게 된다. 나머지 값이 중복되는 경우도 있는데, 이때는 hash 충돌이 일어난다.
만약에 a = {1,2,3} 이라는 set에 1을 다시 넣으려고 하면, 기존의 1을 replace하여 그 자리에 입력한 1이 들어간다.
set도 사실 list로 이루어져 있다. 따라서, 어느정도 데이터가 차면(Python 의 경우 약 70%), array resizing이 일어난다.
더 공부할 용어들
hash table: key가 hash됨
hash : 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 mapping함
mapping: 하나의 값을 다른값으로 치환
Dictionary
데이터의 설명을 달기 위해서 사용한다. key를 해싱하여 저장하므로, 중복이 불가능 하다.
Binary Tree
각각의 node는 최대 둘의 children을 가지며, 각각의 child는 왼쪽과 오른쪽에 위치하게 된다.
탐색을 많이 하는 경우, 이 형식으로 저장하면 빠르게 찾기가 가능하다. 사실 Big O 표기법에 의하면 list가 O(n), tree가 O(log n), set이 log(1)로 set이 lookup에 걸리는 시간이 가장 빠르지만, tree는 set과 달리 순서가 있으므로, indexing이 가능하다.
Stack
First-In-Last-Out 형식의 데이터 구조. 접시쌓기를 생각하면 된다.
함수는 stack의 형태로 쌓인다.
stack overflow는 무한로프에 잘못 걸렸을 때, 또는 사이즈가 정해져 있는데 그보다 함수 호출을 많이 했을 때 일어나는 에러 이다.
Queue
First-In-First-Out 형식의 데이터 구조.
브라우저에서 뒤로가기 버튼 등은 queue를 활용한 예이다.
우선순위가 있는 경우, priority queue 구조를 사용할 수 있다.
