软件工程结对项目第二次作业
031502210 邓弘立
031502245 郑荣尧
项目Github：
https://github.com/Maple27/S-D_Match
最“好”的数据
https://github.com/Maple27/S-D_Match/blob/master/input_data.txt
生成原理：
- 根据所给的的Json数据格式，构造出输入格式的bean类。对于数据的生成，采用了Java随机数生成的方法，将部门和学生的数据生成。生成数据时，我考虑了可能的重复性，所以在生成后对冗余（重复）数据进行了筛选和删除，保证了数据的完全随机性。
数据建模
- 主函数类：生成数据类对象，执行输入输出，生成结果，程序的入口。
- 学生类：拥有学号，空余时间，兴趣TAGS，意愿，是否被部门选中和对各部门的优先级的成员属性，并拥有对应的Getter和Setter方法
- 部门类：拥有部门ID，活动时间表，部门类型TAGS和上限人数的成员属性，并拥有对应的Getter和Setter方法
- 输入Bean类与输出Bean类：通过InputBean类将从txt文件读取的Json转换为程序中的数据以使用。通过OutputBean类将程序运行得到的结果转换成Json数据并输出到txt文件中。
- 匹配类：核心类，承载数据的初始化和输入输出的方法，同时具备对部门学生进行排序和智能匹配的核心算法。
- 数据生成类：自动生成数据的类，主要通过随机数实现。
匹配程序思路
- 要做到部门和学生匹配，首先要明确的目标应该是部门所能接纳的人数和学生总数的关系。
在部门能接纳的人数大于学生人数的时候，学生应该具有优势选择权，最优方法是遍历学生匹配部门；
当学生人数超过部门接纳人数时，部门占据优势，最优方法应该是遍历部门逐个匹配学生；
本题学生300人，部门20个，各部门人数10-15，满足后者条件。所以采用了DtoS的匹配方式。
本人采用了优先级算法，以意愿为基本条件，兴趣和时间为辅助条件对学生进行进行排序，优先级高的先被选中。
实现方式
- 读入当前目录下input_data.txt文件
- 根据读入的文件通过bean类解析并初始化数据（学生，部门的信息）
- 将部门根据tags的数量进行排序（使用了快速排序算法），tags少的部门优先进行匹配
- 统计学生在各个部门的优先级，优先级算法如下：优先级初始为0.学生一周中每有1小时free_time与部门event_schedule时间对应，优先级+1，学生每有一个兴趣tag与部门tags对应，优先级+2.
- 匹配过程：以学生志愿为基本条件（不符合即不选），从tags最少的部门开始，先对学生以在该部门的优先级进行排序，再按第一志愿到最低志愿，遍历学生（三重循环：部门-志愿-学生），符合即选中，并将结果加载到bean类。
- 通过bean类构造json数据，输出output_data.txt
代码规范
- 主要以本人的代码习惯为主，搭档提供模型设计
关键代码
//根据部门tags数量从小到大将部门排序
public void sortDepartment(List<Department> list, int low, int hight) {
int i, j;
Department index;
if (low > hight) {
return;
}
i = low;
j = hight;
index = list.get(i);
while (i < j) {
while (i < j && list.get(j).getTagsSize() >= index.getTagsSize())
j--;
if (i < j){
list.set(i++, list.get(j));
}
while (i < j && list.get(i).getTagsSize() < index.getTagsSize())
i++;
if (i < j)
list.set(j--, list.get(i));
}
list.set(i, index);
sortDepartment(list, low, i - 1);
sortDepartment(list, i + 1, hight);
}
//统计各个学生在各部门的优先级
public void countStudentScore(){
for(int i=0;i<departments.size();i++){
for(int j=0;j<students.size();j++){
List<String> dTimes = departments.get(i).getActivityTime();
List<String> sTimes = students.get(j).getFreeTime();
List<String> dTags = departments.get(i).getTags();
List<String> sTags = students.get(j).getInterests();
int score = 0;
//时间优先级统计
for(int m=0;m<dTimes.size();m++){
String str1 = dTimes.get(m);
String[] string2 = str1.split("\\.");
String[] string3 = string2[1].split("~");
String[] string4 = string3[0].split(":");
String[] string5 = string3[1].split(":");
String day1 = string2[0];
int start1 = Integer.parseInt(string4[0]);
int end1 = Integer.parseInt(string5[0]);
for(int n=0;n<sTimes.size();n++){
String str2 = sTimes.get(n);
String[] string6 = str2.split("\\.");
String[] string7 = string6[1].split("~");
String[] string8 = string7[0].split(":");
String[] string9 = string7[1].split(":");
String day2 = string6[0];
int start2 = Integer.parseInt(string8[0]);
int end2 = Integer.parseInt(string9[0]);
if(day1.equals(day2)){
if(end1<=start2||end2<start1){
score += 0;
}
else if(start1<start2&&end1>start2&&end1<end2){
score += end1-start2;
}
else if(start2<start1&&end2>start1&&end2<end1){
score += end2-start1;
}
else if(start1>start2&&end1<end2){
score += end1-start1;
}
else if(start2>start1&&end2<end1){
score += end2-start2;
}
}
}
}
//兴趣优先级统计
for(int p=0;p<dTags.size();p++){
String tag1 = dTags.get(p);
for(int q=0;q<sTags.size();q++){
String tag2 = sTags.get(q);
if(tag1.equals(tag2)){
score += 2;
}
}
}
//将此部门与学生匹配的优先级加入学生信息中
students.get(j).getScores().add(score);
}
}
}
//部门-学生匹配算法（D->S）
public void match_DtoS(){
for(int i=0;i<departments.size();i++){//部门遍历
int num = 0,flag = 0;
//每次对一个部门招募时以学生对此部门的分数对学生进行重新排列
sortStudent(students, 0, students.size()-1, i);
for(int j=0;j<5;j++){//志愿遍历
for(int k=0;k<students.size();k++){//学生遍历
//超限 下一个
if(num>=departments.get(i).getLimit()){
flag=1;
break;
}
//志愿不足 下一个
if(students.get(k).getWillsSize()<=j) continue;
String wills = students.get(k).getWills().get(j);
String no = departments.get(i).getId();
if(wills.equals(no)){
//符合志愿条件，根据符合分数进行分配
departments.get(i).getMembers().add(students.get(k));
students.get(k).setFlag(1);
num++;
}
}
if(flag==1) break;
}
departments.get(i).setNum(num);
}
for(int i=0;i<departments.size();i++){
for(int p=0;p<departments.get(i).getMembers().size()-1;p++){
for(int j=departments.get(i).getMembers().size()-1;j>p;j--){
if(departments.get(i).getMembers().get(j).equals(departments.get(i).getMembers().get(p))){
departments.get(i).getMembers().remove(j);
}
}
}
}
}结果评估
- 对于匹配结果，由于部门能收纳的人数小于学生总数，但却没有达到部门人数为满，可能是数据限制，但大概率是匹配算法的不足。这个匹配算法是自己想出来的，对数据进行了较多的前期处理，但在核心的匹配层面上可能还有很大的缺陷，一时间不知道如何改进。但结果的匹配率本人还是满意的，符合大学生部门招收新人的大致思路，基本没有遗漏最好的人选(兴趣时间双重占比考虑)。
- 助教的测试样例中可以跑出62个未被选中的学生和248个被接收的学生总数以及0个没有被选中的部门。自己生成的输入数据中未被选中的学生大致在60-80之间，被接收的学生总数在240-270之间，且未发现有没被选中的部门。
结对感言
- 这次结对赶上国庆中秋双节假期，和搭档没有上一次那么多的交流，但通过QQ还是确立了基本的思路，并且在算法上进行了深入的讨论，对这次程序的产生还是十分满意的，希望下次能越做越熟练。
搭档这次在数据建模和设计图方面贡献较大，希望他能提高代码能力，望互相补足。