2018년 7월 10일 화요일

2주 부록: 천문학자 브랜든 브루어와의 인터뷰

[커세라 강좌 소개] 자료기반 천문학(Data-Driven Astronomy)
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 / 한글자막
--------------------------------------------------------
Lesson 5: A (much) faster algorithm / 한글자막
--------------------------------------------------------
2주 요약: 대량의 관측자료분석, 누군가 같은 고민을 했을 것이다.
Mudule Summary / 한글자막
--------------------------------------------------------
2주 부록: 천문학자 브랜든 브루어와의 인터뷰
Interview with Brandon Brewer / 한글자막 / 영문자막



[베이즈 확률론으로 우주를 이해하는 법]

* 이번주 인터뷰는 좀 특이하다. 우주현상의 연구에 베이즈 확률 통계학을 적용하는 학자와의 인터뷰. 내용에 상당히 추상적인 내용을 담고 있다. 시작하기 전에 약간의 지식을 가지고 보는것이 좋다.

베이즈 확률론(Bayesian probability)은 확률을 '지식 또는 믿음의 정도를 나타내는 양'으로 해석하는 확률론이다.[1] 확률을 발생 빈도(frequency)나 어떤 시스템의 물리적 속성으로 여기는 것과는 다른 해석이다. 이 분야의 선구자인 18세기 통계학자 토머스 베이즈의 이름을 따서 명명되었다.

* 대화체 문장이 많고 추상적인 내용을 담고 있음. 우리말로 옮기는데 한계가 있으니 원문과 동영상을 보면서 참고 바람.

[00:06] 안녕하세요, 저는 브랜든 브루어 입니다. 오클랜드 대학교 통계학과에서 강의하고 있어요. 저는 원래 물리학으로 박사학위를 받았고 그 과정에서 자료분석 방법론에 빠졌죠. 그때 제 친구가 저와 통계학의 관계를 이렇게 말했죠. 나와 통계학 사이가 마치 연애 드라마 같다고 했는데 둘 사이가 끝까지 가긴 하지만 아직 미심쩍은 뭔가 있다는 겁니다. 그래서 나는 뭔가 석연찮은게 있다고 생각 했죠. (뭔가 석연치 않아서 이 연구를 파보기로 했다.)

[00:38] [통계학과 천문학 사이에 어떤 연관성이 있을까요?]

사람들이 궁금해 하는 과학적인 질문과 그들이 가지고 있는 자료가 서로 직접적인 관계가 있다고 믿곤 합니다. 하지만 대개 그렇지는 않죠.

*사람들이 과학적인 질문을 할 때 직접적인 자료(근거)를 가지고 있다고 생각하지만 실제론 그렇지 않다.(자신이 가진 자료와 엉뚱한 질문을 한다)

왜 그런지 잘 설명할 수는 없겠지만 제 생각은 이렇습니다. 그러니까 별과 은하와 우주을 모두 통하는 어떤 결론 말이죠. 대개 어떤 자료가 뭔가 조금이라도 설명해 줄 수 있을 것이라고 합니다. 아니면 간접적이라도 말이죠. 하지만 그런 설명은 원하는 직접적인 답이 되진 못합니다.

*작은 단서를 가지고 온전한 답을 얻었다고 할 수 없다.

그래서 제가 하는 일은 우리가 어떤 질문에 답을 줄 수 있는 자료의 신빙성의 정도를 나타내는 확률이론에 관한 겁니다.

*베이즈 확률론:'지식 또는 믿음의 정도를 나타내는 양'으로 해석하는 확률론

[01:27] [베이즈 통계학은 뭐가 다르죠?]

보통 우리는 어떤 질문에 대답을 할 수 있으려면 가정이 참이어야 합니다. 우리가 얻고 싶은 자료는 무엇일까요? 중력 렌즈 현상에서 한 예를 들어보면 한 은하 앞에 다른 은하가 있다고 합시다. 그리고 앞에 있는 은하가 뒤에있는 은하의 빛을 휘게해서 아인슈타인 원을 보게 되는 거죠. 따라서 뒤에 있는 은하의 실제 모습을 보지 못하고 어떤 식으로든 왜곡된 것을 보는 겁니다. 그리고 관측으로 그렇게 나왔으니 왜 그런지 알고 싶겠죠. 어떻게 뒤에 있는 은하가 이렇게 혹은 저렇게 보일 거라고 확신할 수 있을까요? 아니면 이게 클까, 저게 클까, 뭐가 됐든 그것에 대해 알고 싶을 겁니다. 그럼 모델에 맞춰보는(model fitting) 일련의 과정을 수행 할 수 있습니다. 그리하여 과학적인 답이 될 모든 모든 가정을 세우게 됩니다. 그 가정들을 세우는 일은 원칙적으로 이론을 바탕으로 하면 그리 까다롭진 않죠. 맞아야 한다고 생각한 모든 이론(아이디어)을 되도록 많이 취할 겁니다. 그리고 나서 그 모든 이론들을 자료에 맞춰보고 어긋나는 이론은 제거해 나갑니다. 결국 옳다고 믿을 만한 범주에 놓인 하나를 갖게 되겠죠. 물론 이 과정은 실제로는 생각했던 것보다 복잡합니다. (웃음)어쨌든 기본(베이즈)이론은 크게 다르지 않습니다.

