共同好友

发表于 | 分类于

题意

给出A-O个人中每个人的好友列表，求出哪些人两两之间有共同好友，以及他们的共同好友都有谁

原始文件：
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
输出格式：
A-B: C,E
…

解法一

此题旨在求两人之间的共同好友，原信息是<人，该人的所有好友>，因此首先以好友为键，人为值，交给reduce找出拥有此好友的所有人；再将这些人中两两配对作为键，之前的键（好友）作为值交给reduce去合并
简而言之我打算分成两个步骤，两次迭代
1）求出每一个人都是哪些人的共同好友
2）把这些人（用共同好友的人）作为key,其好友作为value输出
upload successful

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
package com.qunar.mr.sharefriends;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

import java.io.IOException;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class ShareFriends {
    /**
     * 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
     */
    public static class Map1 extends Mapper<Object, Text,Text,Text>{
        /**
         * 第一阶段的map函数主要完成以下任务
         * 	 1.遍历原始文件中每行<所有朋友>信息
         * 	 2.遍历“朋友”集合，以每个“朋友”为键，原来的“人”为值  即输出<朋友,人>
         */
        public void map(Object key,Text value,Context context) throws IOException, InterruptedException {
            String lines = value.toString();
            String cur = lines.split(":")[0];
            String[] friends = lines.split(":")[1].split(",");
            for (String f:friends) {
                context.write(new Text(f),new Text(cur));
            }
        }
    }

    /**
     * 第一阶段的reduce函数主要完成以下任务
     * 1.对所有传过来的<朋友，list(人)>进行拼接，输出<朋友,拥有这名朋友的所有人>
     */
    public static class Reduce1 extends Reducer<Text,Text,Text,Text>{
        public void reduce(Text key,Iterable<Text> values,Context context) throws IOException, InterruptedException {
            StringBuffer sb = new StringBuffer();
            for (Text v:values) {
                sb.append(v.toString()).append(",");
            }
            sb.deleteCharAt(sb.length() - 1);
            context.write(key,new Text(sb.toString()));
        }
    }
    /**
     *
     * A	I,K,C,B,G,F,H,O,D
     * B	A,F,J,E
     * C	A,E,B,H,F,G,K
     * D	G,C,K,A,L,F,E,H
     * E	G,M,L,H,A,F,B,D
     * F	L,M,D,C,G,A
     * G	M
     * H	O
     * I	O,C
     * J	O
     * K	B
     * L	D,E
     * M	E,F
     * O	A,H,I,J,F
     */


    /**
     *
     * //todo 如果A是B的好友，B也一定是A的好友，则不需要第一层job
     *
     * 第二阶段的map函数主要完成以下任务
     * 	1.将上一阶段reduce输出的<朋友,拥有这名朋友的所有人>信息中的 “拥有这名朋友的所有人”进行排序 ，以防出现B-C C-B这样的重复
     * 	2.将 “拥有这名朋友的所有人”进行两两配对，并将配对后的字符串当做键，“朋友”当做值输出，即输出<人-人，共同朋友>
     *
     */
    public static class Map2 extends Mapper<Object, Text,Text,Text>{

        public void map(Object key,Text value,Context context) throws IOException, InterruptedException {
            String line = value.toString();
            String[] friend_persons = line.split("\t");
            String friend = friend_persons[0];//todo
            String[] persons = friend_persons[1].split(",");
            Arrays.sort(persons); //todo 排序,以防出现B-C C-B这样的重复
            //两两配对
            for(int i=0;i<persons.length-1;i++){
                for(int j=i+1;j<persons.length;j++){
                    context.write(new Text(persons[i]+"-"+persons[j]+":"), new Text(friend));//todo friend值作为共同好友value
                }
            }
        }
    }

    /**
     * 第二阶段的reduce函数主要完成以下任务
     * 	1.<人-人，list(共同朋友)> 中的“共同好友”进行拼接 最后输出<人-人，两人的所有共同好友>
     */
    public static class Reduce2 extends Reducer<Text,Text,Text,Text>{
        public void reduce(Text key,Iterable<Text> values,Context context) throws IOException, InterruptedException {
            Set<String> set = new HashSet<String>();
            StringBuffer sb = new StringBuffer();
            for(Text friend : values){//todo 获取共同好友的集合
                if(!set.contains(friend.toString()))
                    set.add(friend.toString());
            }
            for(String friend : set){//todo 拼字符串
                sb.append(friend.toString()).append(",");
            }
            sb.deleteCharAt(sb.length()-1);
            context.write(key, new Text(sb.toString()));
        }
    }

    public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException {
        Configuration conf = new Configuration();

        //第一阶段
        Job job1 = Job.getInstance(conf,"shareFriends");
        job1.setJarByClass(ShareFriends.class);
        job1.setMapperClass(Map1.class);
        job1.setReducerClass(Reduce1.class);

        job1.setOutputKeyClass(Text.class);
        job1.setOutputValueClass(Text.class);

        FileInputFormat.setInputPaths(job1, new Path("/Users/lifei/qunarproject/hiveudf/src/main/java/com/qunar/mr/sharefriends/in"));
        FileOutputFormat.setOutputPath(job1, new Path("/Users/lifei/qunarproject/hiveudf/src/main/java/com/qunar/mr/sharefriends/out/01"));

        boolean res1 = job1.waitForCompletion(true);

        //第二阶段
        Job job2 = Job.getInstance(conf);
        job2.setMapperClass(Map2.class);
        job2.setReducerClass(Reduce2.class);

        job2.setOutputKeyClass(Text.class);
        job2.setOutputValueClass(Text.class);

        FileInputFormat.setInputPaths(job2, new Path("/Users/lifei/qunarproject/hiveudf/src/main/java/com/qunar/mr/sharefriends/out/01"));
        FileOutputFormat.setOutputPath(job2, new Path("/Users/lifei/qunarproject/hiveudf/src/main/java/com/qunar/mr/sharefriends/out/02"));

        boolean res2 = job2.waitForCompletion(true);

        System.exit(res2?0:1);

    }
    /**
     * A-B:	C,E
     * A-C:	D,F
     * A-D:	E,F
     * A-E:	B,C,D
     * A-F:	B,C,D,E,O
     * A-G:	C,D,E,F
     * A-H:	C,D,E,O
     * A-I:	O
     * A-J:	B,O
     * A-K:	C,D
     * A-L:	D,E,F
     * A-M:	E,F
     * B-C:	A
     * B-D:	A,E
     * B-E:	C
     * B-F:	A,C,E
     * B-G:	A,C,E
     * B-H:	A,C,E
     * B-I:	A
     * B-K:	A,C
     * B-L:	E
     * B-M:	E
     * B-O:	A
     * C-D:	A,F
     * C-E:	D
     * C-F:	A,D
     * C-G:	A,D,F
     * C-H:	A,D
     * C-I:	A
     * C-K:	A,D
     * C-L:	D,F
     * C-M:	F
     * C-O:	A,I
     * D-E:	L
     * D-F:	A,E
     * D-G:	A,E,F
     * D-H:	A,E
     * D-I:	A
     * D-K:	A
     * D-L:	E,F
     * D-M:	E,F
     * D-O:	A
     * E-F:	B,C,D,M
     * E-G:	C,D
     * E-H:	C,D
     * E-J:	B
     * E-K:	C,D
     * E-L:	D
     * F-G:	A,C,D,E
     * F-H:	A,C,D,E,O
     * F-I:	A,O
     * F-J:	B,O
     * F-K:	A,C,D
     * F-L:	D,E
     * F-M:	E
     * F-O:	A
     * G-H:	A,C,D,E
     * G-I:	A
     * G-K:	A,C,D
     * G-L:	D,E,F
     * G-M:	E,F
     * G-O:	A
     * H-I:	A,O
     * H-J:	O
     * H-K:	A,C,D
     * H-L:	D,E
     * H-M:	E
     * H-O:	A
     * I-J:	O
     * I-K:	A
     * I-O:	A
     * K-L:	D
     * K-O:	A
     * L-M:	E,F
     */
}

