Haskell Lazy Evaluation에서 실마리를 얻어 Erlang 코드를 좋게 하다.

3n + 1 문제를 병렬로 풀기 위해서 문제를 N개의 부분 문제로 나눌 필요가 있었습니다. 리스트 L을 NumberOfChunks개로 최대한 공평하게 나누는 방법을 알려주는 함수를 다음과 같이 만들었죠.

plan_split(NumberOfChunks, L) ->
    F = fun({Nth, X}) ->
		if Nth > (length(L) rem NumberOfChunks) ->
			X;
		   true ->
			X + 1
		end
	end,
    for(F, lists:duplicate(NumberOfChunks, length(L) div NumberOfChunks)).

plan_split_test_() ->
    [?_assertMatch([1, 1], plan_split(2, [1,2])),
     ?_assertMatch([2, 1], plan_split(2, [1,2,3])),
     ?_assertMatch([1, 0, 0], plan_split(3, [1]))].

if가 영 마음에 걸립니다. if 때문에 함수 길이도 무척 길어졌고 임시 함수까지 하나 만들었고 마음에 안듭니다. 하지만 별 좋은 방법이 떠오르지 않더군요.

오늘 제본한 하스켈 튜토리얼을 찾아와서 퇴근하기 전에 이리 저리 뒤지다가 Lazy Evaluation이라는 것을 발견했습니다. 음... 그럴싸한다.

Prelude> let ones = 1:ones
Prelude> let zeros = 0:zeros
Prelude> take 10 (take 3 ones ++ zeros)      
[1,1,1,0,0,0,0,0,0,0]

[무한개의 몫] + [1이 처음 나머지 개 있고 무한개의 0]해서 처음 NumberOfChunks개를 떼어내면 찜찜해 하던 문제를 한방에 해결할 수 있게더군요. 그래서 하스켈로 다음과 같이 작성하려고 했습니다.

distributeFairly nelements nchunk = map plus (take nchunk (zip ((take r ones) ++ zeros) (repeat d)))
    where
      r = (rem nelements nchunk)
      d = (div nelements nchunk)
      zeros = repeat 0
      ones = repeat 1
      plus (a, b) = a + b

하지만 퇴근 버스에서 계속 생각을 하다가 굳이 LazyEvaluation없이도 문제가 간단하게 풀린다는 것을 알아버렸습니다.

distributeFairly nelements nchunk = luckyOnes ++ unluckyOnes
    where
      atLeast = (div nelements nchunk)
      remainder = (rem nelements nchunk)
      luckyOnes = (replicate remainder (atLeast + 1))
      unluckyOnes = (replicate (nchunk - remainder) atLeast)

하스켈 코드를 참고해서 얼랭 코드도 아름답게 고쳤습니다.

distribute_fairly(Whole, NumberOfChunks) ->
    D = Whole div NumberOfChunks,
    R = Whole rem NumberOfChunks,
    lists:duplicate(R, D + 1) ++ lists:duplicate(NumberOfChunks - R, D).

distribute_fairly_test_() ->
    [?_assertMatch([1, 1], distribute_fairly(2, 2)),
     ?_assertMatch([2, 1], distribute_fairly(3, 2)),
     ?_assertMatch([1, 0, 0], distribute_fairly(1, 3))].

덧글

[최우철]

안녕하세요? 이제막 얼랭을 시작한 개발자입니다. 제본하셨다고 하셨는데 제본집 추천좀 부탁드립니다...

[羅]

여러분으로 입력에 대한 감사의