[02:43] [베이즈 통계이론은 어떻게 작동하나요?]

어떻게 작동하는지 알고 싶다면 직접 한번 생각해보는 것도 한 방법이죠. 사람들은 때로 지레 걱정을 하는데 가설을 끼워 넣어야 하기 때문이죠. 예를들어 자료를 수집하기전에 불확실성을 묘사하는 사전(확률)분포(prior distribution)라고 부르는 것인데 그 가설이 사람들을 다소 불편하게 만드는 개념의 한 종류 입니다. 하지만 관련된 수학을 조금 들여다보고 실제 해야할 일과 결과로 얻어낼 것이 무엇인지 살펴보면, 그리고 실제로 내가 가진 자료와 그 가설들을 취해보면 어떤 결론에 도달할 것입니다. 그리고 어쨌든 진실(그결론)이 여전히 합당한 답을 얻을 거라고 생각하는 가설들에서 벗어났는지 알 수 있을 거나는 보장은 없죠. 하지만 그것(맞다는 보장을 할 수 없다고해서)이 가설들의 결말을 찾아내는 것이 가치가 없다는 뜻은 아닙니다. 만일 가성을 세우고 결말을 추정해 보는 것을 모형화의 일환이라고 생각할 수 있죠. 그것은 마치 내가 이렇게 가정하고 그 결론은 이렇게 될 것이라고 관찰하는 것과 같습니다. 그리고 20여년의 세월동안 누군가 당신이 생각지도 못했던 또다른 생각을 해왔을 것이며 그 이론이 이제껏 해온 분석방식보다 실제로 더낳은 결과를 보일 것이란 것을 알게됩니다. 이것이 열린 결말이라 할 것입니다.

[03:57] [당신이 사용하는 자료 방법과 기법은 어떤 것이 있나요?]

가장 중요한 분석 기법 중 하나는 사람들이 천문학에 적용할 필요가 있는 것들인데 자료에 적합한 모형(fit model) 입니다. 그것(모형과 자료)는 뗄 수 없는 관계죠. 여러분이 읽게될 모든 논문과 나누게될 모든 대화에 대해 누군가 확실한 증거를 가지고 결론이 어덯게 될지 아는 모형을 가지고 있다면 인수 값을 메기기 위해 자료를 거기에 맞춰야 합니다. 그리고 그렇게 할 서로다른 방법이 오만개나 있다고 하죠. 그일을 수행할 실용적인 계산 방법이 있습니다. 저는 마코프 체인 몬테 카를로라고 하는 방법을 즐겨 씁니다. 그 방법은 인수들을 이리저리 무작위로 바꾸는데 이전에 시도했던 것을 기억하며 계산을 반복하죠.

*통계의 의미: 이전 (확률)값을 기억한다

그리하여 몇개의 (전이할)지점을 확보하고 그곳에 직통하도록 조정합니다.(전이 확률을 높임) 아마 처음에는 잘 맞지 않는 몇개의 직선(전이경로)으로 시작할 겁니다. 그런 다음에 변경된 인수들을 제시하죠. 그리하여 더 기울거나 덜 기울거나 위나 아래로 이동된 직선을 만들어 냅니다. 마침내 더 잘 들어 맞는 연결도가 만들어지면 그것을 채택 합니다. 그리고 만일 인수변경으로 인해 좋지않은 결과를 낳더라도 그것을 받아들여야 하는 이유있는 확률이 있을 겁니다. 그러니까 내리막길도 있는 법이죠. 그리고 결국 자료에 맞춰진 직결선을 만들어 줄텐데 그것이 바로 베이즈 방식 확률론에 근거한 결과죠.

[05:23] [네, 그렇다면 정통 통계학과 생각하는 방식이 다른건가요?]

제가 이 방법에 몰두하게된 또다른 이유는 기초개념과 원리 때문 입니다. 통계학의 관점에서 보면 두가지 차이점이 있죠. 그중 하나가 여기서 봤다시피 방대한 분량의 조리법이 있다는 것이고 상황에 직면 했을 때 그에 적절한 조리법을 하나 골라 시행 할 수 있다는 겁니다. 저는 베이즈 방식이 있다는 것을 알 았을 때 아주 기뻣습니다. 몇가지 기초원리를 가지고 있는 대신 그 원리라는 것이 격은 혹은 격을 지도 모르는 이전 정보를 표현하는데, 그러니까 그것이 자료와 어떻게 연관되는지 밝혀내고 방향을 꺽어 결과를 얻어 냅니다. 이러한 얼마나 이 가정이 강력하고 이런 자료가 그 결과를 암시하는지 바로 그것이죠. 그리고 모든 여러 다른 조리법 혹은 다수의 서로다른 조리법이 내게 이리저리 강구해 보라고 말하는 요리책. 그것은 내가 이전에 사용하던 정보가 어떤 것이었는지 가정 했던것과 일치.

