文本计算比较

KoomIer

开奖了，开奖了 ， 恭喜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行左右

1. 
   
2. $cat file1
   
3. 1221  2453
   
4. 1223  5687
   
5. 1243  7683
   
6. 1245  1000
   
7. 
   
8. $cat file2
   
9. 1221 2453
   
10. 1223 2000
    
11. 1245 5612
    
12. 1265 8000
    
13. 1287 4321
    

复制代码

期望输出结果: 第一列为索引， 第二列为值， 当第一列索引号相同的时候做差， 当找不到的时候放到另一个文件
生成五个文件， 一个相等的，一个正差，一个逆差， 两个only出现在一个文件中的

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

复制代码

KoomIer

我sever上没有py3

回复 20# ssfjhh


   

ssfjhh

1. python3 balabala.py

复制代码

这样不行么？

KoomIer

这里我只能抱歉，而且我是新手，又没能力改3为2
如果有时间，你帮我改下

而且关键是算法思路

回复 17# ssfjhh


   

KoomIer

对
回复 16# jcdiy0601


   

ssfjhh

楼主，挺多参与者用的py3，也都很想看到结果如何，但是没有数据，你一句py3，no result，打击我们py3用户参与的积极性啊。

jcdiy0601

回复 15# KoomIer

是说参与的都有奖吗
   

KoomIer

已开奖

回复 1# KoomIer


   

Hadron74

这两个文件如果键值是排序好的，是一个归并排序的问题；如果没有排序好，应先排序，再归并，算法复杂度log(n)+log(m)+m+n.
用集合的运算时间复杂度太大了。

这里给出一个用Python的代码：

1. __author__ = 'luhongc'
   
2. # -*- coding: utf_8 -*-
   
3. 
   
4. 
   
5. file1 = """1221  2453
   
6. 1223  5687
   
7. 1243  7683
   
8. 1245  1000
   
9. """
   
10. 
    
11. file2 ="""1221 2453
    
12. 1223 2000
    
13. 1245 5612
    
14. 1265 8000
    
15. 1287 4321
    
16. """
    
17. 
    
18. #file1 = open("file1").read()  # 对外部文件的输入
    
19. #file2 = open("file2").read()
    
20. 
    
21. 
    
22. INfile1 = file1.strip().split('\n')
    
23. INfile2 = file2.strip().split('\n')
    
24. 
    
25. Key1 = [ [ int(i) for i in kv.split()]  for kv in INfile1]
    
26. Key2 = [ [ int(i) for i in kv.split()]   for kv in INfile2]
    
27. 
    
28. Key1.sort(key=lambda x: x[0])  # 队列按键排序，如果排序好文件，可以省略这步
    
29. Key2.sort(key=lambda x: x[0])
    
30. 
    
31. class DATA:
    
32.     def __init__(self,Key,KeyOther,fonly,othername):
    
33.         self.Key = Key                 # 本队列
    
34.         self.KeyOther = KeyOther       # 另一个队列
    
35.         self.fonly = fonly             # 另一个队列的输出文件句柄
    
36.         self.othername = othername     # 另一个队列的名字
    
37.         self.head = 0                  # 对列
    
38. 
    
39.     def get(self,other_header):
    
40.         try:
    
41.             t,v = self.Key[self.head]
    
42.             self.has_data = True   # 是否能 得到 一个 数据
    
43.             self.t = t             # 键
    
44.             self.v = v             # 值
    
45.         except:
    
46.             # 如果一个 序列 为空，则把另一个序列的 值 输出到 指定 文件 中
    
47.             for key,value in self.KeyOther[other_header:]:
    
48.                 self.fonly.write("%d onlyin%s %d\n" % (key,self.othername,value))
    
49.             self.has_data = False  # 返回 序列为空
    
50.             self.t = "NA"
    
51.             self.v = "NA"
    
52.         return self
    
53.     def pop(self):
    
54.         self.head += 1            # 弹出本队列最小元素
    
55.         return
    
56. 
    
57. with open("result1","w") as R1 , \
    
58.      open("result2","w") as R2 , \
    
59.      open("result3","w") as R3 , \
    
60.      open("result4","w") as R4 , \
    
61.      open("result5","w") as R5:
    
62. 
    
63. 
    
64.     D1 = DATA(Key1,Key2,R5,"file2")
    
65.     D2 = DATA(Key2,Key1,R4,"file1")
    
66.     D1.get(D2.head)
    
67.     D2.get(D1.head)
    
68. 
    
69.     while True:                      #归并算法，总选取两个队列中小的键进行处理
    
70.         if (D1.t > D2.t):
    
71.             R5.write("%d onlyin%s %d\n" % (D2.t,"file2",D2.v))
    
72.             D2.pop()
    
73.             D2.get(D1.head)
    
74.             if not D2.has_data:
    
75.                 break
    
76.         elif (D1.t < D2.t):
    
77.             R4.write("%d onlyin%s %d\n" % (D1.t,"file1",D1.v))
    
78.             D1.pop()
    
79.             D1.get(D2.head)
    
80.             if not D1.has_data:
    
81.                 break
    
82.         else:
    
83.             if ( D1.v > D2.v ):
    
84.                 R2.write("%d file1biggerfile2 %d\n" % (D1.t, D1.v-D2.v))
    
85.             elif (D1.v < D2.v):
    
86.                 R3.write("%d file2biggerfile1 %d\n" % (D1.t, D2.v-D1.v))
    
87.             else:
    
88.                 R1.write("%d equal %d\n" % (D1.t, D1.v ) )
    
89.             D1.pop()
    
90.             D2.pop()
    
91.             D1.get(D2.head)
    
92.             if not D1.has_data:
    
93.                 break
    
94.             D2.get(D1.head)
    
95.             if not D2.has_data:
    
96.                 break
    

复制代码

caoshanhu

我是来看看，学习的