코드 품질은 코드 유지 보수성(가독성, 조직, 코드 모듈성 같은 측면을 포함)과 코드 효율성 같은 측면을 포함한다. 이 책은 효율적인 코드 작성법을 다룬다.

자료 구조

• 데이터: 모든 유형의 정보를 망라하는 용어, 가장 기초적인 수와 문자열로 이뤄짐
• 자료구조: 데이터를 조직하는 방법, 코드의 실행 속도에 미치는 영향이 큼

배열: 기초 자료 구조

• 배열: 데이터 원소들의 리스트 ex) ['apple', 'banana']
  • 크기: 배열에 데이터 원소가 얼마나 들어있는지 알려줌
  • 인덱스: 특정 데이터가 배열의 어디에 있는지 알려주며 대부분의 프로그래밍 언어에서 인덱스는 0부터 시작
• 자료 구조 연산: 읽기, 검색, 삽입, 삭제

속도 측정

연산 속도는 얼마나 많은 계산 단계가 필요한가(시간 복잡도)를 따져봐야 한다. 시간은 하드웨어에 따라 바뀌므로 시간 기준 속도 측정은 신뢰할 수 없다.

읽기

컴퓨터는 모든 메모리 주소에 검색 과정 없이 한 번에 갈 수 있기 때문에 한 단계를 거쳐 배열의 인덱스를 찾아볼 수 있다.

• 컴퓨터의 메모리는 셀로 구성된 거대한 컬렉션이다.
• 만약 배열을 선언하면 컴퓨터는 연속된 빈 셀들의 집합을 할당한다.
• 이 때 어떤 메모리 주소에서 시작하는지도 기록해 둔다.
• 시작 주소에서 간단한 덧셈을 수행해 데이터를 읽는다.

검색

읽기가 컴퓨터에 인덱스를 제공하고 그 인덱스에 들어 있는 값을 반환하라고 요청한다면, 검색은 컴퓨터에 값을 제공하고 그 값이 들어 있는 인덱스를 반환하라고 요청한다.

• 컴퓨터는 각 메모리 주소에 어떤 값이 들어있는지 바로 알지 못한다.
• 한 번에 한 셀씩 확인(선형 검색)하며 연산을 수행한다.
  찾는 값이 마지막 셀에 있거나 찾는 값이 어떤 셀에도 없을 때 최대로 많은 단계를 거치며, 이는 배열의 크기와 같다.

삽입

배열의 어디에 데이터를 삽입하는지가 효율성을 결정한다.

• 맨 끝에 삽입: 배열을 할당할 때 컴퓨터는 배열의 크기를 기록하기 때문에 메모리 주소를 계산해 마지막 셀 다음 셀에 항목을 추가한다. 한 단계가 필요하다.
• 맨 처음이나 중간에 삽입: 데이터 조각을 이동시켜야 해서 단계가 늘어난다. 배열의 맨 앞에 삽입하면 배열 내 모든 값을 (마지막 셀부터) 한 셀씩 오른쪽으로 옮겨야 하며, 옮긴 뒤에 삽입을 해야하기 때문에 '배열의 크기 + 1' 단계가 걸린다.

삭제

삭제는 한 단계가 걸리지만, 배열 중간이 비게 되므로 데이터 조각들의 이동이 필요하다.

• 최악의 시나리오는 배열의 첫 번째 원소를 삭제하는 것이며, 삭제 한 단계, 이동 '배열의 크기 - 1' 단계가 필요하므로 배열의 크기 만큼의 단계를 거치게 된다.

집합: 단 하나의 규칙으로 효율성이 달라진다.

• 집합: 중복 값을 허용하지 않는 자료 구조
• 배열 기반 집합: 중복 금지 제약이 추가된 배열이다.

읽기와 검색, 삭제는 기존 배열과 시간복잡도의 차이가 없지만, 삽입에서 차이가 발생한다. 집합에서는 값이 집합에 들어 있는지부터 결정해야 하기 때문에 '검색'이 우선이다.

• 맨 끝에 삽입: 원소 N개에 대해 'N(검색) + 1(삽입)' 단계가 필요하다.
• 맨 앞에 삽입: 원소 N개에 대해 'N(검색) + N(데이터 이동) + 1(삽입)' 단계가 필요하다.