[06:27] [이 분야에서 일하는 즐거움이 뭘까요?]

저는 한 문제에 대해 여러가지 가능성을 줄 수 있다는 것을 좋아합니다. 그리고 문제 해결에 'Numerical Recipes'의 220 쪽에 나온 방법을 적용 했다고 말하는 것이 싫어요. 그대신 이렇게 말하길 좋아합니다.

음... 이것은 우리가 찾는 과학 프로그램의 논리 중 하나구나...

우리가 아는 물리학이 여기에 있어요. 그것은, 우리의 관측자료에 망원경에 따른 잡음이 낀다는 것을 알고 있죠. 그리고 또 확률 이론이란 것이 있죠. 이제 그 둘을 합쳐서 어떤 결론에 도달하게 될지 생각해보세요. 그건 확실 합니다. 온갖 것을 기억할 필요는 없어요.

[07:13] [베이즈 방법을 적용 했을 때 초창기 분위기는 어땠 을까요?]

천문학계는 통계학 쪽으로 오랜동안 좋은 경험을 해왔다는 생각이 들어요. 그리고 이쪽 학계에는 폭넓은 가능성을 가지고 있다고 봅니다. 여전히 통계학에 대해 잘 모르는 사람들이 많구요. 통계학을 적용하기에 좀 주저하거나 고생 중 인 것 같습니다. 그리고 다른 한편으로는 기본적으로 통계학자들이지만 천문학자는 아니구요, 혹은 그 중간에 서있는 사람도 있죠. 그리고 나는 저의 박사학위를 할 때 한쪽으로 사람들이 치우쳐 있는걸 봤어요. 다른 쪽에는 별로 사람들이 없었죠. 이것은 장애을 일종입니다. 그러니까 통계학에서 기본적으로 오랜동안 지하에서 활동하는 이교도들의 비정통 이었던 거죠. 그런데 이제 중심축이 되었습니다. 저는 이렇게 중심축이 된 것을 아주 즐기고 있어여. 그게 옳다고 생각해요. 하지만 인정하기에 인색한 사람들도 있다는 것도 흥미롭습니다. 베이즈 통계 방식의 연구 분야가 주류가 된 것을 비판하고 있죠.

2018년 7월 6일 금요일

2주 요약: 대량의 관측자료분석, 누군가 같은 고민을 했을 것이다.

[커세라 강좌 소개]자료기반 천문학(Data-Driven Astronomy)
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 / 한글자막
--------------------------------------------------------
Lesson 5: A (much) faster algorithm / 한글자막
--------------------------------------------------------
2주 요약: 대량의 관측자료분석, 누군가 같은 고민을 했을 것이다.
Mudule Summary / 한글자막 / 영문자막

[강의대본]

[00:06] 이번 강좌에서 전파관측 은하 목록과 광학관측 은하목록의 정합을 해봤다. 우리는 손수 정합 프로그램을 작성해 봤다. 목록내 은하 갯수가 증가 하면 어떤 문제가 생기는지도 확인하였다. 파이썬의 astropy 패키지에 구현되어 있는 K-d 트리라고 하는 자료구조를 사용 하므로서 우리가 작성한 프로그램으로는 무려 24일이 걸릴 작업을 단 25초에 끝낼 수 있었다. 그 입력으로 사용한 두 목록에 각각 백만개의 항목들이 수록 되었었다.

[00:31] 이는 문제 해결을 위한 접근시 올바른 자료구조와 현명한 계산 방법을 사용해야 하고 어떤 알고리즘이 자료해석에 있어서 엄청난 차이를 낳게 되는지 보여주는 좋은 예다. 이제까지 확실히, 대부분 과학자들은 결과를 얻는데 집중해 왔었다. 그리고 이면에 숨은 것이 무엇인지 알아보려 하거나 작성한 모든 소프트웨어를 세밀하게 살펴 보는데 시간을 할애하지 않았다. 하지만 우리는 이런 상황에 놓이면 표준 라이브러리와 과학관련 계산 라이브러리의 사용이 얼마나 유용한지 보여 주었길 바란다. 이들 라이브러리는 손수 만든 프로그램보다 훨씬 유용하다.

* 계산 소프트웨어를 만드는 것 자체를 연구 성과로 두는 것은 어리석다. 이미 엄청난 관측 자료가 쌓이고 공유되어 거의 동일한 문제로 고민했던 과학자들이 많다는 것을 기억하자. 현대 널리 퍼져있는 컴퓨터 관련 기술과 공개된 소프트웨어의 수준은 이미 넘쳐나는 엉뚱하고 호기심 많은 과학기술자들로 인해 상상할 수 없을 만큼 높다.

