MapReduce实现查找共同好友
2019-07-10 本文已影响0人
Kcrise
引言
近日在做MapReduce的练习，以下纯属于个人的想法，实现可能较为拙劣。而且本人python小白，文章只是为了做个学习思考的记录，大神们请自动绕过。
1、题目：使用MapReduce实现，查找共同好友。好友关系如下：
A:B,C,D,F,E,O
B:A,C,E,K
C:F,A,D,I
D:A,E,F,L
E:B,C,D,M,L
F:A,B,C,D,E,O,M
G:A,C,D,E,F
H:A,C,D,E,O
I:A,O
J:B,O
K:A,C,D
L:D,E,F
M:E,F,G
O:A,H,I,J
2、思路分析：
是否能用join的方式？然后基于join的字段进行分桶并排序。
举个内容少点的例子:
A:B,C,D,E
B:C,D,E
C:D,E
D:E
将左边的人进行组合为
AB AC AD BC BD CD
把与自己相关的组合，进行组合输出。
比如第一行的A，要于AB AC AD进行组合输出。
可以理解为将所有的可能出现共同好友的组合全部罗列出来。
第一行处理为：
A AB B,C,D,E
A AC B,C,D,E
A AD B,C,D,E
第二行处理为：
B AB C,D,E
B BC C,D,E
B BD C,D,E
第三行处理为：
C AC D,E
C BC D,E
C CD D,E
第四行处理为：
D AD E
D BD E
D CD E
3、map.py代码：
import sys
from itertools import combinations
#保存下所有好友关系
nameList = {}
#存放":"左边的人，用于组合两两的好友关系
friSet = set()
for line in sys.stdin:
name, friends = line.strip().split(':')
nameList[name] = friends
#所有的人
for name in nameList.keys():
friSet.add(name)
#人-人的所有组合
friEarch = list(combinations(friSet, 2))
for key,value in nameList.items():
for couple in friEarch:
if key == couple[0] or key == couple[1]:
print "%s\t%s-%s\t%s" % (key, couple[0],couple[1], value)
4、reduce阶段就简单了，因为已经基于两两好友(需要join的key值)进行了sort和partition
import sys
cur_key = ""
flist = []
for line in sys.stdin:
name, key, value = line.strip().split("\t")
if cur_key == "":
cur_key = key
flist.append(value)
elif key != cur_key:
if len(flist) == 2:
a = flist[0].strip().split(",")
b = flist[1].strip().split(",")
#comfriend = ','.join(list(set(a).intersection(set(b))))
comfriend = ''.join(list(set(a).intersection(set(b))))
if len(comfriend):
print "%s\t%s" % (cur_key, comfriend)
flist = []
cur_key = key
flist.append(value)
else:
print "len(flist)=%d" % len(flist)
flist = []
cur_key = key
flist.append(value)
else:
flist.append(value)
flist.append(value)
a = flist[0].strip().split(",")
b = flist[1].strip().split(",")
#comfriend = ','.join(list(set(a).intersection(set(b))))
comfriend = ''.join(list(set(a).intersection(set(b))))
if len(comfriend):
print "%s\t%s" % (cur_key, comfriend)
5、运行脚本run.sh
. /etc/profile
#HADOOP_CMD="/usr/local/src/bin/hadoop"
HADOOP_CMD="hadoop"
STREAM_JAR_PATH="/usr/local/src/hadoop/share/hadoop/tools/lib/hadoop-streaming-2.6.5.jar"
INPUT_FILE_PATH="/homework/001comFriends/data.txt"
OUTPUT_FILE_PATH="/out_home/001comFriends"
$HADOOP_CMD fs -rm -r skipTrash $OUTPUT_FILE_PATH
$HADOOP_CMD jar $STREAM_JAR_PATH \
-input $INPUT_FILE_PATH \
-output $OUTPUT_FILE_PATH \
-mapper "python map.py" \
-reducer "python reduce.py" \
-file "./map.py" \
-file "./reduce.py" \
-jobconf "mapred.reduce.tasks=1" \
-partitioner org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner \
-jobconf mapred.output.key.comparator.class=org.apache.hadoop.mapred.lib.KeyFieldBasedComparator \
-jobconf stream.num.map.output.key.fields=2 \
-jobconf mapred.text.key.partitioner.options="-k2,2" \
-jobconf mapred.text.key.comparator.options="-k2,2 -k1,1" \
-jobconf "mapreduce.input.fileinputformat.split.minsize=1000"
6、运行结果：
[root@master]/root/code/Coding/01MapReduce/HomeWork/02test$hadoop fs -text /out_home/001comFriends/par*
A-B CE
A-C DF
A-D EF
A-E CBD
A-F CBEDO
A-G CEDF
A-H CEDO
A-I O
A-J BO
A-K CD
A-L EDF
A-M EF
B-D AE
B-E C
B-F ACE
B-G ACE
B-H ACE
B-I A
B-K AC
B-L E
B-M E
B-O A
C-B A
C-D AF
C-E D
C-F AD
C-G ADF
C-H AD
C-I A
C-K AD
C-L DF
C-M F
C-O AI
D-F AE
D-G AEF
D-H AE
D-I A
D-K A
D-L EF
D-M EF
D-O A
E-D L
E-F CBMD
E-G CD
E-H CD
E-J B
E-K CD
E-L D
F-H ACEDO
F-I AO
F-J BO
F-K ACD
F-L ED
F-M E
F-O A
G-F ACED
G-H ACED
G-I A
G-K ACD
G-L EDF
G-M EF
G-O A
H-J O
H-K ACD
H-L ED
H-M E
H-O A
I-H AO
I-J O
I-K A
I-O A
K-L D
K-O A
M-L EF
7、总结
方法缺陷：
如果map被切分成了多个，那么无法找全所有的两两好友组合。想过采用多个mr的，实现起来比较麻烦。
代码部分：
以下方法根本就不知道
list(combinations(friSet, 2)) #参考别人的
list(set(a).intersection(set(b))) #自己百度的
参考：
list(combinations(friSet, 2))
https://blog.csdn.net/qq_43350697/article/details/95249462
list(set(a).intersection(set(b)))
https://blog.csdn.net/m62484/article/details/70243335
