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。