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) 가 처리한다.

Go - sort / reverse

Go는 generics 혹은 parametric polymorphism 을 지원하지 않아서 generic collection 같은 걸 만들기가 어렵다.

container/list 패키지를 보면 아래처럼 interface{} 타입을 써서 어떤 값이든 담을 수 있게 했다.

sort 패키지를 보면 1) 크기 비교 가능하고, 2) 랜덤 액세스를 통해 swap 연산이 되며, 3) 전체 길이가 알려진 경우를 인터페이스로 정의하여 정렬 알고리즘을 일반화하였다.

이 경우는 interface{} 타입을 사용하는대신 '인덱스'만으로 알고리즘을 전개할 수 있게 했다.

대개 다른 언어들이 '비교 가능한 요소'들을 대상으로 비교 함수가 만들어지는데, 인덱스를 사용한 것이 특이하다. 비교 함수를 뒤집어서 역순 정렬을 하려면?

Reverse 함수로 interface 값을 한번더 래핑하면 된다.

Reverse 함수의 반환값을 보면 &reverse{data} 인데, 여기서 data 도 sort.Interface 타입이고함수의 반환타입 역시 sort.Interface다. (즉, sort.reverse 구조체는 decorator 나 wrapper 같은 역할을 한다.)

여기서 특이한 점은, 1) Reverse 함수가 왜 포인터를 반환하느냐? 2) Less 메쏘드의 리시버 타입은 왜 밸류 타입인가?

사실 Reverse 함수를 밸류로 반환해도, 이미 reverse 구조체가 sort.Interface 인터페이스를 구현하기 때문에 (임베드하면서 Less만 오버라이드) 정렬 기능에는 문제가 없다. 혹은, 포인터를 반환하여 (sort.Interface로) 래핑하기 때문에 Less 함수의 리시버가 *reverse 타입이어도 문제없다.

왜 이것도 되고, 저것도 되는데 위의 모양을 가지게 되었을까?

추측컨데,

1) Reverse 함수의 반환 값이 인터페이스이므로 포인터를 반환함으로써 어떠한 리시버도 가능할 뿐 아니라 인터페이스 값을 만드는 비용이 저렴하다.

2) Less 메쏘드는 리시버 (reverse 구조체) 내부를 건드리지 않는다. 즉, 포인터를 사용할 이유가 없는 것이다. (만일 메쏘드 리시버가 밸류로 선언되어 호출 시 리시버 값이 복사되는 것이 부담된다면 포인터 타입으로 리시버를 사용할 수 있겠지만 reverse 구조체는 sort.Interface 인터페이스만 임베드하고 있어서 two-word 크기를 가진다. 복사 비용이 부담되지 않으므로 일부러 포인터 타입의 리시버로 정의할 필요가 없다.

Go - random initialization vector

crypto/cipher 패키지의 NewCBCEncrypter 예제를 보자.

encryption을 하려면 아래처럼 Block 과 iv 를 이용하여 BlockMode encrypter를 만들고, 여기에 CryptBlocks(dst,src []byte) 메쏘드를 불러야 한다.

mode := cipher.NewCBCEncrypter(block, iv)
mode.CryptBlocks(ciphertext[aes.BlockSize:], plaintext)

여기서 iv 는 secure 할 필요는 없지만 무작위여야 하는데...

아래처럼 간단히 처리할 수 있다.

io.ReadFull(rand.Reader, iv)

혹은 더 간단히,

rand.Read(iv)