[01:03] 만일 여러분들이 과학과 천문학 컴퓨팅에 관한 알고리즘을 더 배우고자 한다면 시작해볼 방법은 많다. 먼저, 아주 저명한 교과서, 예를 들면 'Numerical Recipies'를 보라. 정렬(Sorting)이나 퓨리에 변환(Fourier Transform)같은 아주 중요한 알고리듬들로 가득하다. 사실, 이번 강좌에서 다뤘던 K-d 트리 알고리즘도 여기에서 차용되었다. 손수 프로그램을 작성해보면 알고리즘의 작동 원리를 배우울 수 있어 항상 흥미롭긴 하다. 비록 쓸만한 프로그램이 만들어지지 못했더라도 말이다.

[01:31] 두번째, 파이썬의 라이브러리 SciPy와 AstroPy에는 훌륭한 예제들로 가득하다. 좌표계 변환 같은 천문-과학 관련 애용을 수록하고 있으니 해당 웹사이트를 방문해 보라.

1. AstroPy, http://www.astropy.org/
2. SciPy, https://www.scipy.org/

[01:38] 끝으로, 흥미로운 논문들이 발간되어 있으니 찾아보기 바란다. 천문 관련 커뮤니티에 고급 컴퓨팅 기법에 관한 논문이 많이 소개되고 있다. 일예로, 상호정합 알고리즘에 관심이 있다면 이에 대한 논문을 강좌 자료실에 소개해 두었으니 참고하기 바란다. 이 논문의 내용에 아주 난해한 수학들을 많이 담고 있으나, 대부분 관련 소프트웨어의 원시 코드들이 공개되어 있으니 이를 읽을 줄 아는 사람들에겐 도움이 될 것이다.

[참고논문]
1. Tamas Budavari, Alexander S. Szalay,
   Probabilistic Cross-Identification of Astronomical Sources,
   https://arxiv.org/abs/0707.1611
2. Line et.al.,
   PUMA: The Positional Update and Matching Algorithm,
   https://arxiv.org/abs/1611.05534,
   PUMA Source, https://github.com/JLBLine/PUMA

[02:02] 소량의 관측자료라면 실행시간에 별로 고민할 것도 없고 손으로 해도 결과를 얻을 수 있다. 심지어 컴퓨터 힘을 빌지 않고도 문제를 해결하고 결론을 낼 수 있다. 하지만 거대규모 자료의 상황이 되면 알고리즘의 선택이나 소프트웨어 패키지의 선택이 아주 중요한 요인이 된다. (기술발전으로 정교하고 방대해진 넘쳐나는 관측자료를 보라!) 누군가 나와 비슷한 관심을 가졌을 것이며 그 전산 문제에 충분한 이해를 가지고 있다는 점을 인식하기 바란다. 그것이 당신의 과학과 분석을 더욱 효과적으로 해결 했을지 모른다. 이런 상세한 것에 메달려야 하는지 그럴 필요없이 이미 준비된 것을 쓰든지 안다면 우주를 이해하는데 훨씬 많은 질문을 던질 수 있을 것이다.

2018년 7월 5일 목요일

2주/5강: 더욱 빠른 알고리즘

[커세라 강좌 소개]자료기반 천문학(Data-Driven Astronomy)
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 / 한글자막
--------------------------------------------------------
5강: 더욱 빠른 알고리즘
Lesson 5: A (much) faster algorithm / 한글자막 / 영문자막

[강의대본]

[00:06] 이번주 강좌를 시작 하면서 전파 대역에서 관측한 은하 목록을 광학 대역으로 관측한 은하의 목록에 맞춰(정합)보았다. 이렇게 맞춰진 두 은하는 실제로 동일한 것이다. 느슨한 교차정합(naive cross-matching) 알고리즘을 컴퓨터 프로그램(파이썬 사용)으로 구현해 봤다. 몇가지 개선을 시도해 봤지만 결과를 얻기까지 매우 느리다는 문제를 발견하게 됐다. 
우리가 만든 교차정합에 어떤 문제가 있는지 알고있다. 이는 나뿐만 아니라 대부분 천문학자들이 항상 부디치는 문제이므로 누군가 이에 대한 고민을 해봤을 것이고 해결책을 찾아 놨을 것이라고 추측할 수 있다. 그리고 확실히 그 해결책이 있다. 파이썬의 astropy 모듈(라이브러리)은 교차정합 함수를 가지고 있는데 엄청나게 쉽게 각거리를 계산하고 두 관측목록의 교차정합을 수행한다.

