论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2014-12-02 09:40 |显示全部楼层 |倒序浏览

本帖最后由 KoomIer 于 2014-12-05 09:57 编辑

开奖了，开奖了，恭喜reyleon 六神夺冠
感谢本次代码活动的所有参与者：银风冷月；Linux_manne；zxy877298415；yinyuemi；reyleon；ssfjhh；这个冬天不冷；jcdiy0601；love_shift；Hadron74

测试用例：
file1             2331859 条记录
file2             2147472 条记录
Onlyinfile2          1484
Onlyinfile1       185871
Equal             1456617
1bigger2          462172
1less2             227199

测试环境
solaris bash python2.6（这里要对manne，Hadron74道歉，因为我开始没有声明代码环境）

测试结果

银风冷月	08:54.8
Linux_manne	no result	应该是源代码环境py3
zxy877298415	no result	bash，语法错误，我没检查出来
yinyuemi	逻辑错误	排序36s；计算5:11.4；生成文件25s，但是最后结果与标准答案不合
relyeon	02:21.5
ssjhh	no result	可能也是py3，逻辑沿袭relyeon，精简了代码
这个冬天不冷	no result	PhP代码无测试环境
jcdiy	no result	文件验证条件较多，改了几次无果放弃
Linux_manne	no result	py3？
love_shift	07:22.5
Hadron74	no result	py3

算法思路的几个精彩两点
1，字典，集合
   以银风为代表，这类代码主要思路为
   读两个文件，讲两个文件内容存入字典，对两个字典键值集合比较得到一个交集两个差集，然后三个子集的的每个键值数据进行处理写入文件
   该方法的可改进点
   a，三个子集的数据处理可以多线程同步做（love_shift）
   b，对文件的写入可以先存入一个变量，最终写入文件，最后只做5次文件写入开关动作，避免一个键值做一次写入操作(Linux_manne)

2，强行闯入式
   以六神relyeon,ssjhh为代表
   读一个文件并建立字典，以另一个文件为输入，做查字典动作从而得到4类（查到了3类，查到后从字典删除这行记录，查不到说明只有文件2有）最后查完了删剩下的就只有文件1有
以上一个方法形象的对比就是：你去拜访亲戚，银风先打电话问到了亲戚在不在家再考虑怎么去拜访，而六神就直接去了不在家就撬门自己煮面，多的消耗时间是电话时间
该方法可改进点
   a，内存足够的情况下减少文件写入次数，先存变量最后一次写入
   b, 这里多线程不好做，除非文件打断，多个数据同时闯入，文件小的调度开销不一定值

3，切菜归并算法
   以Hadron74 和SS(北京冬天不冷刁钻哭大神)为代表
   我以前不知道归并算法，看了下大概理解是这样的
   先对两个文件单独排序，然后存字典然后再做归并排序，关键在于多了键值比较，下图你可以理解为切菜也可以理解我一个两边都掉齿的拉链

归并算法讲解：
可以理解为切菜，我们两根菜放一起对齐从菜头开始切，切到的第一个永远是最小的，如果只切到一个说明另一个里面没有
如果切到两个，这个时候我们比值然后处理，
与闯入式方法比较：多了前期一个排序的消耗，减少了查字典的难度

@all
银风冷月；Linux_manne；zxy877298415；yinyuemi；reyleon；ssfjhh；这个冬天不冷；jcdiy0601；love_shift；Hadron74
请私信我地址，我好准备寄出神秘礼物，当然了也会发的有点慢哈，最近外外头

此题长期开放，提供py2.6 bash 环境测试
鉴于本菜鸟shell,python都是初学水平，导致有些测试失败实在抱歉，同样欢迎算法大大给我们具体分析下上面的算法

--------------------------------------------------------------
我今天收到了一个从台湾寄来的神秘礼物，是从4月出发的，今天才到南京
今天的速度最高者，将得到一份同类型的神秘礼物

目标追求效率，服务器内存和cpu足够，两个文本文件分别在200w行左右