코드의 품질을 측정하는 다양한 척도 중에 코드 '효율성'이 있다. 같은 목표를 달성해도 더 빠르게 실행되는 코드를 효율적인 코드라고 한다. 뛰어난 소프트웨어 개발자로 성장하고 싶다면 더 빠르게 실행되는 코드 작성 능력을 갖춰야 한다.
효율적인 코드를 작성하는 첫 번째 단계는 자료 구조가 무엇인지, 다양한 자료 구조가 코드 속도에 어떤 영향을 미치는지 이해하는 것이다.
1. 1 자료구조
'자료 구조'란 데이터를 조직하는 방법이다.
// 문자열 데이터의 조합
String x = "Hello! ";
String y = "How are you ";
String z = "today?";
System.out.println(x + y + z);
// "Hello! How are you today?"
// 문자열 데이터를 배열로 저장
String[] array = ["Hello! ", "How are you ", "today?"];
System.out.println(array[0] + array[1] + array[2]);
// "Hello! How are you today?"
같은 데이터라도 다양한 방식으로 조직할 수 있다. 그리고 이러한 데이터 조직이 코드의 실행 속도에 미치는 영향이 크다. 따라서 명쾌한 코드를 작성하는 능력을 갖추려면 다양한 자료 구조를 알고, 각각의 자료 구조가 개발 중인 프로그램의 성능에 어떤 영향을 미칠지 이해하고 있어야 한다.
1. 2 배열: 기초 자료 구조
배열은 컴퓨터 과학에서 기초적인 자료 구조 중 하나로, 단순히 데이터 원소들의 리스트이다.
- 배열의 크기: 배열에 데이터 원소가 얼마나 들어있는지 알려준다.
- 배열의 인덱스: 특정 데이터가 배열의 어디에 있는지 알려준다.
String[] array = ["apples", "bananas", "cucumbers", "dates", "elderberries"];
| "apples" | "bananas" | "cucumbers" | "dates" | "watermelon" |
| 인덱스 0 | 인덱스 1 | 인덱스 2 | 인덱스 3 | 인덱스 4 |
대부분의 자료 구조는 4가지 '연산'을 이용하여 코드와 상호작용한다. 해당 연산이 얼마나 걸리냐가 자료 구조의 핵심이다.
- 읽기: 자료 구조 내 특정 위치를 찾아보는 것이다. 배열에서는 특정 인덱스의 값을 찾아보는 것을 뜻한다.
(예: index 2에 들어있는 물건을 찾는 것) - 검색: 자료 구조 내에서 특정 값을 찾는 것이다. 배열에서는 특정 값이 배열에 들어있는지, 만약 그렇다면 어떤 인덱스에 있는지 알아보는 것을 뜻한다. (예: "dates"가 배열에 있는지, 어떤 인덱스에 있는지 알아보는 것)
- 삽입: 자료 구조에 새로운 값을 추가하는 것이다. 배열이라면 배열 내에 슬롯을 더 만들어 새 값을 추가한다.
- 삭제: 자료 구조에서 값을 제거하는 것이다.
1. 3 속도 측정
연산이 얼마나 "빠른가"를 측정할 때는 순수하게 '시간' 관점에서 연산이 얼마나 빠른가가 아니라, 얼마나 많은 '단계'가 필요한지 봐야한다.
코드의 속도를 단계로 측정하는 이유는, 어떤 연산이 정확히 몇 초가 소요되는지 아무도 알 수 없기 때문이다. 같은 연산이라도 신형 컴퓨터와 구형 컴퓨터 사이엔 차이가 존재한다. 미래의 컴퓨터에선 훨씬 빠를 수도 있다. 시간은 연산을 실행하는 하드웨어에 따라 항상 바뀌기 때문에 시간을 기준으로 속도를 측정하면 신뢰하기 어렵다.
따라서, 연산의 속도를 측정할 땐 얼마나 많은 계산 단계(step)가 필요한지 따져봐야 한다. 단계 수 측정이 연산 속도를 분석하는 핵심 비결이다.
1. 4 읽기
'읽기' 연산은 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾아보는 것이다.
컴퓨터는 배열 내 특정 인덱스에 딱 한 번에 접근해서 볼 수 있기 때문에 배열에서의 읽기는 한 단계만 소요된다. 컴퓨터가 어떻게 단 한 단계로 배열의 인덱스를 찾아보는지 알아보자. 컴퓨터의 메모리는 셀로 구성된 거대한 컬렉션이다.
아래 그림은 컴퓨터 메모리의 내부 동작을 단순화시킨 것이다. 프로그램에서 배열을 선언하면 컴퓨터는 프로그램이 쓸 수 있는 연속된 빈 셀들의 집합을 할당한다. 만약 원소 다섯 개를 넣을 배열을 생성하면 컴퓨터는 한 줄에서 5개의 빈 셀 그룹을 찾아 사용자가 사용할 배열로 지정한다.
| 9 | 16 | ||||
| "a" | |||||
| 77 | |||||
| "hello" | "hi" | ||||
| 100 | |||||
| 8014 |
컴퓨터 메모리 내의 각 셀에는 특정 주소가 있다. 각 셀의 메모리 주소는 앞 셀의 주소에서 1씩 증가한다.
그리고 앞서 지정한 배열의 인덱스에 맞게 메모리 주소가 연결된다.
| 1000 | 1001 | 1002 | 1003 | 1004 | 1005 |
| 1006 | 1007 | 1008 | 1009 | 1010 | 1011 |
| 1012 | 1013 | 1014 | 1015 | 1016 | 1017 |
| 1018 | 1019 | 1020 | 1021 | 1022 | 1023 |
| 1024 | 1025 | 1026 | 1027 | 1028 | 1029 |
| 1030 | 1031 | 1032 | 1033 | 1034 | 1035 |
| 1036 | 1037 | 1038 | 1039 | 1040 | 1041 |
| 1042 | 1043 | 1044 | 1045 | 1046 | 1047 |
인덱스 0 = 메모리 주소: 1006
인덱스 1 = 메모리 주소: 1007
인덱스 2 = 메모리 주소: 1008
인덱스 3 = 메모리 주소: 1009
인덱스 4 = 메모리 주소: 1010
컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있는 특징이 있다. 컴퓨터에 메모리 주소 1033에 있는 값을 조사하라고 요청하면 검색 과정 없이 바로 찾아낸다. 그리고 배열을 할당할 때 어떤 메모리 주소에서 시작하는지도 기록해 두기 때문에 배열의 첫 번째 원소를 찾으라고 하면 적절한 메모리 주소로 바로 가서 찾는다.
만약 컴퓨터에 배열의 인덱스 3에 있는 값을 찾으라고 요청하면, 컴퓨터는 인덱스 0의 메모리 주소를 가져와 3을 더한다. 어차피 메모리 주소는 +1 순차적으로 늘어나기 때문이다.
1. 배열의 인덱스는 0부터 시작하며, 인덱스 0의 메모리 주소는 1006이다.
2. 인덱스 3은 인덱스 0부터 정확히 세 슬롯 뒤에 있다.
3. 인덱스 3을 찾으려면 1006 + 3인 1009 메모리 주소로 간다.
배열은 기초 자료 구조일 뿐만 아니라 빠르게 읽을 수 있는 강력한 자료 구조이다.
1. 5 검색
'검색' 연산은 배열에 특정 값이 있는지 알아본 후, 있다면 어떤 인덱스에 있는지 찾는 것이다. 읽기 연산은 인덱스 값을 주고 값을 반환하라고 요청한 반면, 검색 연산은 값을 주고 인덱스 값을 반환하는 것으로 반대이다.
서로 비슷해 보이지만 효율성 측면에서 어마어마하게 다르다. 읽기와 다르게 검색은 컴퓨터가 특정값으로 바로 갈 수 없으니 오래 걸린다. 컴퓨터는 모든 메모리 주소에 한 번에 접근할 수 있지만, 각 메모리 주소에 어떤 값이 있는지는 바로 알지 못한다. ㅠㅠ
컴퓨터 입장에선 메모리의 각 셀에 실제 어떤 내용이 들어 있는지 바로 알 수 없다. 배열이 이렇게 보일 것이다.
| ??? | ??? | ??? | ??? | ??? |
| 인덱스 0 | 인덱스 1 | 인덱스 2 | 인덱스 3 | 인덱스 4 |
그래서 컴퓨터는 각 셀을 한 번에 하나씩 조사하는 방법을 쓸 수밖에 없다. 인덱스 0부터 하나씩, 하나씩 열어보며 사용자가 요청한 값이 있는지 확인해본다. 만약 "cucumbers"를 찾으려면 아래와 같은 단계를 거친다.
| "apples" | ??? | ??? | ??? | ??? |
| 인덱스 0 | 인덱스 1 | 인덱스 2 | 인덱스 3 | 인덱스 4 |
▼
| "apples" | "bananas" | ??? | ??? | ??? |
| 인덱스 0 | 인덱스 1 | 인덱스 2 | 인덱스 3 | 인덱스 4 |
▼
| "apples" | "bananas" | "cucumbers" | ?? | ?? |
| 인덱스 0 | 인덱스 1 | 인덱스 2 | 인덱스 3 | 인덱스 4 |
총 3단계를 거친 후에 "cucumbers"를 찾았다!
이렇게 컴퓨터가 한 번에 한 셀씩 확인하는 방법을 '선형 검색'이라고 부른다. 만약 찾고 싶은 값이 배열의 마지막 셀에 있다면 컴퓨터는 이 값을 발견할 때까지 배열의 모든 셀을 검색해야 한다. 또한, 찾고 있는 값이 배열의 어떤 셀에도 없으면 모든 셀을 검색해야 배열에 값이 없다고 확실한 수 있다.
따라서 컴퓨터가 배열에서 선형 검색을 수행하는 데 필요한 최대 단계 수는 N개다. (N은 어떤 수든 넣을 수 있는 변수로써 N개의 셀로 이뤄진 배열의 경우를 뜻한다.)
검색은 읽기보다 덜 효율적이다. 읽기는 배열이 얼마나 크든 항상 한 단계만 걸리지만 검색은 많은 단계가 걸릴 수 있다.
1. 6 삽입
배열에 새 데이터를 삽입하는 연산은 배열의 어디에 데이터를 삽입하는가에 따라 효율성이 달라진다.
만약 배열의 맨 끝에 추가할 경우, 이 삽입에는 딱 한 단계만 필요하다. 컴퓨터는 배열이 시작되는 메모리 주소를 알고 있고, 또 배열을 할당할 때 이미 배열의 크기까지 기록하기 때문에 컴퓨터가 배열 마지막 항목의 메모리 주소를 계산하는 건 매우 쉽다. 배열이 메모리 주소 1006에서 시작하고 크기가 5면 마지막 메모리 주소는 1010다. 그 뒤에 항목을 삽입하면 다음 메모리 주소인 1011에 항목을 추가한다는 뜻이다. 이제 컴퓨터는 새 값을 삽입할 메모리 주소를 계산할 수 있고 한 단계면 충분하다.
하지만,
배열의 맨 처음이나 중간에 데이터를 삽입하면 문제가 달라진다. 이때는 삽입할 공간을 만들기 위해 많은 데이터 조각을 이동시켜야 하므로 단계가 늘어난다.
| "apples" | "bananas" | "cucumbers" | "dates" | "watermelon" |
(1단계: watermelon을 옮긴다)
▼
| "apples" | "bananas" | "cucumbers" | "dates" | "watermelon" |
(2단계: dates를 옮긴다)
▼
| "apples" | "bananas" | "cucumbers" | "dates" | "watermelon" |
(3단계: cucumbers을 옮긴다)
▼
| "apples" | "bananas" | "cucumbers" | "dates" | "watermelon" |
(4단계: orange를 인덱스 2에 삽입한다.)
▼
| "apples" | "bananas" | "orange" | "cucumbers" | "dates" | "watermelon" |
데이터를 옮기는 3단계와 실제로 새 값을 삽입하는 1단계, 총 4단계가 소요됐다.
배열의 삽입에서 가장 최악의 시나리오는 데이터를 배열의 맨 앞에 삽입할 때다. 배열의 앞에 삽입하면 배열 내 모든 값을 한 셀씩 오른쪽으로 옮겨야 하기 때문이다.
다시 말해 원소 N개를 포함하는 배열에서 최악의 시나리오일 때 삽입은 N+1단계가 걸린다. N개의 원소를 전부 이동시키고 끝으로 실제 삽입 단계를 실행해야 하기 때문이다.
1. 7 삭제
배열의 삭제는 특정 인덱스의 값을 제거하는 것이다.
배열의 삭제는 삽입 연산과 유사하다. 실제 값을 삭제하는 건 한 단계만 소요되지만, 배열의 중간에 빈 공간을 메꿔야 하므로 값들을 왼쪽으로 옮겨야 한다. 즉 삭제 과정에 단계가 더 필요하다는 뜻이다.
삽입과 비슷하게 원소 삭제에서 최악의 시나리오는 배열의 첫 번째 원소를 삭제하는 것이다. 이렇게 되면 인덱스 0이 비게 되고, 남아 있는 모든 원소를 왼쪽으로 이동시켜 빈 공간을 채워야 한다. 만약 원소가 500개인 배열이면 1단계는 첫 번째 원소의 삭제에, 499단계는 남은 데이터를 이동하는 데 쓰인다.
따라서 원소 N개를 포함하는 배열에서 삭제에 필요한 최대 단계 수는 N단계이다.
1. 8 집합: 단 하나의 규칙으로 효율성이 달라진다
또 다른 자료 구조인 '집합'은 배열과 비슷하지만, 중복 값을 허용하지 않는다.
여러 종류의 집합 중에서도 '배열 기반 집합'은 값들의 단순 리스트로 배열과 거의 비슷하다. 중복 값의 삽입을 절~대 허용하지 않는 것만 차이가 있다.
만약 ["a", "b", "c"]라는 집합에 또 다른 "b"를 추가하려고 하면 컴퓨터는 "b"가 이미 집합에 있으므로 삽입을 허용하지 않는다. 즉, 집합은 중복 데이터가 없어야 할 때 유용하다. (전화번호부를 만들 때 동일한 전화번호가 있으면 안 되므로 집합이 적합할 것이다)
중복 값을 허용하지 않는 집합의 특성은 네 가지 주요 연산 중 하나에서 엄청난 효율성을 보인다.
'읽기'는 메모리 주소를 쉽게 계산해서 접근할 수 있으므로 1단계 만에 찾아 배열 읽기와 동일하다.
'검색'도 최대 N단계가 걸려 배열의 검색과 아무런 차이가 없다.
'삭제'도 마찬가지로 값을 삭제하고 데이터를 왼쪽으로 옮겨 빈 공간을 메꾸는데 최대 N단계가 걸린다.
하지만 '삽입'에선 배열의 삽입과 다르다.
집합은 중복된 값을 허용하지 않기 때문에, 먼저 동일한 값이 있는지 '검색'을 해야 한다. 따라서 모든 삽입에는 검색이 우선이다. (배열의 삽입에선 맨 끝에 삽입하는 경우엔 1단계로 끝난다!)
집합의 끝에 삽입하려면 값이 집합에 없음을 확인하는 데 N단계의 검색과 이어서 실제 삽입에 필요한 1단계를 사용해 최대 N+1단계가 필요하다.
집합의 맨 앞에 삽입하는 최악의 시나리오일 때는, 셀 N개를 검색해서 중복 값 여부를 확인한 다음, 또 다른 N단계로 모든 데이터를 오른쪽으로 옮겨야 하며, 마지막 단계에서 새 값을 삽입해야 한다. 총 2N+1단계다.
이처럼 집합에서는 일반적인 배열보다 삽입이 느리다. 그러나 중복 데이터가 없어야 할 때는 집합이 답이다. 애플리케이션의 요구사항을 먼저 분석한 후 어떤 자료 구조가 더 적합한지 결정해야 한다.
1. 9 마무리
자료 구조의 성능 측정은 연산에 필요한 단계 수를 구하는 게 핵심이다. 프로그램에 꼭 맞는 자료 구조를 선택했느냐에 따라 프로그램의 성능이 좌지우지된다.
해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.
오로지 학습용으로 작성하였음을 밝힙니다.
더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.
'자료구조 & 알고리즘' 카테고리의 다른 글
| Ch.06 긍정적인 시나리오 최적화 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.05.05 |
|---|---|
| Ch.05 빅 오를 사용하거나 사용하지 않는 코드 최적화 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.05.03 |
| Ch.04 빅 오로 코드 속도 올리기 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.04.26 |
| Ch.03 빅 오 표기법 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.04.23 |
| Ch.02 알고리즘이 중요한 까닭 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.04.21 |
