免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 4972 | 回复: 20

文本计算比较 [复制链接]

论坛徽章:
0
发表于 2014-12-02 09:40 |显示全部楼层
本帖最后由 KoomIer 于 2014-12-05 09:57 编辑

开奖了,开奖了 , 恭喜reyleon 六神夺冠
感谢本次代码活动的所有参与者:银风冷月Linux_mannezxy877298415yinyuemireyleonssfjhh这个冬天不冷jcdiy0601love_shiftHadron74


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

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

测试结果
银风冷月
08:54.8

Linux_manneno result应该是源代码环境py3
zxy877298415no resultbash,语法错误,我没检查出来
yinyuemi 逻辑错误排序36s;计算5:11.4;生成文件25s,但是最后结果与标准答案不合
relyeon
02:21.5

ssjhhno result可能也是py3,逻辑沿袭relyeon,精简了代码
这个冬天不冷no resultPhP代码无测试环境
jcdiyno result文件验证条件较多,改了几次无果放弃
Linux_manneno resultpy3?
love_shift
07:22.5

Hadron74no resultpy3



算法思路的几个精彩两点

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

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

3, 切菜归并算法
      以Hadron74 和SS(北京冬天不冷刁钻哭大神)为代表
     我以前不知道归并算法,看了下大概理解是这样的
      先对两个文件单独排序,然后存字典 然后再做归并排序,关键在于多了键值比较,下图你可以理解为切菜也可以理解我一个两边都掉齿的拉链
     
1.jpg
归并算法讲解:
    可以理解为切菜, 我们两根菜放一起对齐从菜头开始切,切到的第一个永远是最小的,如果只切到一个说明另一个里面没有
    如果切到两个,这个时候我们比值然后处理,
    与闯入式方法比较: 多了前期一个排序的消耗,减少了查字典的难度


@all
银风冷月Linux_mannezxy877298415yinyuemireyleonssfjhh这个冬天不冷jcdiy0601love_shiftHadron74
请私信我地址,我好准备寄出神秘礼物,当然了也会发的有点慢哈,最近外外头

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




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


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

  1. $cat file1
  2. 1221  2453
  3. 1223  5687
  4. 1243  7683
  5. 1245  1000

  6. $cat file2
  7. 1221 2453
  8. 1223 2000
  9. 1245 5612
  10. 1265 8000
  11. 1287 4321
复制代码
期望输出结果: 第一列为索引, 第二列为值, 当第一列索引号相同的时候做差, 当找不到的时候放到另一个文件
生成五个文件, 一个相等的,一个正差,一个逆差, 两个only出现在一个文件中的

  1. cat result1
  2. 1221 equal 2453
  3. cat result2
  4. 1223 file1biggerfile2 3678
  5. cat result3
  6. 1245 2bigger1 5612
  7. cat result4
  8. 1243 onlyinfile1  7683
  9. cat result5
  10. 1265 onlyinfile2 8000
  11. 1287 onlyinfile2 4321
复制代码
1.jpg

论坛徽章:
2
白羊座
日期:2014-06-17 11:04:28午马
日期:2014-12-29 15:37:13
发表于 2014-12-02 10:27 |显示全部楼层
  1. #!/usr/bin/env python
  2. # -*- coding:utf8 -*-

  3. d1 = {}
  4. d2 = {}

  5. for i in open("E:\\file1.txt"):
  6.     l = i.strip().split()
  7.     d1[l[0]] = l[1]

  8. for i in open("E:\\file2.txt"):
  9.     l = i.strip().split()
  10.     d2[l[0]] = l[1]

  11. x = set(d1.keys())
  12. y = set(d2.keys())
  13. for i in x&y:
  14.     if int(d1[i]) == int(d2[i]):
  15.         f = open('result1.txt','a+')
  16.         f.write('%s equal %s\n'%(i,d1[i]))
  17.         f.close()
  18.     elif int(d1[i]) > int(d2[i]):
  19.         f = open('result2.txt','a+')
  20.         f.write('%s file1biggerfile2 %s\n'%(i,d1[i]))
  21.         f.close()
  22.     else:
  23.         f = open('result3.txt','a+')
  24.         f.write('%s file2biggerfile1 %s\n'%(i,d2[i]))
  25.         f.close()

  26. for i in x-y:
  27.     f = open('result4.txt','a+')
  28.     f.write('%s onlyinfile1 %s\n'%(i,d1[i]))
  29.     f.close()
  30. for i in y-x:
  31.     f = open('result5.txt','a+')
  32.     f.write('%s onlyinfile2 %s\n'%(i,d2[i]))
  33.     f.close()
