Nice to meet you everyone.
I’m an engineer of Korea, working on image object recognition.
Any help (especially about my English translation) would be welcomed.
pilhoon-at-gmail-dot-com

2014년 7월 14일 월요일

spiral matrix

spiral matrix란 다음과 같은 행렬이다.

 0  1  2  3  4
15 16 17 18  5
14 23 24 19  6
13 22 21 20  7
12 11 10  9  8

  1. 가로 세로 길이의 제한은 없다. 같을 필요가 없다.
  2. 0이 왼쪽 위가 아니라 네 귀 어디나 올 수 있다.
  3. 회전방향도 시계/반시계 모두 가능하다.
  4. 시작점(가장 작은 숫자)이 바깥(involute)이 아니라 중심이어도 된다. 이러면 중심에서 밖으로 그린다(evolute)
  • 가장 작은 숫자가 왼쪽 위 귀에 오는 것을 기본형이라고 한다면, 0이 다른 귀에 오는 형태도 기본형에서 쉽게 변형 가능하다. 그냥 회전.
  • evolute도 involute로부터 쉽게 얻는다. 위의 \(5 \times 5\)의 경우, 24에서 각 셀의 값을 뺀것으로 셀을 채우면 된다. new = max - old
  • 1로 시작하는것도 기본형으로부터 쉽게 얻는다. 그냥 모든 셀에 대해 +1 
  • 방향을 바꾸는 것도 기본형으로부터 가능하다. 예를들어 \(5 \times 6\) 반시계를 얻고 싶으면 \(6 \times5\) 기본형(=시계방향)을 가지고 xy대칭시키면 된다.
결국 문제는 임의의 사이즈의 기본형을 어떻게 얻느냐이다.

가장 쉬운 구현은 직관적으로 그대로 구현하는 것이다. (이하의 모든 소스는 내 github에서 다운받을 수 있다.) http://rosettacode.org/wiki/Spiral_matrix에 다양한 언어들의 해법이 있는데 대부분 이런식으로 구현한 것이다.

두번째 해법은 Joey Tuttle이라는 사람의 아이디어를 이용한 해법이다. 위 페이지의 여러 구현중 J의 구현을 보면 http://www.jsoftware.com/papers/play132.htm 페이지로 링크가 있고 거기 설명이 잘 되어있다. 해당 페이지의 설명대로 구해도 되고, 정확히 같은 원리지만 좀 더 직관적이고 구현이 쉬운 방법은 다음과 같다. 일단 \(3\times 4\)를 예로 들면, 진행방향이 오른쪽이면 +1, 아랫줄이면 +4, 왼쪽이면 -1, 위쪽이면 -4이다. column width(=stride size)가 4이기 때문이다.

0  1  2  3
4  5  6  7
8  9 10 11

규칙없이 0부터 차례대로 적은 것이다. 이 행렬을 그려야 하는 순서대로 짚어나가면서 숫자를 적으면

0, 1, 2, 3, 7, 11, 10, 9, 8, 4, 5, 6 이 된다.

계차수열을 구하면,

1, 1, 1, 4, 4, -1, -1, -1, -4, 1, 1

이것이 규칙이다.
같은 사이즈의 행렬에 우리가 따라가야 하는 경로대로 위 숫자들을 넣으면 더 잘 보인다.

 * →  1 →  1 → 1
               ↓
-4 →  1 →  1   4
 ↑             ↓
-1 ← -1 ← -1 ← 4

square matrix의 경우를 고려하면 규칙이 더 쉽게 보인다. 
예를들어 \(3\times 3\)이라면 1, 1, 3, 3, -1, -1, -3, 1 일 것이다. 이것을 거꾸로 하면 1, -3, -1, -1, 3, 3, 1, 1
부호는 교차되면서 1과 stride size가 교대된다. 가로가 길거나 세로가 더 긴경우도 쉽게 알 수 있다.

보면 알겠지만 evolute가 더 구현하기는 쉽다. 그걸 뒤집으면 involute가 되고. 여튼 involute를 바로 구하는 것도 그리 어려운 일은 아니어서 구현된 코드도 그렇게 만들어졌다.

