cyclic list - ugly numbers (leetcode #264)

리트코드 문제를 풀다보면 cyclic list 문제를 더러 만난다. 이 문제도 마찬가지.
먼저 문제를 보자.

2,3,5만을 소인수(prime factor)로 가지는 수를 ugly number라고 했을때 n번째 ugly number를 구하라!

prime number 수열을 계산하는 에라토스테네스의 체(sieve)와 비슷한 문제다. 이미 계산된 ugly number에 다시 2를 곱하고, 3을 곱하고, 5를 곱해서 뒤에 나오는 ugly number가 구해진다.

맨 앞에 1이 있고, 여기에 2,3,5를 각각 곱하여 2,3,5가 구해진다.

1 -> 2,3,5

그 다음 ugly number는 2가되고, 2에 다시 2,3,5를 곱하면 4,6,10이 되는데, 이미 구했던 3이 더 작으니 3이 그 다음 ugly number가 된다.

1,2 -> 3,5   4,6,10

1,2,3 -> 5  4,6,10   6,9,15

1,2,3,4 -> 5   6,10    6,9,15    8,12,20

1,2,3,4,5 -> 6,10   6,9,15   8,12,20   10,15,25


이렇게 ugly number가 하나씩 결정될 때마다 그 뒤에 이어질 ugly number들을 계산할 수 있다.

이런 문제는 Haskell의 cyclic list로 풀면 딱이다.

ugly = 1 : merge (map (2*) ugly)  (map (3*) ugly)  (map (5*) ugly)

여기서 merge는 각 리스트에서 최소값을 꺼내고, 그 값을 뺀 나머지에 대해 같은 과정을 반복한다.

merge as bs cs =
   let next = minimum (map head [as,bs,cs])
   in next : merge (skip next as) (skip next bs) (skip next cs)

skip x (a:as) = if x == a then as else (a:as)

-- UPDATE

하스켈 같은 취미 언어는 금새 까먹는다.  2년 전에 이미 풀어본 거다. 그런데 이전에 푼 게 더 낫네. ㅠ.ㅠ

Go - io.Pipe()

Go 인터페이스 중 가장 흔히 쓰이는 것이 io.Reader/Writer 일 거다.

그런데 여기에 Go의 강점인 goroutine 이 결합되어서 빛을 발하게 되는 것이 io.Pipe() 아닐까 싶다.

r,w := io.Pipe()

호출하면 Reader/Writer 를 얻어내는데, 이 둘은 파이프로 연결된 양쪽 끝이다. w(Writer)로 쓰는 내용을 r(Reader)에서 읽을 수 있다.

Reader가 필요한 코드와 Writer가 필요한 코드를 연결시킬 때 쓰면 좋다.

예를 들어 multipart/form-data 로 파일을 POST 한다고 보자.

요청 객체는 아래처럼 Reader를 요구한다.

http.NewRequest("POST", url, bodyReader)

보낼 파일은 os.Open(path) 로 열어서 얻을 수 있는데, *File 은 Reader 인터페이스를 만족한다.

그렇다고 NewRequest(... file) 처럼 바로 전달할 수 없는 것이, "multipart/form-data" 형식을 맞춰줘야 하기 때문이다. 그리고 이 형식 맞추기를 도와주는 것이 multipart.Writer 타입이다.

multipart.NewWriter(w) 로 만들 수 있으며, 다른 io.Writer w를 래핑하여 "multipart/form-data" 형식으로 데이터를 쓸 수 있게 해준다.

앞서 얘기한 것처럼, 우리가 필요한 것은 (body)Reader인데 multipart.Writer는 다른 Writer를 필요로 한다. io.Pipe()를 쓰기 딱 좋은 순간이다.

그런데,

구글에 "golang request multipart file" 로 검색해보면 몇가지 예제들을 볼 수 있다.

대부분은 bytes.Buffer 를 만들고 이를 multipart.Writer 로 래핑한다. bytes.Buffer는 Writer 인터페이스를 통해 데이터를 기록할 수도 있지만 동시에 Reader이기도 해서 Reader와 Writer가 필요한 이 상황에 쓰일 수 있다. 우선 Writer 인터페이스를 이용하여 버퍼를 채우고, Reader 인터페이스로 다시 읽으면 된다.

var buf bytes.Buffer
w := multipart.NewWriter(&buf)
~~~
req := http.NewRequest(...,&buf)

이 방법은 단점이 있다. 바로 보내려는 데이터 크기만큼 bytes.Buffer에 쌓아야 해서 메모리 부담이 커진다는 것이다.

io.Pipe()를 사용하면 어떨까? io.Pipe()로 생성되는 io.Reader와 io.Writer를 bytes.Buffer 처럼 사용하면 된다.

pr, pw := io.Pipe()
w := multipart.NewWriter(pw)
req := http.NewRequest(...,pr)

앞에서 bytes.Buffer의 경우는 Reader를 사용하기 전에 Writer로 내용을 채워야 했다.
그런데 io.Pipe()는 Consumer/Producer 처럼 동기화되어 동작하기 때문에 미리 채우고 나중에 읽고, 이런식으로 동작할 수 없다.

goroutine이 필요한 순간이다. Reader 를 사용하는 코드와 Writer 를 사용하는 코드는 서로 다른 고루틴에서 실행되어야 한다. io.Pipe()는 사실 채널 몇개를 만들어 줄 뿐이다. 각 Reader/Writer는 이 채널에 데이터를 쓰고, 채널에서 데이터를 읽는 것이다.

pr, pw := io.Pipe()
w := multipart.NewWriter(pw)
go ~~~
req := http.NewRequest(...,pr)

이제, 파일이 크다고 하더라도 조금씩 읽어서 (Read) 읽은 만큼 쓰기 (Write) 를 반복하면 메모리 부담 없이 전송할 수 있다.

io.Pipe() 가 Writer ---> Reader 를 연결하는 채널을 만들어 주는 것이라면 반대로 Reader ---> Writer 의 연결은 io.Copy(w,r) 가 처리한다.