复制代码
可以试试

论坛徽章:
5
巨蟹座
日期:2014-08-28 18:12:342015年迎新春徽章
日期:2015-03-04 10:01:4415-16赛季CBA联赛之江苏
日期:2016-04-28 09:43:3115-16赛季CBA联赛之吉林
日期:2016-06-22 10:34:4315-16赛季CBA联赛之山西
日期:2016-08-16 16:29:55
发表于 2014-12-02 10:28 |显示全部楼层
本帖最后由 Linux_manne 于 2014-12-02 15:29 编辑

  1. def fequal(c):
  2.     with open('result1','a') as f:
  3.         f.writelines(c+"\n")

  4. def fbigger(c):
  5.     with open('result2','a') as f:
  6.         f.writelines(c+"\n")

  7. def fsmaller(c):
  8.     with open('result3','a') as f:
  9.         f.writelines(c+"\n")


  10. def fonly(fname,c):
  11.     with open(fname,'a') as f:
  12.         f.writelines(c+"\n")



  13. f1 = open('file1','r')
  14. f2 = open('file2','r')

  15. d1 = dict(line.split() for line in f1)
  16. d2 = dict(line.split() for line in f2)
  17. x = set(d1.keys())
  18. y = set(d2.keys())
  19. for k in x-y:
  20.     fonly("result4","%s only file1 %s" %(k,d1[k]))

  21. for k in y-x:
  22.     fonly('result5','%s only file2 %s' %(k,d2[k]))

  23. for k in x&y:
  24.     if k in d2.keys():
  25.         if d1[k] == d2[k]:
  26.             fequal("%s equal %s" %(d1[k],d2[k]))
  27.         if d1[k] > d2[k]:
  28.             fbigger('file1 bigger file2')
  29.         if d1[k] < d2[k]:
  30.             fsmaller('file2 bigger file1')

复制代码
我修改下

论坛徽章:
30
申猴
日期:2014-04-10 09:43:532015年亚洲杯纪念徽章
日期:2015-03-20 14:40:232015亚冠之阿尔纳斯尔
日期:2015-06-02 18:59:042015亚冠之阿尔希拉尔
日期:2015-06-30 15:22:572015亚冠之大阪钢巴
日期:2015-07-20 10:44:332015亚冠之阿尔纳斯尔
日期:2015-10-28 14:57:5215-16赛季CBA联赛之新疆
日期:2015-12-25 10:18:45黑曼巴
日期:2016-06-26 21:39:5315-16赛季CBA联赛之山西
日期:2016-07-25 21:54:2715-16赛季CBA联赛之北京
日期:2016-10-27 12:07:2315-16赛季CBA联赛之八一
日期:2017-07-07 16:39:0915-16赛季CBA联赛之吉林
日期:2017-09-04 12:14:43
发表于 2014-12-02 10:38 |显示全部楼层
awk 'FNR==NR{a[$1]=$2;next}{if(($1 in a)&&(a[$1]==$2)) {print $1,"equal",$2>"result1 ";delete a[$1]}
> else if(($1 in a)&&(a[$1]>$2)) {print $1,"file1biggerfile2",$2>"result2";delete a[$1]}
> else if(($1 in a)&&(a[$1]<$2)) {print $1,"file2biggerfile1",$2>"result3";delete a[$1]}
> else if (!($1 in a)) {print $1,"only in file2",$2>"result4";delete a[$1]}
>  }END{for (i in a) print i,"only in file1",a[i]>"result 5"}' file1 file2


   