[00:47] 어떻게 이렇게 빠르게 할 수 있을까? 전에 astropy 모듈을 사용하여 교차정합을 해본적이 있는데 백만개의 항목을 수록한 두 목록의 교차정합에 단 25초밖에 걸리지 않았다. 우와! 우리 프로그램으로는 24일에서 개선 해다고 해봐야 12일이 걸릴일은 단 25초에 해내다니 놀랍다. astropy 에는 이 일을 해내기 위해 어떤 신통한 마법이라도 있는 것일까?

[01:12] 그 해답은 k-d 트리(나무모양의 가지치기 구조)라고 하는 자료구조에 있다. k-d 트리는 k-dimensional tree 의 약자인데 점들을 공간에 재귀적(자기참조, recursive) 구조로 표현한다.

* 컴퓨터를 비롯해 기계가 제일 잘하는 일이 '반복'이다. 정의만 잘 해주면  덧셈뺄셈을 하든, 로그와 삼각함수를 계산하든 반복해야 할 일의 난이도에 불평도 없다! 일을 반복시키는 방법으로 구간 또는 조건을 정해놓은 '단순반복(for-repeat, while-repeat)'과 좀더 지능적인 '재귀적 반복(recursive loop)'이 있다. 함수 내에서 자기 자신을 호출 하는 방식으로 이뤄진다(recursive function call). '단순반복'에 의한 변화량이 선형적 이라면 '재귀적 반복'은 기하급수적인 변화를 뛰어넘는다. 이 강의에서 보게될 트리 탐색, 프랙탈(Fractal)이 대표적인 재귀적 반복의 예다.

[01:23] K는 차원의 수를 나타내는 것으로 우리가 사용했던 공간의 좌표계에서는 적경(RA,right ascension)와 적위(DEC, declination)의 2차원이었다. K-d 트리를 구성하기 위해 공간을 매번 중간값(median)을 기준으로 재귀적으로 분할 한다. 예를 들어보자.

[01:39] 이 기하학적으로는 2차원인 공간을 x-차원(축)의 중심에 가까운 점, 여기에서는 A를 기준으로 양분한다.

* K-d 트리에서 각 분할을 차원이라 한다. 이 분할을 지칭하는 차원은 수리 기하학에서 말하는 물리적 차원이 아닌 개념적의미다. 그리고 아직 몇개로 분할할지 정해지지 않았다.

[01:42] 처음 양분한 기준인 점 A를 트리의 뿌리(root)가 된다. 이어서 A를 기준으로 양분된 평면 중 왼편을 y-축(차원)에서 분할한다. y-축 중앙에서 가장 가까운 점 E를 중심점(median)으로 삼는다. 이렇게 x 와 y 축을 번갈아가며 중심점을 찾고 더이상 왼편으로 분할한 공간에 점이 없을 때까지 분할해 나간다. 왼 평면이 끝나면 이어 오른 평면, 윗 평면이 끝나면 아랫 평면으로 분할을 계속하여 그 이력을 가지친 나무 모양으로 만들어 놓는다.

[02:10] 이제 나무가 완성 되었으므로 이를 활용할 차례다. 빠르게 이웃하는 점을 탐색하는 방법이다.

* 자신의 위치에서 동일한 행동을 반복하는 행위를 재귀적 반복(recursive)이라고 한다.
일반적인 반복(repeat)은 횟수(loop count)가 정해져 있지만 재귀적 반복은 횟수가 정형화 되어 있지 않다. 정형화 되어 있지 않은(분포빈도는 물론 갯수조차 알려져 있지 않음) 실험이나 관측 자료를 검색할 때 재귀적 알고리즘이 유리하다.

[02:16] 점 T에 은하가 있다 하고 이와 가장 가까운 점을 탐색해보자. 먼저 뿌리 마디(node) A와 거리를 계산한다. 탐색을 시작하는 시점에서 점 A는 T와 가장 가까운 셈이다.

[02:26] X-축 상으로 T는 A보다 작으므로 A 에서 왼쪽 가지를 택하여 마디 E에서 탐색을 시작한다. A보다 E가 T에 가깝다는 것은 잠재적으로 가장 근접한 정합 원의 크기를 줄일 수 있다는 것이고 네개의 구획을 건너뛰게 됐다는 것이다.

[02:42] 이제 이 과정을 반복해 보자. 이번에는 점 T와 E의 Y-축 값을 비교해 보자. E보다 T의 Y-축 값이 크다. 윗편 분할, 즉 마디 E의 오른쪽 가지의 B를 택한다. 점 B가 T에 더 가까워 정합 원의 반경을 더 줄일 수 있다.

[02:55] 좌측 위의 영역에 아직 남아있는 두개의 상자를 탐색 해보자. 우측 가지의 마디 D가 앞서 좁혀놓은 정합 원의 범위에 벗어났다. 따라서 D는 제외한다. 이제 더이상 탐색해 볼 가지가 없다. 최적 정합 원에 걸쳐있는 분할이 없다는 뜻이다. 

