16. 애플리케이션 성능 개선
알고리즘
개념
문제를 해결하기 위한 절차나 방법
제시된 문제를 논리적으로 해결하기 위하여 절차, 방법 그리고 명령어들을 모아 놓은 것
알고리즘의 표현은 자연어, 순서도, 의사 코드, 프로그래밍 언어 등을 이용
조건
입력 : 알고리즘의 입력 데이터는 0 또는 그 이상의 외부에서 제공된 자료가 반드시 필요
출력 : 알고리즘은 최소 1개 이상의 결과 필요
명확성 : 알고리즘을 처리하는 각 단계는 명확하게 수행되어 모호함이 없어야 하며, 이를 위해서 순서도(flow chart)나 의사코드(pseudocode) 등의 표현 방법을 이용
유한성 : 알고리즘은 결과물을 도출하기 위하여 유한의 각 단계를 수행 후 문제를 해결하고 종료
효과성 : 알고리즘의 모든 유한의 각 수행단계는 유사한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순
설계 기법
분할 & 정복 | Divide & Conquer
문제를 더는 쪼갤 수 없을 때까지 작은 문제로 나누고, 이렇게 나누어진 작은 문제를 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방법
퀵 정렬, 합병 정렬, 이진 탐색 등에 사용
동적 계획법 | Dynamic Programming
큰 문제를 풀기 위해 작은 문제를 풀어 큰 문제를 풀어가는 방법
어떤 문제를 풀기 위해 그 문제를 더 작은 문제들로 나누고, 작은 문제들에서 구한 해를 어딘가에 저장한 다음 활용해 문제를 해결하는 알고리즘 설계 기법
탐욕법 | Greedy
그때그떄 가장 좋은 해결책을 찾아가는 방법
최소비용 신장트리 알고리즘(크루스칼, 프림 알고리즘)에서 사용
백트래킹 | Backtracking
더 이상 해가 없으면 왔던 길을 되돌아가서 다른 길을 찾아보는 방법
그래프에서 DPS(깊이우선탐색)에서 사용
성능 분석
- 알고리즘의 효율성을 높이기 위해서는 자원(시간과 공간)을 어떻게 소모하는가에 따른 분석
시간 복잡도 | Time Complexity
알고리즘의 수행시간을 분석한 결과
빅오(Big-O), 빅오메가(Big-Ω), 빅세타(Big-θ) 표기법 존재
빅오 표기법 유형 | 빠른 순서부터 나열
O(1)
- 문제를 해결하는데 오직 한 단계만 처리
- 스택, Hash 함수
O(log n)
- 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 감소
- 이진탐색
O(n)
- 문제를 해결하기 위한 시간이 입력값과 1:1 관계를 가짐
- 배열 순차 탐색
O(n log n)
- 문제를 해결하기 위한 단계의 수가 n*(log n)번 만큼의 수행 시간을 가짐
- 퀵정렬, 힙정렬, 병합정렬
O(n^2)
- 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱만큼의 수행시간을 가짐
- 버블정렬, 삽입정렬, 선택정렬
O(2^n)
- 문제를 해결하기 위한 단계의 수는 상수의 n제곱만큼의 수행시간을 가짐
O(n!)
- 문제를 해결하기 위한 단계의 수는 n의 팩토리얼 만큼의 수행시간을 가짐
공간 복잡도 | Space Complexity
알고리즘을 실행하여 종료할 때까지 필요한 기억 장치의 크기로서 자원 공간의 양을 의미
알고리즘과 밀접한 부분은 문제를 해결하기 위해 필요한 공간, 즉 변수를 저장하기 위한 공간
정렬알고리즘
선택 정렬 | Selection Sort
주어진 리스트 중에 최솟값을 찾아 비교 대상의 값과 교체
정렬을 위한 비교 횟수는 많지만, 실제 교환 횟수는 적음
37 14 17 40 35
14 37 17 40 35
14 17 37 40 35
14 17 35 40 37
14 17 35 37 40
삽입 정렬 | Insertion Sort
현재 값이 들어가야 할 자리를 찾아서 삽입하는 방식
비교횟수를 줄이기 위해 고안된 정렬 방법
자료가 어느 정도 정렬이 되어 있을 경우 빠른 성능을 가짐
8 3 4 9 7
3 8 4 9 7
3 4 8 9 7
3 4 7 8 9
버블 정렬 | Bubble Sort
인접한 값만 계속 비교하면서 수행하는 단순한 정렬 알고리즘
모든 인접값을 비교해야하기 때문에 비효율적
4 7 3 1
1회전
4 7 3 1
4 3 7 1
4 3 1 72회전
3 4 1 7
3 1 4 7
3 1 4 73회전
1 3 4 7
퀵 정렬 | Quick Sort
기준 값에 의한 분할을 통해서 구현하는 정렬법
분할 과정에서 O(log n)의 시간이 걸리고, 전체적으로 O(n log n)의 시간복잡도를 가짐
기준값(Pivot)에 따라서 시간복잡도가 O(n^2)될 수 있음
힙 정렬 | Heap Sort
추가적인 메모리를 불필요
항상 O(n log n)의 시간복잡도를 가짐
병합 정렬 | Merge Sort
퀵 정렬과 비슷하게 원본 배열을 반씩 분할해 가면서 정렬하는 방법
추가적인 메모리 필요
쉘 정렬 | Shell Sort
- 삽입 정렬의 단점을 보완해서 만든 정렬법
기수 정렬 | Radix Sort
분배 방식의 정렬 방법
정렬할 원소의 키값에 해당하는 bucket에 원소를 분배하였다가 bucket의 순서대로 원소를 꺼내는 방법을 반복하여 정렬을 수행
검색 기법
선형 검색 | Linear Search
배열의 가장 좌측부터 시작하여 찾으려는 값과 하나씩 배열의 각 요소와 비교하여 검색
O(N)의 시간복잡도
이진 탐색 | Binary Search
검색 반경을 반으로 나누어 반복하는 검색 방법
정렬된 배열에서 사용 가능
찾으려는 값을 배열의 중간값과 비교하여 그 값이 더 작다면 우측 배열, 크다면 좌측 배열로 이동하여 반복
O(n log n)의 시간복잡도
보간 검색 | Interpolation Search
- 정렬이 이미 되어 있는 리스트에서 검색값이 존재할 위치를 예측하여 검색하는 방법
소스코드 품질 분석 도구
개념
코딩을 하면서 발생하는 문제를 해결하기 위해 사용하는 도구
소스코드의 코딩 스타일, 코딩 표준, 코드의 복잡도, 메모리 누수 현상, 스레드 결함과 같은 소스코드로 인해 발생하는 문제를 찾기 위해 사용
분류
정적 분석 도구
프로그램을 실행하지 않고 소프트웨어를 분석하는 방법
소스 코드의 결함 및 취약성을 찾기 위한 도구
소프트웨어 코드 내에 잠재된 오류, 버그, 보안취약점 등의 각종 결함들을 소스코드 분석을 통하여 탐지
PMD
- 주로 Java에서 사용하지만, Javascript, PLSQL, XML 등의 언어도 지원
checkstyle
- 자바 코드에 대한 소스 코드 표준 준수 검사, 다양한 개발 도구에 통합 가능
SonarQube
- 중복코드, 복잡도, 코딩 설계 등을 분석하는 소스 분석 통합 플랫폼
cppcheck
- C, C++코드에 대한 메모리 누수, 오버플로우 등 문제 분석
ccm
- 다양한 언어의 코드 복잡도 분석 도구
cobertura
- 자바 언어의 소스 코드 복잡도 분석 및 테스트 커버리지 측정
동적 분석 도구
- 프로그램을 실행하여 코드에 존재하는 메모리 누수나, 스레드의 결함 등을 발견
Avalanche
- 프로그램에 대한 결함 및 취약점 분석
Valgrind
- 프로그램 내 존재하는 메모리 및 스레드 결함 등 분석
소스코드 복잡도 분석
McCabe 순환복잡도 | Cyclometic Complexity
논리적인 복잡도를 정량적으로 측정하기 위한 제어 흐름을 그래프로 표현하는 측정 지표
정량 지표, 구조적 평가, 간접 방식
CC = E(간선의 수) - N(노드의 수) + 2
코드 최적화
개념
주어진 코드에 대해 같은 작업을 수행하면서, 실행 시간을 줄이거나 메모리를 줄이는 것
기존의 방법보다 계산 횟수를 줄이거나 실행 시간을 더 짧고, 기억 용량을 더 적게 코드를 작성
알고리즘을 개선하거나, 병목 현상을 제거
소스코드를 가지고 협업하거나, 유지운영을 위해 소스코드를 다른 사람들이 읽기 쉽게 작성
소스코드 리팩토링을 통해서 코드 스멜을 제거하고 품질 좋은 코드를 작성
코드 스멜 | Code Smell
같은 코드가 여러 곳에 존재하는 중복된코드로 코드 스멜이 발생
클래스, 메소드, 함수, 프로시저의 길이가 매우 길어져서 발생
다른 클래스의 메소드들을 너무 많이 사용하는 기능 의존으로 발생
다른 클래스의 구현에 세밀하게 의존하는 클래스로서 부적절한 관계를 형성
상속을 거부하는 현상으로 부모 클래스의 규약을 지키기 않은 채, Method Override를 하는 경우에 발생
Spaghetti code
- 소스코드가 복잡하게 얽힌 모습을 스파게티의 면발에 비유한 표현
- 스파게티 코드는 정상적으로 작동하지만, 사람이 코드를 읽으면서 그 코드의 작동을 파악하기는 어려움
- GOTO문을 지나치게 많이 사용하거나, 프로그램을 구조적으로 만들지 않는 경우에 만들어지기 쉬움
외계인 코드
- 아주 오래되거나 참고 문서 또는 개발자가 없어 유지보수 작업이 어려운 프로그램 코드
Refactoring
외부 동작을 바꾸지 않으면서 내부 구조를 개선하는 방법
코드가 작성된 후에 디자인을 개선하는 작업
모든 것을 미리 생각하기 보다는 개발을 하면서 지속적으로 좋은 디자인을 탐색
이미 작성한 소스코드에서 구현된 일련의 기능을 변경없이, 코드의 가독성과 유지보수성을 높이기 위해 내부 구조를 변경하는 것
주요 리팩토링 기법
메서드 정리
객체 간 기능 이동
이름 변경
추측성 일반화
클린코드
개념
- 의존성을 최소로 하고 사람이 이해할 수 있는 가독성, 목적성이 뛰어난 명확한 코드
특징
의존성 최소화
단일 책임의 원칙
버그 유입 최소화
가독성 향상
중복코드 최소화
변경 용이
작은 코드
구현 방법
클래스명, 메서드명, 변수명은 명사를 사용하여 의미가 있는 이름을 지음
불필요한 주석을 제거하고 의도를 명확히 기술한 주석을 작성
리팩토링을 통해 점진적인 개선을 통해 코드의 복잡도를 낮게 함
코드는 가급적 기능별로 간단하게 작성
코드의 중복을 최소화
누구든지 코드를 쉽게 읽을 수 있도록 작성
다른 모듈에 미치는 영향을 최소화하여 작성
작성 원칙
가독성
- 누구든지 코드를 쉽게 읽을 수 있도록 작성
- 코드 작성 시 이해하기 쉬운 용어를 사용하고, 들여쓰기 등을 이용
단순성
- 코드를 간단하게 작성
- 한 번에 한 가지를 처리하도록 코드를 작성하고 클래스/메소드/함수 등을 최소 단위로 분리
의존성 배제
- 코드가 다른 모듈에 미치는 영향을 최소화
- 코드 변경 시 다른 부분에 영향이 없도록 작성
중복성 최소화
- 코드의 중복을 최소화
- 중복된 코드는 삭제하고 공통된 코드를 사용
추상화
- 상위 객체는 간략하게 기능적 특성을 나타내고, 상세 내용은 하위 객체에서 구현