论坛徽章:
2
射手座
日期:2014-10-10 15:59:4715-16赛季CBA联赛之上海
日期:2016-03-03 10:27:14
发表于 2014-12-02 12:02 |显示全部楼层
回复 1# KoomIer
  1. #!/usr/bin/env python

  2. f1=open("file1","r");
  3. f2=open("file2","r");

  4. def read_f1():
  5.     return f1.readline().strip().split()
  6. def read_f2():
  7.     return f2.readline().strip().split()

  8. line1=[];
  9. line2=[]
  10. line1=read_f1()
  11. line2=read_f2()

  12. while 1:
  13.     if not line1:
  14.         print "file2only\t","\t".join(line2)
  15.         line2=read_f2()
  16.     elif not line2:
  17.         print "file1only\t","\t".join(line1)
  18.         line1=read_f1()
  19.     elif int(line2[0]) > int(line1[0]):
  20.         print "file1only\t","\t".join(line1)
  21.         line1=read_f1()
  22.     elif int(line1[0]) > int(line2[0]):
  23.         print "file2only\t","\t".join(line2)
  24.         line2=read_f2()
  25.     elif int(line1[0]) == int(line2[0]):
  26.         if int(line1[1]) == int(line2[1]):
  27.             print "equal\t","\t".join(line2)
  28.         elif int(line1[1]) > int(line2[1]):
  29.             print "biggerinfile1\t",line1[0],"\t",(int(line1[1])-int(line2[1]))
  30.         else:
  31.             print "biggerinfile2\t",line2[0],"\t",(int(line2[1])-int(line1[1]))
  32.         line1=read_f1()
  33.         line2=read_f2()
  34.     if (not line1) and  (not line2):
  35.         break
复制代码

论坛徽章:
60
20周年集字徽章-20	
日期:2020-10-28 14:04:3015-16赛季CBA联赛之北京
日期:2016-07-06 15:42:0715-16赛季CBA联赛之同曦
日期:2016-06-12 10:38:0915-16赛季CBA联赛之佛山
日期:2016-05-27 11:54:56黄金圣斗士
日期:2015-12-02 11:44:35白银圣斗士
日期:2015-11-25 14:32:43白银圣斗士
日期:2015-11-23 12:53:352015亚冠之布里斯班狮吼
日期:2015-10-21 16:55:482015亚冠之首尔
日期:2015-09-01 16:46:052015亚冠之德黑兰石油
日期:2015-08-31 11:39:192015亚冠之萨济拖拉机
日期:2015-08-28 21:06:5315-16赛季CBA联赛之广东
日期:2016-07-12 14:58:53
发表于 2014-12-02 13:35 |显示全部楼层
本帖最后由 reyleon 于 2014-12-02 13:49 编辑
  1. #!/usr/bin/env python
  2. # -*- coding: utf-8 -*-

  3. d1 = {}
  4. s1 = open('result1', 'w+')
  5. s2 = open('result2', 'w+')
  6. s3 = open('result3', 'w+')
  7. s4 = open('result4', 'w+')
  8. s5 = open('result5', 'w+')

  9. with open('file1') as fd1:
  10.     for record in fd1:
  11.         line = record.strip().split()
  12.         d1.setdefault(line[0], line[1])

  13. with open('file2') as fd2:
  14.     for record in fd2:
  15.         line = record.strip().split()
  16.         k = line[0]
  17.         v = line[1]
  18.         if d1.get(k):
  19.             if v == d1[k]: s1.write('%s equal %s\n' %(k, v))
  20.             elif int(v) < int(d1[k]):  s2.write('%s file1biggerfile2 %s\n' %(v, int(d1[k])-int(v)))
  21.             elif int(v) > int(d1[k]):  s3.write('%s 2bigger1 %s\n' %(v, int(v)-int(d1[k])))
  22.             del d1[k]
  23.         else:
  24.             s5.write('%s onlyinfile2 %s\n' %(k, v))
  25. for k in d1: s4.write('%s onlyinfile1 %s\n' %(k, d1[k]))