[03:11] K-트리의 가장 큰 장점은 목표 T와 가장 근접한 점을 찾을 때 노란 색으로 표시된 점들은 아예 비교대상에 넣지도 않았다는 것이다.

[03:18] 자료창고(Database)의 규모가 방대해 질 수록 탐색 시간을 아낄 수 있는 규모는 엄청나다. 우리의 프로그램 속도가 빨라지고 시간 복잡도가 개선된다.

[03:27] 핵심 알고리즘을 변경하여 작업시간을 엄청나게 줄이고 작업규모의 증가에 대한 대응(scalability)도 엄청나게 개선 시킬 수 있다. (위 도표의 검은 실선으로 선형적이며 기울기는 O(log n)보다 작다! 앞서 우리가 작성했던 알고리즘은 증가하는 자료의 량 에 따라 처리시간은 제곱으로 늘어 났었다는 점을 기억하자! 아래 도표에서 O(n^2)에 해당.)

<그림> 트리 탐색 시간 O(log n)

[03:33] 만일 교차정합의 규모가 정말로 크다면 시간 이외에 고려할 사항이 한둘이 아니다. 예를들어 자료를 저장해 놓기 좋은 자료창고도 찾아봐야 한다. 좋은 자료관리 도구를 사용하므로서 매번 목록을 읽을 때마다 중요한 CPU 동작의 상당량을 줄일 수 있다.

[03:49] 또다른 중요한 사항으로 결합 하여 얻는 주변 관련 기술의 활용이다. 혹은 은하가 보여주는 물리적인 특성에 어떤것이 있을지 알아보는 것이다. 이 질문에 답을 하자면 아마도 천문학적 관점으로 접근하는 것 외에 전산 과학적 사고(computational thinking)를 결합하는 것이다.

[04:04] 예를들어 관측한 대상의 적색편이를 측정할 수 있다면 같은 거리에 있는 것들끼리 묶어놓을 수 있다. 그렇게 묶인 은하들은 물리적으로 유사성을 더 많이 가졌을 것이라고 볼 수 있다. 또한 두가지 탐사에서 천체의 공간적 밀도에서 추측해낸 유사성을 정량화 하기위해 통계분석을 해보고 싶을 것이다.


[04:23] 자 이제 우리는 교차정합(cross-matching)을 성공적으로 마쳤다. 이를 통해 우리가 얻은 것은 무엇인가? 거의모든 전파원들은 광학적으로도 관측 가능한 것들이다. 이는 두개의 서로다른 목록을 만들 수 있다는 뜻이다.

[04:37] 전파은하의 대부분은 퀘이사와 관련이 있다. 은하중심의 블랙홀을 찾는 곳에서 강력한 강착원반을 볼 수 있다. 강착원반의 복사는 은하내의 전체 별을 합한 것보다 밝다. 마치 밝은 별처럼 보이기 때문에 이를 별에 준한 천체(quasi-stellar object), 퀘이사(quasar)라고 부른다.


[04:59] 우리가 알고있는 전파은하의 배부분은 일반 은하의 내에 자리한다. 그곳에 별들이 떼지어 구름처럼 몰려있는 것을 볼 수 있다. 이 별들의 구름의 존재는 물질을 빨아들이는 초거대 블랙홀의 활동이 중지했다는 의미다. 그리고 그 잔여활동으로 전파 분출이 있다. 대부분 광학적으로 전파원을 확인해 왔으므로 그들의 적색편이 또한 확인할 수 있었다. 이 적색편이는 각 은하와 퀘이사의 거리를 알려준다.


[05:23] 은하의 적색편이가 0.02에서 0.5의 범위에 있는 반면 퀘이사의 적색편이는 0.2에서 3에 이른다. 이로서 대부분 은하들이 상대적으로 가깝게 위치하는 우주라는 사실을 알려준다. 반면 퀘이사는 대개 훨씬 더 멀리 있다. 광학 목록과 전파 목록을 정합해 보면서 초거대 블랙홀을 보유할 수 있는 은하가 따로 있다는 것을 알게됐고 그 은하까지 거리를 측정 할 수 있게 되었다. 이는 다른 파장대의 관측으로 얻는 정보를 취합하여 얻은 과학연구의 성과의 예다.

[05:54] 현대 천문학이 다파장 관측으로 접근하는 이유를 보여준다.

* 현대 천문학에 기여한 과학기술로 컴퓨터기술,고감도 반도체 센서,다파장 관측,우주탐사을 들 수있다.

[관련 강좌] AstroTech, https://www.coursera.org/learn/astronomy-technology


2018년 7월 4일 수요일

2주/4강: 실행 시간 복잡도 평가

[커세라 강좌 소개]자료기반 천문학(Data-Driven Astronomy)
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]

[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)로 평가한다.

<그림> 반복과 소요시간

[참조] Analysis of Algorithm, https://www.coursera.org/learn/analysis-of-algorithms
------------------------------------------------------------

