들어가며
컴퓨터 코드를 조금이라도 작성해 보면 프로그래밍이 데이터를 주로 다루는 것임을 곧 알 수 있다.
컴퓨터 프로그램은 데이터를 입력받아 조작하고 반환하는 게 전부다.
두 수의 합을 계산하는 간단한 프로그램이든, 회사 전체를 관리하는 기업용 소프트웨어든,
소프트웨어는 데이터에 관한 것이다.
데이터는 일반적으로 모든 유형의 정보를 망라하는 용어이며, 가장 기초적인 수와 문자열로 이뤄진다.
간단하지만 고전적인 "Hello World!" 프로그램을 떠올리면
"Hello World"
문자열이 바로 데이터다.
매우 복잡한 데이터라도 대개는 수와 문자열 묶음으로 나뉜다.
자료 구조란 데이터를 조직하는 방법이다.
다음의 코드를 살펴보자.
x = "Hello! "
y = "How are you "
z = "today?"
print(x + y + z)
문자열 3개를 하나의 메시지로 이어 출력하는 매우 간단한 프로그램이다.
위 프로그램이 데이터를 어떻게 조직했는지 다음과 같이 설명해 볼 수 있다.
문자열 3개가 있고, 각 문자열은 변수 하나씩 연결되어 있다.
이 책은 단순히 데이터를 조직하는 방법이 아니라,
데이터 조직이 코드의 실행 속도에 미치는 영향이 크다는 것을 가르치고자 한다.
데이터를 어떻게 조직하는가에 따라 프로그램은 수십수백 배 더 빠르게 혹은 더 느리게 실행될 수 있다.
대량의 데이터를 처리해야 하는 프로그램이나 수천 명이 동시에 사용하는 웹 앱을 개발한다고 가정하자.
여러분이 선택한 자료 구조가 소프트웨어가 잘 실행될지 혹은 처리량을 감당할 수 없어 멈춰버릴지를 결정할지도 모른다.
우리가 소프트웨어를 문제 없이, 빠르게 실행할 수 있는 명쾌한 코드를 작성하는 능력을 갖추고
소프트웨어 공학자가 가져야 하는 전문성을 키우려면
다양한 자료 구조를 알고, 각각의 자료구조가 개발 중인 프로그램의 성능에 어떤 영향을 미칠지 확실히
이해하고 있어야 한다.
1장은 배열과 집합이라는 2가지 자료 구조를 분석한다.
언뜻 보면 거의 동일해 보이지만, 앞으로 소개할 도구를 통해 성능에 미치는 영향이 어떻게 다른지 분석해 보자.
1.1. 배열: 기초 자료 구조
배열은 컴퓨터 과학에서 기초적인 자료 구조 중 하나다.
이미 배열을 다뤄봤을 테니 배열이 단순히 데이터 원소들의 리스트임을 알 것이다.
배열은 다양한 용도로 여러 가지 상황에서 유용한 도구로 쓰이지만, 여기서는 간단한 예제 하나만
다뤄보자.
마트에서 살 쇼핑 목록을 만들고 사용할 수 있는,
그런 애플리케이션의 소스 코드를 보는 중이라면 다음과 같은 코드를 찾을 수 있다.
string[] array = {"apples", "bananas", "cucumbers", "dates", "elderberries"};
배열에 들어있는 다섯가지 문자열은 마트에서 살 법한 식료품들이다.
배열의 인덱스는 특정 데이터가 배열의 어디에 있는지 알려주는 숫자다.
대부분의 프로그래밍 언어에서 인덱스는 0부터 시작한다.
예제의 배열도 마찬가지로, 다음 표처럼 "apples"는 인덱스 0, "elderberries"는 인덱스 4에 있다.
| "apples" | "bananas" | "cucumbers" | "dates" | "elderberries" |
| 인덱스 0 | 인덱스 1 | 인덱스 2 | 인덱스 3 | 인덱스 4 |
배열같은 자료 구조의 성능을 알려면 코드가 자료구조와 일반적으로 어떻게 상호작용하는지 분석해야 한다.
대부분의 자료 구조는 4가지 기본 방법을 사용하며, 이를 연산이라 부른다.
- 읽기
읽기는 자료구조 내 특정 위치를 찾아보는 것이다. 배열에서는 특정 인덱스의 값을 찾아보는 것을 뜻한다.
가령 인덱스 2에 들어 있는 물건을 찾는 게 배열의 읽기의 예다. - 검색
검색은 자료 구조 내에서 특정 값을 찾는 것이다. 배열에서는 특정 값이 배열에 득어 있는지, 만약 그렇다면 어떤 인덱스에 있는지 알아보는 것을 뜻한다.
예를 들어 "dates"가 식료품 목록에 있는지, 어떤 인덱스에 있는지 알아보는 게 배열 검색이다. - 삽입
삽입은 자료 구조에 새로운 값을 추가하는 것이다. 배열이라면 배열 내에 슬롯을 더 만들어 새 값을 추가하는 것을 뜻한다.
앞선 쇼핑 목록에 "figs"를 추가하는 게 배열에 새 값을 삽입하는 예다. - 삭제
삭제는 자료 구조에서 값을 제거하는 것이다. 배열에서는 배열의 값 중 하나를 제거하는 것을 뜻한다.
예를 들어 예제의 식료품 목록에서 "bananas"를 제거하는 게 배열 삭제다.
1장에서는 각 연산을 배열에 적용했을 때 얼마나 빠르게 수행되는지 알아본다.
이쯤에서 이 책이 다루는 첫 번째 깜짝 놀랄만한 개념이 나온다.
연산이 얼마나 "빠른가"를 측정할 때는 순수하게 시간 관점에서 연산이 빠른가가 아니라,
얼마나 많은 단계가 필요한가를 논해야 한다.
왜 그럴까?
누구도 어떤 연산이, 예컨대 정확히 5초가 걸린다고 단정할 수 없다.
같은 연산도 어떤 컴퓨터에서는 5초가 걸리고, 구형 하드웨어에서는 더 오래 걸릴 수도 있으며,
미래의 슈퍼 컴퓨터에서는 훨씬 빠를 수도 있다.
시간은 연산을 실행하는 하드웨어에 따라 항상 바뀌므로 시간을 기준으로 속도를 측정하면 신뢰할 수 없다.
대신 연산의 속도를 측정할 때 얼마나 많은 단계(step)가 필요한가를 따져볼 수 있다.
연산 A에 5단계가 필요하고 연산 B에 500단계가 필요하면, 모든 하드웨어에서 연산 A가 연산 B보다
항상 빠를 거라고 가정할 수 있다.
결국 단계 수를 측정하는 게 연산 속도를 분석하는 핵심 비결이다.
연산의 속드 측정은 연산의 시간 복잡도 측정으로도 알려져 있다.
이 책 전반에서 속도와 시간 복잡도, 효율성, 성능이라는 용어를 같은 의미로 사용하겠다.
4가지 용어 모두 주어진 연산에 걸리는 단계 수를 나타낸다.
이제 배열에 쓰이는 4가지 연산으로 돌아가서 각각 얼마나 많은 단계가 필요한지 알아내 보자.
1.2. 읽기
첫 번째로 살펴볼 연산인 읽기는 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾아보는 것이다.
배열에서 읽기는 실제로 딱 한 단계다.
컴퓨터는 배열 내 특정 인덱스에 한 번에 접근해서 볼 수 있기 때문이다.
string[] array = {"apples", "bananas", "cucumbers", "dates", "elderberries"};
앞선 식료품 예제에서 인덱스 2를 찾아본다면 컴퓨터는 인덱스 2로 바로 가서 "cucumbers"라는 값이 있다고 알려줄 것이다.
컴퓨터는 어떻게 단 한 단계로 배열의 인덱스를 찾아볼 수 있을까?
그 방법은 다음과 같다.
컴퓨터의 메모리는 셀로 구성된 거대한 컬렉션이라 할 수 있다.
다음 표는 격자로 된 셀을 보여준다.
어떤 셀은 비어있고, 어떤 셀에는 데이터가 들어있다.
| 9 | ||||
| 16 | ||||
| "a" | ||||
프로그램에서 배열을 선언하면 컴퓨터는 프로그램이 쓸 수 있는 연속된 빈 셀들의 집합을 할당한다.
예를 들어 원소 다섯 개를 넣을 배열을 생성하면,
컴퓨터는 한 줄에서 5개의 빈 셀 그룹을 찾아 사용자가 사용할 배열로 지정한다.
| 9 | ||||
| □ | □ | □ | □ | □ |
| 16 | ||||
| "a" | ||||
컴퓨터 메모리 내에 각 셀에는 특정 주소가 있다.
간단한 수로 표시한다는 점만 제외하면 일종의 거리 주소와 비슷하다.
각 셀의 메모리는 앞 셀의 주소에서 1씩 증가한다.
다음 표를 보자.
| 1000 | 1001 | 1002 | 1003 | 1005 |
| 1006 | 1007 | 1008 | 1009 | 1010 |
| 1011 | 1012 | 1013 | 1014 | 1015 |
| 1016 | 1017 | 1018 | 1019 | 1020 |
| 1021 | 1022 | 1023 | 1024 | 1025 |
이어지는 표는 인덱스와 메모리 주소를 표시한 쇼핑 목록 배열이다.
| "apples" | "bananas" | "cucumbers" | "dates" | "elderberries" |
| 1010 | 1011 | 1012 | 1013 | 1014 |
| 인덱스 0 | 인덱스 1 | 인덱스 2 | 인덱스 3 | 인덱스 4 |
컴퓨터가 배열의 특정 인덱스에 있는 값을 읽을 때 한 번의 단계로 바로 갈 수 있는데는 다음과 같은 점들이 복합적으로 작용한다.
- 컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있다.
- 각 배열에 저장된 내용은 메모리의 시작 주소다. 따라서 컴퓨터는 손쉽게 시작 주소를 얻는다.
- 배열의 인덱스는 0부터 시작한다.
앞선 예제에서 컴퓨터에 인덱스 3에 있는 값을 읽으라고 명령하면 컴퓨터는 다음과 같은 과정을 밟는다.
- 배열의 인덱스는 0부터 시작하며 인덱스 0의 메모리 주소는 1010이다.
- 인덱스 3은 인덱스 0으로부터 정확히 3슬롯 뒤에 있다.
- 따라서 인덱스 3을 찾으려면 1010+3인 1013메모리 주소로 간다.
1013이라는 메모리 주소에 접근한 컴퓨터는 "dates"라는 값을 반환한다.
보다시피 배열 읽기는 한 단계만에 끝나는 매우 효율적인 연산이다.
한 단계로 끝나는 연산은 당연히 가장 빠른 연산 유형이다.
배열이 그토록 강력한 자료 구조인 이유 중 하나는 어떤 인덱스의 값이든 빠르게 찾을 수 있기 때문이다.
그렇다면 컴퓨터에 인덱스 3에 들어 있는 값이 무엇인지 묻는 대신 배열이 "dates"를 포함하는지 물어보면 어떨까?
이를 검색 연산이라 부르며 다음 절에서 알아본다.
1.3. 검색
앞서 언급했듯이
