第六期Power8大赛
1.1 比赛题目
题目：
计算两个集合的差集；
详细说明：
分别有集合A和B两个大数集合，求解集合A与B的差集(A中有，但B中无的元素)，并将结果保存在集合C中，要求集合C中的元素升序。
输入为两个文件，分别为A.txt，B.txt，一行一个值，并且是无序的。结果输出到C.txt，即输入文件的差集，一行一个值，并且要求结果升序排列。
考量点：
(1) 大数集合求差集；
(2) 大数据集合排序；
题目实例：
例如，若集合A={5,20,10,15,25,30}，集合B={15,5,35,25}，完成计算后A={10,20,30}。
1.2 程序功能要求
(1)程序执行时传入三个参数(输入输出文件尽量与可执行文件在同一目录下)：
1)参数一：输入文件./A.txt路径；
2)参数二：输入文件./B.txt路径；
3)参数三：输出文件./C.txt路径；
(2)程序运行结果必须输出到文件./C.txt，文件格式要求：
1)一行一个值；
2)差集必须以升序排列；
(3)程序屏幕直接打印三行信息，形式如下：
num: XX
max: num1
min: num2
//num为差集个数，max差集中的最大值，min为差集中的最小值;
实例：例如，当集合A={5,20,10,15,25,30}，集合B={15,5,35,25}，屏幕输出形如：
num: 3
max: 30
min: 10
1.3 作品打包要求
(1)程序源码；
(2)作者自己生成的可执行文件，并且命名为csdn；
(3)程序编译Shell脚本make.sh：执行这个编译脚本，可以在当前目录生成可执行文件csdn；
(4)可执行文件执行Shell脚本run.sh：连续执行三次csdn(可执行文件)，并且每次使用time命令获取时间；
(5)说明文件readme.txt分条罗列以下信息：
1)程序编译说明；
2)程序运行说明；
3)作者连续执行三次的平均时间；
4)程序的设计思路，尽可能详细地有条理地陈述；
(6)执行run.sh脚本的截图，时间必须与说明文件readme.txt中的平均时间对应。
1.4 校验流程说明
(1)程序功能必须满足1.2所述，不然程序判为不合格；
(2)程序打包必须满足1.3所述，不然无法进行正常程序校验，判为不合格；
(3)作者提供的截图以及说明文件readme.txt中的平均时间仅作参考，具体时间以校验时间为准；
(4)程序校验步骤说明：
1)查看作者截图，屏幕输出是否正确，若正确进行下一步；
2)直接执行run.sh获取三次的执行时间，即使用作者提供的可执行文件csdn进行执行；
3)删除csdn可执行文件，执行make.sh，再执行run.sh脚本，获取三次的执行时间；
4)查看是否有输出文件C.txt，获取C.txt与标准结果进行校验；
5)若输出校验无误，则以步骤(3)获取的平均时间为最终作品校验时间；
我的作答
1. 解题思路：
判断两个集合的差集——求 A 中有，但是 B 没有的元素——数据结构选择哈希表来存储 B 表。
从内存流中每次读取一个 A 集合中的元素，使用 unordered_set::find() 来确定 B 中是否存在该元素，如果 B 中不存在则将该元素，则将元素加入新的 unordered_set<T> 集合。最后函数返回新的 unordered_set<T> 集合。
1.2 新的解题思路：
hashmap 对内存的使用率不足 50% ——因为装填因子最好小于 0.5 具体取决于冲突的解决方法——所以使用 bitmap 是更省内存的方法，但前提是已经知道了数值范围。
2. 项目源代码
2.1 main.cpp
#include <fstream>
#include <unordered_set>
#include <set>
#include <iostream> using namespace std; typedef unsigned DataType; set<DataType>* fileDifferent(ifstream &ifile1, ifstream &ifile2)
{
unordered_set<DataType> *m = new unordered_set<DataType>();
set<DataType> *v = new set<DataType>(); DataType num; while (ifile1 >> num)
m->insert(num); while (ifile2 >> num)
{
if (m->find(num) == m->end())
v->insert(num);
} delete m; return v;
} int main(int argc, char *argv[])
{ if(argc != )
{
cout << "./a.out A.txt B.txt C.txt" << endl;
return ;
} cout << argv[] << " " << argv[] << " " << argv[] << endl; ifstream ifile1(argv[]);
ifstream ifile2(argv[]); ofstream ofile1;
ofile1.open(argv[], ofstream::out); set<DataType>* p = fileDifferent(ifile1, ifile2); cout << "num: " << p->size() << endl;
cout << "max: " << *(--p->end()) << endl;
cout << "min: " << *(p->begin()) << endl; for (set<DataType>::const_iterator it = p->cbegin(); it != p->cend(); it++)
ofile1 << *it << "\n"; delete p; ifile1.close();
ifile2.close();
ofile1.close(); return ;
}
2.2 Makefile 文件
OBJ=csdn
FLAGS=-std=c++ -Wall -O2 all:
g++ -o $(OBJ) main.cpp $(FLAGS) test:
(./$(OBJ) A.txt B.txt C.txt)
(./$(OBJ) a.txt b.txt c.txt) debug:
g++ -o $(OBJ) main.cpp $(FLAGS)
(gdb $(OBJ)) clean:
rm $(OBJ)
rm C.txt
2.3 run.sh 文件
#!bin/sh/bash time ./csdn A.txt B.txt C.txt
time ./csdn A.txt B.txt C.txt
time ./csdn A.txt B.txt C.txt
2.4 make.sh 文件
#!bin/sh/bash make clean
make all
3. 附件
3.1 A.txt 和 B.txt
https://yunpan.cn/crDtxZkcWHRHy （提取码：a59d）
3.2 项目源码结构
/---Power8-6th
/--- A.txt
/--- B.txt
/--- main.cpp
/--- Makefile
/--- run.sh
/--- make.sh