[00:51] 어떤 알고리즘의 복잡성이 선형적으로 증가하거나 입력에 대해 상수라면 잘 만들어진 알고리즘이라고 한다. 아래 도표에서 녹색의 영역에 놓인 알고리즘을 말한다. 한편 개선이 필요한 알고리즘이라 하면 복잡성의 정도(Order)가 n의 제곱 이거나 그보다 높은 경우인데 현재 우리 프로그램이 이에 해당한다.
* 가로축은 알고리즘의 수행시 소요되는 입력의 갯수(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: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] 어쩌면 위에서 우리가 해봤던 것처럼 여러분 스스로 구현해 보면서 실용적인 개선점을 찾을 수도 있다. 컴퓨터 과학자도 미처 생각치 못한 특이한 방법이 있을 지도 모른다. 지금까지 우리가 살펴봤던 것은 시간 복잡성을 따지는 공식에서 상수 인자를 줄이는 방법에 관한 것이었다. 이에 대해 실습과정에서 자세히 다뤄 보기로 하자. 우리 프로그램을 상당히 개선하긴 했지만 여전히 만족 스럽지 못할 만큼 느리다. 다음 강의에서 또다른 접근 방법은 없는지 찾아 보기로 하자.

----------------------------------

2018년 7월 2일 월요일

2주/3강: 교차정합(cross-matching) 알고리즘에 대하여

[커세라 강좌 소개]자료기반 천문학(Data-Driven Astronomy)
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 ? / 한글자막 / 영문자막

[강의대본] 교차정합(Cross-Matching)이 뭔지 알아나보자


[00:06] 천체 탐사(survey*)영상에서 그안에 담긴 천체 목록을 만들려고 할 때 먼저 대상찾기** 소프트웨어를 사용하여 찍힌 목록을 만든다. 이 일을 수행하는 소프트웨어가 다양하게 있지만 그 한가지로 sExtracter***가 널리 이용된다.

  * 탐사(survey) 와 관측(observation)의 차이에 대하여 생각해 보자.
 ** 인식 전처리용 영상처리 소프트웨어
*** https://www.astromatic.net/software/sextractor

[00:17] 대부분 소프트웨어가 작동하는 방식은 대동소이하다. 기본적으로 영상에서 화소점을 훑어가며 통계적으로 화소점 값이 극대가 되는 점을 찾는다. 그런 후 주변의 화소점과 묶은 후 망원경의 반응(특성) 함수에 맞춰 보는데 이를 '빛내기(beam)' 또는 '점 확산 함수(point spread function)'라고 한다.



[00:35] 그 결과 각 천체 마다 위치(position),각크기(angular size)와 밝기(intensity)측정치가 포함된 목록을 얻는다. 측정치는 불확정(uncertainties)* 적인데 관측영상의 잡음, 망원경의 보정, 망원경의 반응 함수를 얼마나 잘 특성화** 하느냐에 따라 달렸다.

* 관측 측정치의 불확정성: 워낙 멀리 떨어진 대상을 찍은 천체 영상은 외적 영향을 많이 받는다. 동일한 대상이라도 사진을 찍을 때마다 다르다. 따라서 통계적 분석과 표준함수로의 근사기법이 매우 중요한 역활을 한다.
** 목적에 따라 서로 다른 파장대의 반응 특성을 갖는 망원경의 사진을 교차비교 하는 경우

<왼쪽은 전파 망원경, 오른쪽은 광학 망원경 탐색 영상: 분해능, 감응 파장대 같은 특성이 완전히 다른 두 망원경으로 획득한 영상이다. 과연 같은 대상인가? 오른편에 찍힌 영상의 천체 목록과 왼편에 찍힌 영상에서 목록을 비교하는 것이 바로 교차정합이다.>

[00:53] 관측 목록을 얻고나면 교차 탐색을 실시하는데 첫번째 목록(Catalog_1)에서 각 대상에 상응하는 대상을 찾기위한 두번째 목록(Catalog_1)을 준비한다. 이를 위해 대개 주어진 범위 내에서 탐색을 하는데 위치의 부정확성을 고려한다. 말은 쉽다.


[01:08] 교차정합 프로그램을 실제로 구현하기 전에 옆으로 약간 비켜서서 하늘에서 거리계산 방법에 대한 논의를 해보도록 하자. 왜냐하면 거리야 말로 가장 먼저 해결해야 할 문제이기 때문이다. 이번 강좌는 하늘에 투영된 각거리를 계산할 것이다. 이는 공간 상에서 두 물체 사이의 물리적 거리를 의미하는 것이 아니다. 이 영상에서 왼쪽에 있는 은하는 천 오백만 광년 떨어져 있다고 하자. 그리고 오른쪽에 위치한 은하는 1억 광년 떨어져 있다고 하자. 그 두 은하가 구면에 투영되면 마치 가까운 것 처럼 보이지만 실제로는 이웃하고 있다고 하기에는 너무 멀다.

