Python版的一個計算好友相似度的MapReduce實現

     背景是一個8萬多人的小型社區，平均每個用戶添加了4.792名好友，好友數最多的用戶有3000多名好友，也有4萬多用戶沒有添加任何好友（挺符合社交網絡長尾效應的）。

     話說經典的計算好友交集大小的代碼應該是這樣的：

for i in user_ids:
    for j in user_ids:
        if i == j:
            continue
        s = len(friends_i & friends_j)

     (friends_i和friends_j分別表示i和j的好友集合）

     這種實現的算法復雜度是O(N^2*M*2)，其中N表示用戶規模，M表示計算共同好友的兩名用戶添加的最小好友數。經測算，大概每名用戶需要5s的計算時間。

     而MapReduce就是把原來一步能完成的工作切成了三步，mapper -> sort -> reducer。其中mapper負責化整為零，把要計算的數據轉化成一行一行的key-value，sort負責把相同的key比鄰排列，reducer則負責和mapper相反的工作，把零散的value值以一定的模式（比如累加）結合起來。

     網上流傳的演示MapReduce的都是一個WordCount的例子，好友相似度的計算涉及到兩個對象的關系，數據的輸入和key-value的設計還是要花點心思的。

     具體mapper的程序是這樣實現的：

def do_map():
     for i in user_ids:
          if friends_i is None:
               continue
          for j in friends_i:
               if  friends_j is None:
                    continue
               for k in friends_j:
                    # 排除k和i本來就已經是好友的情況
                    if k == i or k in friends_i:
                         continue
                    print '%s_%s,%s' % (i, k, 1)

     這一步輸出的是這樣的key-value格式：

74722_10622,1

50041_10622,1

74722_10622,1

10622_50041,1

……

     兩個有共同好友的id用下劃線分割，value表示出現的次數。

     經過了sort之后，相同的key被放在一起，變成了這樣的排列：

10622_50041,1

50041_10622,1

74722_10622,1

74722_10622,1

……

     reducer是一個標準的累加計數程序，和WordCount的實現并無二致：

def do_reduce(fin = sys.stdin):
    prev_key = None
    key = None
    current_count = 0
    for line in fin:
        key, count = line.split(',', 1)
        count = int(count)
        if key == prev_key:
            current_count += count
        else:
            if prev_key:
                print >> x, '%s,%s' % (prev_key, current_count)
            current_count = count
            prev_key = key
     #打印最后一行
    if key == prev_key:
        print '%s,%s' % (prev_key, current_count)

     經過reducer之后，相同的key出現的次數被累加，得出任意兩個用戶的共同好友數，也就是好友相似度的分子：

10622_50041,1

50041_10622,1

74722_10622,2

……

     總共耗時17分21秒。與頭一種算法相比，MapReduce的計算時間只有前者的百分之一。

     大概估算了算法復雜度：

     1. maper的算法復雜度大約是O(N*M^2)，其中M表示整個社區所有用戶的平均好友數，應該可以輕松得證，任意兩名用戶的好友數積的平均值小于平均好友數的平方。

     2. linux的sort采用的是歸并排序，算法復雜度不超過O(N*logN)。

     3. reducer的算法復雜度大約是O(N*M)。

     可見MapReduce確實降低了算法復雜度，另一方面也歸功于Python在文本處理方面的效率。

后記：

     之后好奇了一把，用python的dict重復了實驗，發現寫dict寫到一半就假死了，dict大小是40665020。