文本计算比较
本帖最后由 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_manneno result应该是源代码环境py3
zxy877298415no resultbash，语法错误，我没检查出来
yinyuemi 逻辑错误排序36s；计算5:11.4；生成文件25s，但是最后结果与标准答案不合
relyeon02:21.5
ssjhhno result可能也是py3，逻辑沿袭relyeon，精简了代码
这个冬天不冷no resultPhP代码无测试环境
jcdiyno result文件验证条件较多，改了几次无果放弃
Linux_manneno resultpy3？
love_shift07:22.5
Hadron74no resultpy3
算法思路的几个精彩两点
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行左右
$cat file1
12212453
12235687
12437683
12451000
$cat file2
1221 2453
1223 2000
1245 5612
1265 8000
1287 4321
期望输出结果: 第一列为索引， 第二列为值， 当第一列索引号相同的时候做差， 当找不到的时候放到另一个文件
生成五个文件， 一个相等的，一个正差，一个逆差， 两个only出现在一个文件中的
cat result1
1221 equal 2453
cat result2
1223 file1biggerfile2 3678
cat result3
1245 2bigger1 5612
cat result4
1243 onlyinfile17683
cat result5
1265 onlyinfile2 8000
1287 onlyinfile2 4321
#!/usr/bin/env python
# -*- coding:utf8 -*-
d1 = {}
d2 = {}
for i in open("E:\\file1.txt"):
l = i.strip().split()
d1] = l
for i in open("E:\\file2.txt"):
l = i.strip().split()
d2] = l
x = set(d1.keys())
y = set(d2.keys())
for i in x&y:
if int(d1) == int(d2):
f = open('result1.txt','a+')
f.write('%s equal %s\n'%(i,d1))
f.close()
elif int(d1) > int(d2):
f = open('result2.txt','a+')
f.write('%s file1biggerfile2 %s\n'%(i,d1))
f.close()
else:
f = open('result3.txt','a+')
f.write('%s file2biggerfile1 %s\n'%(i,d2))
f.close()
for i in x-y:
f = open('result4.txt','a+')
f.write('%s onlyinfile1 %s\n'%(i,d1))
f.close()
for i in y-x:
f = open('result5.txt','a+')
f.write('%s onlyinfile2 %s\n'%(i,d2))
f.close()可以试试 本帖最后由 Linux_manne 于 2014-12-02 15:29 编辑
def fequal(c):
with open('result1','a') as f:
f.writelines(c+"\n")
def fbigger(c):
with open('result2','a') as f:
f.writelines(c+"\n")
def fsmaller(c):
with open('result3','a') as f:
f.writelines(c+"\n")
def fonly(fname,c):
with open(fname,'a') as f:
f.writelines(c+"\n")
f1 = open('file1','r')
f2 = open('file2','r')
d1 = dict(line.split() for line in f1)
d2 = dict(line.split() for line in f2)
x = set(d1.keys())
y = set(d2.keys())
for k in x-y:
fonly("result4","%s only file1 %s" %(k,d1))
for k in y-x:
fonly('result5','%s only file2 %s' %(k,d2))
for k in x&y:
if k in d2.keys():
if d1 == d2:
fequal("%s equal %s" %(d1,d2))
if d1 > d2:
fbigger('file1 bigger file2')
if d1 < d2:
fsmaller('file2 bigger file1')
我修改下 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>"result 5"}' file1 file2
回复 1# KoomIer #!/usr/bin/env python
f1=open("file1","r");
f2=open("file2","r");
def read_f1():
return f1.readline().strip().split()
def read_f2():
return f2.readline().strip().split()
line1=[];
line2=[]
line1=read_f1()
line2=read_f2()
while 1:
if not line1:
print "file2only\t","\t".join(line2)
line2=read_f2()
elif not line2:
print "file1only\t","\t".join(line1)
line1=read_f1()
elif int(line2) > int(line1):
print "file1only\t","\t".join(line1)
line1=read_f1()
elif int(line1) > int(line2):
print "file2only\t","\t".join(line2)
line2=read_f2()
elif int(line1) == int(line2):
if int(line1) == int(line2):
print "equal\t","\t".join(line2)
elif int(line1) > int(line2):
print "biggerinfile1\t",line1,"\t",(int(line1)-int(line2))
else:
print "biggerinfile2\t",line2,"\t",(int(line2)-int(line1))
line1=read_f1()
line2=read_f2()
if (not line1) and(not line2):
break
本帖最后由 reyleon 于 2014-12-02 13:49 编辑
#!/usr/bin/env python
# -*- coding: utf-8 -*-
d1 = {}
s1 = open('result1', 'w+')
s2 = open('result2', 'w+')
s3 = open('result3', 'w+')
s4 = open('result4', 'w+')
s5 = open('result5', 'w+')
with open('file1') as fd1:
for record in fd1:
line = record.strip().split()
d1.setdefault(line, line)
with open('file2') as fd2:
for record in fd2:
line = record.strip().split()
k = line
v = line
if d1.get(k):
if v == d1: s1.write('%s equal %s\n' %(k, v))
elif int(v) < int(d1):s2.write('%s file1biggerfile2 %s\n' %(v, int(d1)-int(v)))
elif int(v) > int(d1):s3.write('%s 2bigger1 %s\n' %(v, int(v)-int(d1)))
del d1
else:
s5.write('%s onlyinfile2 %s\n' %(k, v))
for k in d1: s4.write('%s onlyinfile1 %s\n' %(k, d1)) AWK我已经阴影了，读文本到内存的时候内存很难过180M， 算起来太慢了
回复 4# zxy877298415
本帖最后由 ssfjhh 于 2014-12-02 15:18 编辑
#!/usr/bin/env python
# -*- coding:utf8 -*-
with open('file1.txt') as f:
d1 = dict(l.strip().split() for l in f)
with open('file2.txt') as f:
d2 = dict(l.strip().split() for l in f)
result1 = open('result1.txt', 'w')
result2 = open('result2.txt', 'w')
result3 = open('result3.txt', 'w')
result4 = open('result4.txt', 'w')
result5 = open('result5.txt', 'w')
for k, v in d1.items():
if k in d2:
v2 = d2
if v == v2:
result1.write('{} equal{}\n'.format(k, v))
elif v > v2:
result2.write('{} 1bigger2{}\n'.format(k, v))
else:
result3.write('{} 2bigger1{}\n'.format(k, v2))
d2.pop(k)
else:
result4.write('{} onlyinfile1{}\n'.format(k, v))
for k, v in d2.items():
result5.write('{} onlyinfile2{}\n'.format(k, v))
result1.close()
result2.close()
result3.close()
result4.close()
result5.close() 本帖最后由 这个冬天不冷 于 2014-12-02 15:28 编辑
<?php
error_reporting(0);
ini_set('memory_limit','2048M'); //修改php支持的最大内存
$fp1 = fopen("file1.txt", "r") or die('no file1');
$fp2 = fopen("file2.txt", "r") or die('no file2');
$contents1 = fread($fp1, filesize('file1.txt'));
$contents2 = fread($fp2, filesize('file2.txt'));
$arr1 =explode("\n", $contents1);
$arr2 =explode("\n", $contents2);
$t1 = array();
$t2 = array();
foreach ($arr1 as $key => $value) {
if(!empty($value))
$a_tmp = explode(" ", $value);
$t1[$a_tmp] = end($a_tmp);
}
foreach ($arr2 as $key => $value) {
if(!empty($value))
$a_tmp = explode(" ", $value);
$t2[$a_tmp] = end($a_tmp);
}
//统计结果
$xiangdeng = array();
$cha1 = array();
$cha2 = array();
$no1 = array();
$no2 = array();
foreach ($t1 as $key => $value) {
if($t1[$key] > $t2[$key] && isset($t2[$key])) $cha1 = "$key file1biggerfile2 $t1[$key]";
if($t1[$key] < $t2[$key] && isset($t1[$key])) $cha2 = "$key file2biggerfile1 $t2[$key]";
if($t1[$key] == $t2[$key]) $xiangdeng = "$key equal$t2[$key]";
}
//求只在文件2 中出现的
foreach ($t2 as $key => $value) {
if(!isset($t1[$key])) $no2 = "$key onlyinfile2 $t2[$key]";
}
foreach ($t1 as $key => $value) {
if(!isset($t2[$key])) $no1 = "$key onlyinfile1 $t1[$key]";
}
$str = implode("\r\n", $xiangdeng);
file_put_contents("result1", $str);
$str = implode("\r\n", $cha1);
file_put_contents("result2", $str);
$str = implode("\r\n", $cha2);
file_put_contents("result3", $str);
$str = implode("\r\n", $no1);
file_put_contents("result4", $str);
$str = implode("\r\n", $no2);
file_put_contents("result5", $str);
echo '<pre>';
print_r($xiangdeng);
print_r($cha1);
print_r($cha2);
print_r($no1);
print_r($no2);
fclose($fp1);
fclose($fp2);Array
(
=> 1221 equal2453
)
Array
(
=> 1223 file1biggerfile2 5687
)
Array
(
=> 1245 file2biggerfile1 5621
)
Array
(
=> 1243 onlyinfile1 7683
)
Array
(
=> 1265 onlyinfile2 8000
=> 1287 onlyinfile2 4321
)文件都不贴了，文件就是根据上面的数组运行结果 ，写入的
#!/usr/bin/env python
# -*- coding:utf-8 -*-
f1 = open('result1', 'w+')
f2 = open('result2', 'w+')
f3 = open('result3', 'w+')
f4 = open('result4', 'w+')
f5 = open('result5', 'w+')
dict1 = {}
dict2 = {}
def dict(file):
if file == 'file1':
file = open(file,'r')
for line in file.readlines():
line = line.strip('\n')
list = line.split('')
dict1] = list
if file == 'file2':
file = open(file,'r')
for line in file.readlines():
line = line.strip('\n')
list = line.split(' ')
dict2] = list
dict('file1')
dict('file2')
for k in dict1:
try:
if int(dict1) == int(dict2):
f1.write('%s equal %s\n' % (k,dict1))
elif int(dict1) < int(dict2):
v = int(dict2) - int(dict1)
f3.write('%s file2biggerfile1 %s\n' % (k,v))
elif int(dict1) > int(dict2):
v = int(dict1) - int(dict2)
f2.write('%s file1biggerfile2 %s\n' % (k,v))
except:
f4.write('%s onlyfile1 %s\n' % (k,dict1))
for k in dict2:
try:
if int(dict1) == int(dict2):
pass
if int(dict1) < int(dict2):
pass
if int(dict1) > int(dict2):
pass
except:
f5.write('%s onlyfile2 %s\n' % (k,dict2))