[01:41] 거리야 말로 천문학에 있어서 가장 난제다. 만일 두점이 주어지고 그 둘사이의 거리를 계산하라고 한다면 아마도 이렇게 할 것이다. 그러니까 유클리디언(직교좌표계) 거리계산을 떠올릴 것이다. 이는 고교 수학에서 피타고라스 정리로 잘 알고 있다.


[01:56] 하지만 여기에 문제가 있는데 피타고라스 정리는 평면을 가정하는데 우리는 하늘에서 거리를 계산하고자 한다. (하늘은 구면이다. 직교좌표계에서 구면 좌표계로 생각 체계를 바꾸자.) 예를 들어 시드니에서 런던까지 비행하는 가장 짧은 거리를 계산 하고자 한다면 하늘에 대원을 긋는 거리를 사용해야 한다. 이에 대해 다음 과제활동에서 다뤄볼 것이다.


[참조] 넘겨짚어보는 가우스 함수와 적분(feat.부분적분법, 중적분, 야코비언)

[02:14] 기본지식을 얻었으니 이제 교차정합 알고리즘을 구현해볼 준비가 됐다. 앞서 논의한 대로 이 알고리즘은 다음과 같다.


[02:19] 첫번째 목록(Catalogue_1)에서 광원A(Source_A)에 대해 상응하는 광원B(Source_B)를 두번째 목록(Catalogue_2)에서 찾아낸다. 두 상응하는 짝의 각거리, angular_distance(A,B),를 계산했더니, 만일 각거리가 미리 정해놓은 탐색범위(radius) 내에 있고 광원A의 위치 이격(offset)이 가장 작았다면 두 대상이 일치한다고 간주 할 수 있다. 두가지 목록에 대하여 개발한 프로그램을 작동 시키면 첫번째 목록에 나와있는 은하들과 두번째 목록에 나와있는 은하들 사이에 가장 일치하는 것들과 대원 이격이 가장 짧은 것(best_match)을 추려낸다.

[02:47] 이 프로그램이 내 컴퓨터에서 실행되는 시간을 재봤다. 각각 100개의 탐색 대상이 있는 두 목록을 처리 하는데 약 50밀리초가 걸렸다. 이정도면 아주 괜찮아 보인다. 우리의 교차정합 알고리즘이 잘 작동하는 것 같다. 우리가 원하는 결과를 얻었다.

[02:59] 무슨 문제가 있을까?

[03:01] 이곳이 바로 대부분 학생들이 자신의 결과에 만족해 하는 지점이다. 이제 그들의 프로그램을 방대한 목록을 상대로 돌려 보기로 한다. 그리고 아마 다음 회의 때 이렇게 질문 할 것이 뻔하다.

[03:12] 인터넷이 끊어져도, 제 노트북이 꺼져도 제 프로그램을 계속 실행시킬 수는 없을까요? (학생들은 단말기를 통해 방대한 관측 자료들이 저장된 서버에 접근하고 있다.)

[00:03:16] 그러면 나는 물론 가능하다고 답해줄 수 있지만 학생들은 왜 시간을 더 요구하게 됐을까?

[03:20] 맞다. 학생들이 만든 교차정합 프로그램이 밤새 실행 되고도 아직도 마치지 못했기 때문이다. 더 긴 시간을 주기로 했다.

[03:26] 왜 이런 일이 발생 했을까? 왜 그처럼 작은 교차정합 프로그램이 실행 되는데 몇일 씩이나 걸리는 걸까?

[03:32] 이 문제가 무엇인지 파헤쳐보기 위해 몇가지 시험을 해보자. 난수의 배열을 생성해 놓고 각 배열에 담긴 값의 갯수를 매번 증가시키면서 교차정합을 실시해 보면, 아마 다음과 같은 도표를 얻게 된다. X-축은 목록에 담긴 각 지점의 갯수를 나타내며, Y-축은 프로그램이 실행되면서 걸린 시간을 미리초 단위로 나타내었다.

[03:50] 100개의 은하가 담긴 목록에 대해 내 프로그램은 약 50 미리초가 걸렸다. 1천개의 은하의 경우 약 5천 미리초가 걸렸다. 1만개의 은하에 대해서 약 50만 밀리초가 걸렸다. 더 많은 갯수로 시험을 해볼 수 있지만 실행되길 기다리기가 너무나 지루해서 그만 두었다. 프로그램이 실행되는 시간이 증가하는 경향을 알아보기에 충분했으므로 상관없다. 각 목록에 담긴 은하의 갯수를 열배 씩 증가시키면 실행에 걸리는 시간은 백배 씩 증가한다.

[04:20] 다음 강의에서 실행시간이 오래 걸리는 알고리즘을 어떻게 다룰지 살펴보고 우리의 교차정합 알고리즘을 개선할 방도를 찾아보기로 하자.

--------------------------------------------
[파이썬 실습]