复制代码

论坛徽章:
0
发表于 2014-12-02 13:37 |显示全部楼层
AWK我已经阴影了,读文本到内存的时候内存很难过180M, 算起来太慢了

回复 4# zxy877298415


   

论坛徽章:
4
金牛座
日期:2013-10-11 16:12:50卯兔
日期:2014-07-31 09:17:19辰龙
日期:2014-08-08 09:28:02狮子座
日期:2014-09-14 20:32:05
发表于 2014-12-02 14:57 |显示全部楼层
本帖最后由 ssfjhh 于 2014-12-02 15:18 编辑
  1. #!/usr/bin/env python
  2. # -*- coding:utf8 -*-

  3. with open('file1.txt') as f:
  4.     d1 = dict(l.strip().split() for l in f)

  5. with open('file2.txt') as f:
  6.     d2 = dict(l.strip().split() for l in f)

  7. result1 = open('result1.txt', 'w')
  8. result2 = open('result2.txt', 'w')
  9. result3 = open('result3.txt', 'w')
  10. result4 = open('result4.txt', 'w')
  11. result5 = open('result5.txt', 'w')

  12. for k, v in d1.items():
  13.     if k in d2:
  14.         v2 = d2[k]
  15.         if v == v2:
  16.             result1.write('{} equal  {}\n'.format(k, v))
  17.         elif v > v2:
  18.             result2.write('{} 1bigger2  {}\n'.format(k, v))
  19.         else:
  20.             result3.write('{} 2bigger1  {}\n'.format(k, v2))
  21.         d2.pop(k)
  22.     else:
  23.         result4.write('{} onlyinfile1  {}\n'.format(k, v))

  24. for k, v in d2.items():
  25.     result5.write('{} onlyinfile2  {}\n'.format(k, v))

  26. result1.close()
  27. result2.close()
  28. result3.close()
  29. result4.close()
  30. result5.close()
复制代码

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:58:11
发表于 2014-12-02 15:16 |显示全部楼层
本帖最后由 这个冬天不冷 于 2014-12-02 15:28 编辑
  1. <?php
  2. error_reporting(0);
  3. ini_set('memory_limit','2048M'); //修改php支持的最大内存
  4. $fp1 = fopen("file1.txt", "r") or die('no file1');
  5. $fp2 = fopen("file2.txt", "r") or die('no file2');

  6. $contents1 = fread($fp1, filesize('file1.txt'));
  7. $contents2 = fread($fp2, filesize('file2.txt'));

  8. $arr1 =  explode("\n", $contents1);
  9. $arr2 =  explode("\n", $contents2);

  10. $t1 = array();
  11. $t2 = array();
  12. foreach ($arr1 as $key => $value) {
  13.         if(!empty($value))
  14.                 $a_tmp = explode(" ", $value);
  15.         $t1[$a_tmp[0]] = end($a_tmp);
  16. }

  17. foreach ($arr2 as $key => $value) {
  18.         if(!empty($value))
  19.                 $a_tmp = explode(" ", $value);
  20.         $t2[$a_tmp[0]] = end($a_tmp);
  21. }

  22. //统计结果
  23. $xiangdeng = array();
  24. $cha1 = array();
  25. $cha2 = array();
  26. $no1 = array();
  27. $no2 = array();
  28. foreach ($t1 as $key => $value) {
  29.         if($t1[$key] > $t2[$key] && isset($t2[$key])) $cha1[count($cha1)] = "$key file1biggerfile2 $t1[$key]";
  30.         if($t1[$key] < $t2[$key] && isset($t1[$key])) $cha2[count($cha2)] = "$key file2biggerfile1 $t2[$key]";
  31.         if($t1[$key] == $t2[$key]) $xiangdeng[count($cha2)] = "$key equal  $t2[$key]";
  32. }

  33. //求只在文件2 中出现的
  34. foreach ($t2 as $key => $value) {
  35.         if(!isset($t1[$key])) $no2[count($no2)] = "$key onlyinfile2 $t2[$key]";
  36. }

  37. foreach ($t1 as $key => $value) {
  38.         if(!isset($t2[$key])) $no1[count($no2)] = "$key onlyinfile1 $t1[$key]";
  39. }

  40. $str = implode("\r\n", $xiangdeng);
  41. file_put_contents("result1", $str);
  42. $str = implode("\r\n", $cha1);
  43. file_put_contents("result2", $str);
  44. $str = implode("\r\n", $cha2);
  45. file_put_contents("result3", $str);
  46. $str = implode("\r\n", $no1);
  47. file_put_contents("result4", $str);
  48. $str = implode("\r\n", $no2);
  49. file_put_contents("result5", $str);

  50. echo '<pre>';
  51. print_r($xiangdeng);
  52. print_r($cha1);
  53. print_r($cha2);
  54. print_r($no1);
  55. print_r($no2);

  56. fclose($fp1);
  57. fclose($fp2);