解法二

upload successful

  1. 将好友关系分配到两个 Map 进行处理，其中每个 Map 包含 3 条好友关系。对每一条好友关系进行拆分，若 Key 中的两个人为朋友，则记录 value 值为0，否则 value 值为 1。将拆分的结果进行排序，其中（A B）和（B A）作为同一个 key（A B）。

upload successful

  1. 分别对两个 Map 处理的记录进行初步合并，若两个记录的 Key 值相同且每条记录的 Value 都不为 0，则 Value 值加 1。(都为0的说明两者本身就是好友，不需要参与推荐)

    注意：
    在 Combine 阶段，必须保留 Value 为 0 的记录，否则，在 Reduce 阶段，获取的结果会出错。
    upload successful

  2. 通过 Reduce 方式，合并两个 Map 处理的 Combine 结果。

    1. 若两个记录的 Key 值相同且每条记录的 Value 都不为 0，则 Value 值加 1。
    2. 将 Value 值为 0 的记录删除。(本身就是好友，不需要推荐)
    3. 获取不为好友的两个用户之间的公共好友数：Key 为两个不为好友的用户，Value 是两个不是好友的用户之间的共同好友数。社交网站或者 APP 可以根据这个数值对不是好友的两个用户进行推荐。

upload successful

参考：
https://blog.csdn.net/u012808902/article/details/77513188
https://help.aliyun.com/document_detail/58590.html?spm=a2c4g.11186623.6.728.45e5693dRhOoRo#h2-u5B9Eu9A8Cu4ECBu7ECD