https://www.coursera.org/learn/data-driven-astronomy
--------------------------------------------------------
Week 2: Big data makes things slow
제2주차: 자료가 방대해지면 뭘하든 느려진다.
- How to work out the time complexity of algorithms
복잡한 계산을 빠르게 수행하는 방법
- Exploring the black holes at the centers of massive galaxies
거대 은하의 중심부 블랙 홀 찾기
--------------------------------------------------------
1강: 방대한 자료는 일을 더디게 만든다
Lesson 1: Big Data makes things slow / 한글자막
--------------------------------------------------------
2강: 초거대 블랙홀과 활동성 은하 핵(AGN)
Lesson 2: Supermassive Black Hole / 한글자막
--------------------------------------------------------
3강: 교차정합(cross-matching) 알고리즘에 대하여
Lesson 3: What is cross-matching ? / 한글자막
--------------------------------------------------------
4강: 실행 시간 복잡도 평가
Lesson 4: Evaluating Time Complexity / 한글자막 / 영문자막
[강의대본]
[MUSIC]
[MUSIC]
[00:06]
우리가 만든 느슨한 교차정합 알고리즘의 복잡성이 선형적이지 못하다는 것을 알게됐다. 각 목록에 포함된 은하의 갯수가 열배 늘어날 수록 실행 시간은 100배 그러니까 10의 제곱배로 늘어난다. 그럼 양 목록의 길이를 일부러 같은 크기에 맞춰 늘려보기로 하자. 좀더 엄밀히 말하면 이 알고리즘의 복잡성 규모는 n 곱하기 m의 비율로 증가한다.
[00:26] 만일 n 이 첫번째 목록(Catalogue 1)에 포함된 은하의 갯수라면 m을 두번째 목록(Catalogue 2)의 은하 갯수라고 하자. 알고리즘의 복잡성을 측정하는 방법으로 입력에 대한 함수로 표현한다. 이를 시간 복잡성(Time Complixity)이라 한다. 때로는 이를 대문자 O를 사용한 함수로 나타낸다. 우리의 느슨한 교차정합 알고리즘의 복잡성을 온전히 표현하면 다음과 같다. 이 알고리즘의 복잡성의 척도를 한마디로 하면 O(nm)가 된다.
------------------------------------------------------------
* Time Complexity: 어떤 알고리즘이 실행되어 완료될 때 까지 걸리는 시간이다. 알고리즘이 복잡 할수록 소요시간은 길어진다. 즉, 실행 시간으로 알고리즘의 복잡도를 평가한다. 이는 수학적 의미와 약간 다른 측면이 있는데, 가령 곱셈과 덧셈의 복잡도를 따지면 당연히 곱셈의 복잡도가 높다. 하지만 덧셈이나 곱셈이 단일 명령으로 실행되는 컴퓨터라면 이 두 연산의 복잡도는 같다. 심지어 산술연산(arithmetic operation)과 할당(assignment, =)도 같은 복잡도로 친다. 곱셈을 한번 하던 변수에 값을 저장하던 기계의 입장에서는 한번의 동작을 했을 뿐이다. 컴퓨터 과학에서 알고리즘의 복잡도는 그 연산의 종류가 무엇이든 상관없이 연산의 횟수를 따진다.
** 위의 '시간 복잡성'을 표현한 수식에서 a, b, c는 1회 동작을 수행 했을 때 소요되는 시간 상수다. 우리 알고리즘이 입력 갯수 n와 m을 가지고 2중으로 반복 실행 되었음을 상기하자. 따라서 총 반복되는 횟수는 n 과 m 의 곱과 같으며 한 반복에서 소요되는 시간이 a 다. b 는 n 개의 입력에 대한 반복, c 는 m 개의 입력에 대한 반복시 각각 1회의 반복에서 소요되는 시간을 의미한다. 위의 복잡도 수식에서 a, b, c를 계수 상수로 놓자. O(n) 이나 O(m)은 선형적인데 비해 O(mn) 제곱이다. 따라서 전체 복잡도가 n 과 m의 곱에 의해 지배될 것이므로 복잡도는 O(mn)로 평가한다.
* Time Complexity: 어떤 알고리즘이 실행되어 완료될 때 까지 걸리는 시간이다. 알고리즘이 복잡 할수록 소요시간은 길어진다. 즉, 실행 시간으로 알고리즘의 복잡도를 평가한다. 이는 수학적 의미와 약간 다른 측면이 있는데, 가령 곱셈과 덧셈의 복잡도를 따지면 당연히 곱셈의 복잡도가 높다. 하지만 덧셈이나 곱셈이 단일 명령으로 실행되는 컴퓨터라면 이 두 연산의 복잡도는 같다. 심지어 산술연산(arithmetic operation)과 할당(assignment, =)도 같은 복잡도로 친다. 곱셈을 한번 하던 변수에 값을 저장하던 기계의 입장에서는 한번의 동작을 했을 뿐이다. 컴퓨터 과학에서 알고리즘의 복잡도는 그 연산의 종류가 무엇이든 상관없이 연산의 횟수를 따진다.
** 위의 '시간 복잡성'을 표현한 수식에서 a, b, c는 1회 동작을 수행 했을 때 소요되는 시간 상수다. 우리 알고리즘이 입력 갯수 n와 m을 가지고 2중으로 반복 실행 되었음을 상기하자. 따라서 총 반복되는 횟수는 n 과 m 의 곱과 같으며 한 반복에서 소요되는 시간이 a 다. b 는 n 개의 입력에 대한 반복, c 는 m 개의 입력에 대한 반복시 각각 1회의 반복에서 소요되는 시간을 의미한다. 위의 복잡도 수식에서 a, b, c를 계수 상수로 놓자. O(n) 이나 O(m)은 선형적인데 비해 O(mn) 제곱이다. 따라서 전체 복잡도가 n 과 m의 곱에 의해 지배될 것이므로 복잡도는 O(mn)로 평가한다.
<그림> 반복과 소요시간
[참조] Analysis of Algorithm, https://www.coursera.org/learn/analysis-of-algorithms
------------------------------------------------------------
* 가로축은 알고리즘의 수행시 소요되는 입력의 갯수(Elements), 세로축은 연산의 총 횟수(Operation)다.
[01:08] 이런 모든 평가에서 프로그램이 작성된 내용(code)중 주요부의 실행 시간(위의 복잡도 평가식에서 a, b, c 를 의미함) 만을 따져보고 있다는 점에 주목하자. 프로그램이 시작되기 위해 한번 거치는 준비과정,예를들면 프로그램이 적제되고 자료를 읽어들이는 과정에서 소요되는 시간은 제외한다. (프로그램 준비 및 알고리즘 개시전 초기화) 이런 과정도 물론 시간계산의 척도에 중요하긴 하나 한번 실행되고 마는(one-off) 것이기 때문이다. 그것들은 전체 실행시간 증가 척도를 평가할 때 고려할 요소는 아니다.
00:01:24.584 --> 00:01:26.825
이제 알고리즘의 실행시간의 평가를 마쳤으면 다음은 이를 개선할 방도를 찾아야 한다. 만일 처음 알고리즘의 구현이 지금 우리 것처럼 매우 느슨한 것이었다면 속도를 높일 수 있는 여지가 매우 많다. 우리의 교차정합 알고리즘의 경우 실행시간 증가요인이 n 과 m 의 곱이 된 이유는 첫 목록에 담긴 각 은하 마다 두번째 목록의 모든 은하에 대해 비교를 실시하고 있기 때문이다.
[01:47] 이럴 때마다 매번 대원 각거리(a great circle distance)를 계산하고 있다. 매우 복잡한 수학이 동원되는 이 각거리의 계산에 시간이 많이 든다. 따라서 필요한 계산 횟수를 줄일 수는 없을까?
[01:58] 여러가지 생각이 떠오를 줄 안다. 하지만 한가지 예로 간단한 방법 하나만 소개해보기로 하겠다. 그러니까 두번째 목록에 있는 은하의 적위(Declination)를 오름차순으로 배열해 놓자. 그리고 첫번째 목록에 있는 매 은하에 대하여 구하고자 하는 최대 대원 각거리를 알고 있다.
[02:07] 따라서 최대 각거리를 벗어나는 위치에 있는 은하를 만나면 즉시 반복 계산을 멈춘다. 거리로 유사성을 찾으려 하는데 이 범위를 벗어나면 정합을 시도할 필요가 없다. 이는 마치 우리가 관심을 두고 있는 범위에 대략적인 금을 쳐놓은 것과 같다. 그리고 그 금안에 든 대상들 만 정확한 거리계산을 실시한다. 이를 근거로 새로 작성한 프로그램은 다음과 같다.
[02:07] 따라서 최대 각거리를 벗어나는 위치에 있는 은하를 만나면 즉시 반복 계산을 멈춘다. 거리로 유사성을 찾으려 하는데 이 범위를 벗어나면 정합을 시도할 필요가 없다. 이는 마치 우리가 관심을 두고 있는 범위에 대략적인 금을 쳐놓은 것과 같다. 그리고 그 금안에 든 대상들 만 정확한 거리계산을 실시한다. 이를 근거로 새로 작성한 프로그램은 다음과 같다.
[02:35] 이제 이렇게 변경한 프로그램이 얼마나 효과가 있을지 살펴보면 흥미롭다. 새 알고리즘을 시험해보기 위해 이전에 사용했던 전략을 동일하게 적용한다. 교차정합을 실행 할 때마다 다른 규모의 목록을 적용해 본다. 지난번 강의에서 두 목록의 교차정합을 실시하며 소요된 시간을 측정하면서 각 목록에 백만개의 은하를 넣어 놨었다. 슬로언 디지털 스카이 서베이(SDSS)를 통해 관측된 은하의 갯수가 대략 그정도다.
[02:59] 이제 계산을 해보자. 느슨한 교차정합으로는 1천개의 은하가 담긴 목록에 대해 약 5초가량 소요됐었다. 단지 위치 좌표를 탐색하기 전에 라디안으로 바꿔놓은 것 만으로도 2초가 걸리는 속도 향상의 효과를 봤다. 실행 시간이 n 과 m의 곱에 비례한다는 것을 알고 있다. 따라서 우리의 프로그램은 n 과 m 이 각각 1백만개인 두 목록을 처리하는데 소요될 실행 시간은 2백만 초가 될 것이다. 이는 556시간이며 대략 24일이 걸리는 셈이다.
[03:25] 이번에는 개선된 프로그램(improved cross-match)을 사용하여 이 시간 계산을 다시 해보자. 개선된 프로그램에서는 매번 정합을 실시할 때 마다 평균적으로 절반의 시간이 소요된다. 이는 1천개의 항목이 담긴 두 목록을 정합하는데 단 1초로 실행 시간이 단축된다. 하지만 여전히 알고리즘의 복잡도가 n 과 m 의 곱에 있다. 따라서 전반적으로 이 프로그램의 속도를 두배로 높인다 해도 12일이 걸린다.
[03:49] 약간의 컴퓨터 활용에 대한 생각(computational thinking)과 몇줄의 코드를 추가하는 것으로 프로그램 실행 속도를 두배나 올려 실행 시간을 12일로 단축 했다. 이정도면 해볼만 하다 싶을 수도 있다. 하지만 아직 뭔가 더 할 것이 남아보인다. 비록 속도가 향상되긴 했지만 근본적으로 해결된 것은 아니다. 최악의 경우를 상정 해보자. 만일 두번째 목록에 담긴 모든 대상들이 첫번째 목록과 비교할 탐색 범위내에 있다고 해보자. 비교할 대상의 갯수와 계산은 여전하게 된다. 그리고 프로그램은 그전만큼 느려질 것이다. 왜 이렇게 됐을까?
[04:23] 속도 향상을 위해 취할 수 있는 여러 방도가 있다. 예를 들어,
- 실행 속도가 빠른 언어로 프로그램을 작성 할 수 있다(Program language). 보통 C 언어가 이면에서 유리하다.
- 같은 언어에서도 자료구조(Data structure)를 변경 하는 방법도 있다. 예를 들어 파이썬 NumPy 라이브러리에서 리스트(List) 대신 배열(Array)을 사용하면 조금 빠르다.
- 또는 문제에 맞게 부호처리에 특화된 함수(Specialized routine)를 만들어 보는 방법도 있다. 때로 이런 방법들은 더빠른 언어로 작성할 때 덤으로 주어지기도 한다.
- 근본적으로 프로그램을 효율적이 되도록 재설계(Redesign) 할 수도 있다.
- 끝으로, 알고리즘의 핵심부의 시간 복잡성(Time complexity)을 향상 시킬 수도 있을 것이다.
[04:50] 어쩌면 위에서 우리가 해봤던 것처럼 여러분 스스로 구현해 보면서 실용적인 개선점을 찾을 수도 있다. 컴퓨터 과학자도 미처 생각치 못한 특이한 방법이 있을 지도 모른다. 지금까지 우리가 살펴봤던 것은 시간 복잡성을 따지는 공식에서 상수 인자를 줄이는 방법에 관한 것이었다. 이에 대해 실습과정에서 자세히 다뤄 보기로 하자. 우리 프로그램을 상당히 개선하긴 했지만 여전히 만족 스럽지 못할 만큼 느리다. 다음 강의에서 또다른 접근 방법은 없는지 찾아 보기로 하자.
----------------------------------
댓글 없음:
댓글 쓰기