이제 1과 stride, 부호를 적당히 섞은 수열만 가지면 0, 1, 2, 3, 7, 11, 10, 9, 8, 4, 5, 6 을 그냥 얻을 수 있다. 실제로 네모에 그려보지 않고서.

이제부터가 핵심인데 이 수열을 inverse permutation한다.

그러면 0, 1, 2, 3, 9, 10, 11, 4, 8, 7, 6, 5

넷씩 끊어 적으면,

0  1  2  3
9 10 11  4
8  7  6  5

답을 얻는다.

inverse permutation이란게 position정보를 겉으로 드러내는 것이라 어찌보면 당연한 과정인데, 또 다시 생각해보면 그리 녹록한 직관력은 아니다. 凡夫는 그저 감탄할 뿐. 구현도 매우 쉽다. 다만, 구현을 해보면 중간 단계를 거쳐야 하기 때문에 메모리 소모가 많다. 최소 두배의 메모리가 필요하다. 구현된 코드는 최적화처리가 전혀 되어있지 않아서 세배 가까운 메모리가 필요하다. 내 랩탑은 메모리가 16G인데 \(30000 \times 30000\) 도 겨우 소화할 수 있었다.

마지막 방법은 일반항을 구해서 row, column값으로 바로바로 해당 cell의 값을 얻는 방법이다. 이 방법은 주변값을 이용하지 않는다. 다시말해, 어떤 위치에 있든 \( O(1) \)이다. 이렇게만 써놓으면 가장 속도가 빨라야 할것 같지만 (상수값 로드가 커서 = \( kO(n) \)이라 하면 \( k \)가 커서) 워낙 계산량이 좀 있기도 하고, 각 cell이 \( O(1) \)이니까 총 계산은 \( O(n) \)인데, 위 Joey의 방법도 \( O(n) \)이라 어떻게 구현하고 어떤 architecture를 쓰는지가 중요해진다.(심지어 첫번째 방법도 \( O(n) \)이다. 첫번째, 두번째 방법 모두 array의 각 cell에 접근하는 실제적인 문제때문에 \( O(n \log n) \)일것 같은데 이것도 확인해보지는 않았다) 하지만 정말 강력한 두가지 장점이 다른 모든 방법을 압도하는데, 일단 메모리를 쓰지 않는다. 다른 셀의 도움을 받지 않으므로 메모리에 뭔가를 저장해둘 필요가 없다. 그리고 다른 셀에 의존하지 않는다는 점은 더더욱 강력한 무기를 사용가능하게 만든다. 병렬화. 자원이 충분하다면 다른 방법들은 비교조차 안될 것이다. 일반항을 얻는 과정은 크게 어렵지 않으니 코드를 참고하면 된다. 기본 아이디어는, 밖에서부터 몇겹을 벗겨 나가야 해당 셀이 나오는지와, 해당 셀이 가장 바깥에 있을 때 몇번째로 그려지는가를 계산해 내는 것이다. 정확히 몇번째 셀인지만 알면 된다. 어차피 order자체가 그 cell의 값이니까.

speed test결과는 신뢰할수가 없는게, 리눅스박스에서 했을 때와 랩탑(OSX, xcode)에서 했을 때 결과가 많이 달랐다. g++버전도 서로 달랐다. 일단 랩탑에서 xcode profiler로 돌려보니 Joey가 가장 빨랐고 그보다 두배 약간 못되는 시간에 마지막 방법(일반항 구하는방법)도 solution을 냈다. 사람이 그리듯 일일이 그려보는 첫번째 방법은 Joey의 열배정도 느렸다. 리눅스에서는 일반항으로 구하는 방법이 압도적으로 빨랐는데 최적화옵션(-O4)이 알아서 병렬화한것 아닌가 의심이 가지만 확인해보지는 않았다.

메모리 allocation문제로 Joey가 그릴 수 있는 사이즈가 제일 작았고 가장 쉬운 첫번째 방법으로는 16기가 메모리로 대략 25억개 셀까지 가능했다. 이 경우에도 1분 미만이 소요되었다. 일반항 방법으로는 bignum을 썼다면 무한까지도 했을 것이다.

3차원의 경우도 비슷할 것으로 예상한다. 우리가 실패(reel)를 감는 방법을 응용해서 3차원에서도 spiral을 정의할 수 있다.

댓글 없음:

댓글 쓰기