MapReduce

Mapreduce라고 개념을 듣긴 했는데 도대체 머하는 놈인지 개념이 잡히질 않았다.

언듯 느끼기로는 분할정복으로 대용량의 파일을 처리하기 위한 개념정도였는데

 

예제로 돌아다니는 놈이 내가 사용하는 서버에서는 돌아가질 않아 이번기회에 하나씩 뜯어 보기로 했다.

 

그리 긴 코드가 아니라서 오랜 시간이 걸리지 않을것 같다..

 

아래 보이는 것이 전체 코드이다. 복사해서 실행시키면 될것 같은데 잘 안된다..

 

Example Code :

input = ((1,'boy'),(2,'dog'),(3,'cat'),(4,'snake'), (5,'cat'))
// 입력 데이터가 ((1,'boy'),(2,'dog'),(3,'cat'),(4,'snake'), (5,'cat')) 와 같을때..

def doMap(gen): return ( (v,k) for k,v in gen if v.find('a')!=-1 ) //a를 포함한것만 뽑아서 k,v 를 reverse
// 결과 : (('cat', 3), ('snake', 4), ('cat', 5))

def group(gen):              //레코드값을 그룹화 하여 (('snake', [4]), ('cat', [3, 5])) 반환  
    sl = sorted(list(gen))  
    if not sl: return           
    rkey, rlist = sl[0][0], [sl[0][1]]
    for k,v in sl[1:]:      
      if k==rkey:
         rlist.append(v)
      else:
         yield (rkey, rlist)
         rkey, rlist = k, [v]
    yield(rkey, rlist)       

def doReduce(gen): return ((k, len(v)) for k,v in gen) // length 값으로 치환 출력

print tuple(doReduce(group(doMap(input))))   // (('snake', 1), ('cat', 2)) 과 같은 리스트를 출력

 

 

결국 함수 하나하나씩을 분리해서 테스트를 진행한다.

 

우선 Map()

 

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

#!/usr/bin/python

input=((1,'boy'),(2,'dog'),(3,'cat'),(4,'aardvark'), (5,'cat'))
def doMap(gen) : return [ (y,x) for x,y in gen if y.find('a') != -1]

print tuple(doMap(input))
------------------------------------------------------------------

원 소스에는 doMap의 리턴값이 tuple로 되어 있는데 그렇게 하면 에러가 발생하여, 불가피하게 리스트로 리턴하고 다시 tuple로 형변화을 했더니 동작이 정상적으로 되었다.

코드는 파이선을 아시는 분들은 금방 보면 아시겠지만 잠깐 설명을 붙이면

입력으로 워드 포지선을 가지는 (포지선, 워드)형태의 튜플리스트를 입력으로 받고

워드에 'a'가 포함된 것만 뽑아 리턴한다.

따라서 이파일을 실행하면 결과는 (('cat', 3), ('aardvark', 4), ('cat', 5)) 식으로 만들어진다.

 

 

이번에는 doReduce()

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

input = ((3, 'cat'),(4, 'aardvark'), (5, 'cat'))

def doReduce(gen):  return [(k,len(v))  for k,v in gen]

 

print tuple(doReduce(input))
------------------------------------------------------------------

이 함수는 더 간단하다. 입력으로 (포지선,워드)형태의 튜플을 입력받아서

(워드,워드의길이)로 리턴을 한다 다음 코드를 실행하면

((3, 3), (4, 8), (5, 3)) 가 리턴이 된다.

 

마지막으로 doGroup()

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

#!/usr/bin/python

input=(('cat', 3), ('aardvark', 4), ('cat', 5))
def doGroup(gen):             # accept a list of key,value pairs
    sl = list(gen)  # sort
    sl.sort()
    if not sl: return         # might be empty
    rkey, rlist = sl[0][0], [sl[0][1]] # a key and list to return
    for k,v in sl[1:]:        # process rest of sorted list
        if k==rkey:
            rlist.append(v) # extend the list for this key
            print rlist
        else:
            yield (rkey, rlist) # output key & list
            rkey, rlist = k, [v]# start next key & list
            print rkey
            print rlist
    yield(rkey, rlist)          # output last key & list

print doGroup(input)
------------------------------------------------------------------

이 함수의 코드는 앞에 본것보다 약간 긴데 내용은 별로 어렵지 않다.

 

우선 입력으로 들어온 튜플을 리스트로 변환한다

변환된 리스트의 내부 함수인 sort로 정렬한다.

정렬된 값을 보면

sl[0] = ('aardvark', 4)
sl[1] = ('cat', 3)
sl[1] = ('cat', 5)

그리고

rkey에 sl[0][0] 값을 대입한다.

rkey에는 addrdvark가 들어간다.

rlist에는 [sl[0][1]]을 입력한다

rlist에는 [4]가 들어간다

 

 

이제부터 리스트 수만큼 for문을 실행한다

 

 

for문의 k,v는 다음과 같은 값을 가진다

첫번째 loop cat 3

두번째 loop cat 5

 

첫번째 cat 3에 cat을 rkey(addrdvark)와 같은지 비교한다.

같다면 rlist에 v(3)을 추가하고

아니면  현재의 rkey, rlist를 저장하고 rkey,rlist에 k, [v]를 대입한다

이 함수의 실행결과는 와 같은 오브젝트를 리턴한다. 그 이유는 yield를 사용했기 때문인데 이함수에 대한 설명을 생략한다.

 

위에 설명한 세가지 함수가 하나로 실행되면

입력값이 input=((1,'boy'),(2,'dog'),(3,'cat'),(4,'aardvark'), (5,'cat')) 일때

출력값은 [('aardvark', 1), ('cat', 2)]가 된다.

 

실행 코드

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

#!/usr/bin/python

input=((1,'boy'),(2,'dog'),(3,'cat'),(4,'aardvark'), (5,'cat'))
def doMap(gen) : return [ (y,x) for x,y in gen if y.find('a') != -1]
def doReduce(gen):  return [(k,len(v))  for k,v in gen]
def doGroup(gen):             # accept a list of key,value pairs
    sl = list(gen)  # sort
    sl.sort()
    if not sl: return         # might be empty
    rkey, rlist = sl[0][0], [sl[0][1]] # a key and list to return
    for k,v in sl[1:]:        # process rest of sorted list
        if k==rkey:
            rlist.append(v) # extend the list for this key
        else:
            yield (rkey, rlist) # output key & list
            rkey, rlist = k, [v]# start next key & list
    yield(rkey, rlist)          # output last key & list

print doReduce(doGroup(tuple(doMap(input))))

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

 

초기 입력으로((1,'boy'),(2,'dog'),(3,'cat'),(4,'aardvark'), (5,'cat'))
가 doMap을 실행하면

(3,'cat'),(4,'addrdvark'),(5,'cat')이 리턴이 되고

다시 doGroup를 실행하면 (addrdark,[4]),(cat,[3,5])가 리턴이 된다.

최종적으로 doReduce에서 [('aardvark', 1), ('cat', 2)]라 리턴된다.

#1 ((1,'boy'),(2,'dog'),(3,'cat'),(4,'aardvark'), (5,'cat'))
#2  (3,'cat'),(4,'addrdvark'),(5,'cat')
#3  (addrdark,[4]),(cat,[3,5])

#4  [('aardvark', 1), ('cat', 2)]

참고 : http://pdos.csail.mit.edu/6.824/papers/mapreduce.pdf