复制代码
  1. Array
  2. (
  3.     [0] => 1221 equal  2453
  4. )
  5. Array
  6. (
  7.     [0] => 1223 file1biggerfile2 5687
  8. )
  9. Array
  10. (
  11.     [0] => 1245 file2biggerfile1 5621
  12. )
  13. Array
  14. (
  15.     [2] => 1243 onlyinfile1 7683
  16. )
  17. Array
  18. (
  19.     [0] => 1265 onlyinfile2 8000
  20.     [1] => 1287 onlyinfile2 4321
  21. )
复制代码
文件都不贴了,文件就是根据上面的数组运行结果 ,写入的

论坛徽章:
6
羊年新春福章
日期:2015-03-03 17:16:28双子座
日期:2015-03-03 17:16:56巳蛇
日期:2015-03-03 17:17:2415-16赛季CBA联赛之福建
日期:2016-03-11 09:05:00黑曼巴
日期:2016-07-07 16:58:1215-16赛季CBA联赛之吉林
日期:2016-11-14 09:23:07
发表于 2014-12-02 15:23 |显示全部楼层

  1. #!/usr/bin/env python
  2. # -*- coding:utf-8 -*-

  3. f1 = open('result1', 'w+')
  4. f2 = open('result2', 'w+')
  5. f3 = open('result3', 'w+')
  6. f4 = open('result4', 'w+')
  7. f5 = open('result5', 'w+')
  8. dict1 = {}
  9. dict2 = {}

  10. def dict(file):
  11.     if file == 'file1':
  12.         file = open(file,'r')
  13.         for line in file.readlines():
  14.             line = line.strip('\n')
  15.             list = line.split('  ')
  16.             dict1[list[0]] = list[1]
  17.     if file == 'file2':
  18.         file = open(file,'r')
  19.         for line in file.readlines():
  20.             line = line.strip('\n')
  21.             list = line.split(' ')
  22.             dict2[list[0]] = list[1]
  23. dict('file1')
  24. dict('file2')
  25. for k in dict1:
  26.     try:
  27.         if int(dict1[k]) == int(dict2[k]):
  28.             f1.write('%s equal %s\n' % (k,dict1[k]))
  29.         elif int(dict1[k]) < int(dict2[k]):
  30.             v = int(dict2[k]) - int(dict1[k])
  31.             f3.write('%s file2biggerfile1 %s\n' % (k,v))
  32.         elif int(dict1[k]) > int(dict2[k]):
  33.             v = int(dict1[k]) - int(dict2[k])
  34.             f2.write('%s file1biggerfile2 %s\n' % (k,v))
  35.     except:        
  36.         f4.write('%s onlyfile1 %s\n' % (k,dict1[k]))
  37. for k in dict2:
  38.     try:
  39.         if int(dict1[k]) == int(dict2[k]):
  40.             pass
  41.         if int(dict1[k]) < int(dict2[k]):
  42.             pass
  43.         if int(dict1[k]) > int(dict2[k]):
  44.             pass
  45.     except:
  46.         f5.write('%s onlyfile2 %s\n' % (k,dict2[k]))
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP