status

草稿

ZoomQuiet,xyb

完成度~40%

Contents

  1. 文本处理实感
    1. 读取google搜索信息
      1. search.py
    2. 从 whois 信息中提取网段信息
      1. netsegm.py
    3. 找出两个文件中不同部分
      1. 大文件排序
      2. 大文件比较
      3. notin.py
      4. sortfile.py
  2. 小结
    1. 练习

1. 文本处理实感

1.1. 读取google搜索信息

读取google搜索信息

互联网已经成为我们生活中必不可少的一部分，它提供的海量资料是我们在日常工作经常会接触和使用的。这里简单介绍有如何处理html格式数据。 

   1 import urllib2
   2 from urllib import quote
   3 
   4 def search(keyword):
   5     request = urllib2.Request('http://www.google.com/custom?q=' + quote(keyword))
   6     request.add_header('User-Agent', 'Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.6) Gecko/20061201 Firefox/2.0.0.6 (Ubuntu-feisty)')
   7     opener = urllib2.build_opener()
   8     html = opener.open(request).read()
   9 
  10     html = html.replace('<div class=g', '\n<div class=g')
  11     html = html.replace('</h2>', '</h2>\n')
  12     results = [s for s in html.split('\n') if s.startswith('<div class=g')]
  13     for s in results:
  14         s = s[s.find('href="'):]
  15         s = s.replace('href="', '')
  16         link = s[:s.find('"')]
  17         t = s[s.find('>')+1:]
  18         t = t[:t.find('</a>')]
  19         t = t.replace('<b>', '')
  20         t = t.replace('</b>', '')
  21         title = t[t.rfind('>')+1:]
  22         yield link, title

程序首先从google上按照指定的关键字检索，并读取搜索结果，存入html变量。通过认真观察google的结果页面，可以找到一个规律，每个结果项都在一个class=g的div中；找到'<div class=g'，也就找到了一个搜索结果的起始位置。不过糟糕的是，所有搜索结果都挤在一行文本中，所以我们先找到'<div class=g'，在前面增加换行符，把它分成多行。每个搜索结果包括标题、链接，还有部分摘要。这个程序里，我们只取每个检索结果的标题和链接，所以在标题结束部分'</h2>'的后面，也增加一个换行符，把我们关心的这部分代码单独放到一行里。这时，每个检索结果就变成了这个样子： 

<div class=g><link rel="prefetch" href="http://www.python.org/"><h2 class=r><a href="http://www.python.org/" target=_blank class=l onmousedown="return clk(0,'','','cres','1','')"><b>Python</b> Programming Language -- Official Website</a></h2>

准备好数据以后，按照换行符把html分割成字符串的列表，并且过滤出是以'<div class=g'开始的字符串，存入results列表。下面的处理就是我们不需要的字符去掉，并切分离出网址链接和标题。首先查找链接：s.find('href="')，并把它后面的字符串保留下来，然后就可以把网址分离出来，存入link变量。与此类似，我们可以得到标题部分的字符串。 

if __name__ == '__main__':
    import sys
    for link, title in search(sys.argv[1]):
        print link, title

程序的运行，传入的第一个参数作为检索的关键字。

大家看起来上面的代码，有没有觉得即繁琐，又不容易一眼看懂？也就是说，这种方法虽然简单，但可读性并不好。下面我介绍一种更简洁、同时也很易读懂的方法：使用正则表达式。

正则表达式是一种匹配及处理特定字符串的专门格式。如果用正则表达式来编写同样的功能，上面的函数就可以写成： 

RE_LINK = r'<div class=g[^>]*>(?:<link [^>]*>)?<h2 class=r><a href="([^"]+)"[^>]*>(.+?)</a></h2>'

def search(keyword):
    request = urllib2.Request('http://www.google.com/custom?q=' + quote(keyword))
    request.add_header('User-Agent', 'Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.6) Gecko/20061201 Firefox/2.0.0.6 (Ubuntu-feisty)')
    opener = urllib2.build_opener()
    html = opener.open(request).read()

    for link, title in re.findall(RE_LINK, html):
        title = re.sub('</?b>', '', title)
        yield link, title

RE_LINK是关键的正则表达式，它的含义为：

group匹配是我们从大量信息中挑出自己需要的数据的一种方法，也是用来组织复杂的、嵌套的正则表达式的有力工具。在这个正则表达式中，共出现三次group匹配，第一个(?:...)，是因为有多个表达式要绑定成一组，所以要用括号()把它们绑在一起之后，才能用后面带的问号?来修饰它，告知正则表达式处理引擎，它们或者一起出现一次，或者一起都不出现。由于这个匹配并不是我们需要的数据，不需要他出现在最终的结果中，所以我们用(?:...)类型，这样就可以把它从结果中忽略掉了。第二个和第三个(...)，是我们要命中匹配的链接地址和标题，这是两个普通类型的gorup匹配。

通过re.findall，就可以把文本中所有符合规则的信息一起全部提取出来。然后再稍作处理，用re.sub过滤掉标题中可能存在的'<b>'或者'</b>'，就得到最终的检索结果了。

1.1.1. search.py

   1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 
   4 import urllib2
   5 from urllib import quote
   6 import re
   7 
   8 RE_LINK = r'<div class=g[^>]*>(?:<link [^>]*>)?<h2 class=r><a href="([^"]+)"[^>]*>(.+?)</a></h2>'
   9 
  10 def search(keyword):
  11     request = urllib2.Request('http://www.google.com/custom?q=' + quote(keyword))
  12     request.add_header('User-Agent', 'Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.6) Gecko/20061201 Firefox/2.0.0.6 (Ubuntu-feisty)')
  13     opener = urllib2.build_opener()
  14     html = opener.open(request).read()
  15 
  16     for link, title in re.findall(RE_LINK, html):
  17         title = re.sub('</?b>', '', title)
  18         yield link, title
  19 
  20 def search2(keyword):
  21     request = urllib2.Request('http://www.google.com/custom?q=' + quote(keyword))
  22     request.add_header('User-Agent', 'Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.6) Gecko/20061201 Firefox/2.0.0.6 (Ubuntu-feisty)')
  23     opener = urllib2.build_opener()
  24     html = opener.open(request).read()
  25 
  26     html = html.replace('<div class=g', '\n<div class=g')
  27     html = html.replace('</h2>', '</h2>\n')
  28     results = [s for s in html.split('\n') if s.startswith('<div class=g')]
  29     for s in results:
  30         s = s[s.find('href="'):]
  31         s = s.replace('href="', '')
  32         link = s[:s.find('"')]
  33         t = s[s.find('>')+1:]
  34         t = t[:t.find('</a>')]
  35         t = t.replace('<b>', '')
  36         t = t.replace('</b>', '')
  37         title = t[t.rfind('>')+1:]
  38         yield link, title
  39 
  40 if __name__ == '__main__':
  41     import sys
  42     for link, title in search(sys.argv[1]):
  43         print link, title

1.2. 从 whois 信息中提取网段信息

这段程序用于从 whois 信息中提取网段信息，并保存为 nc 格式的 tiny dns 配置文件。它可以针对来访者网段，为一个域名分配不同的ip。

我们先来看一段文本： 

inetnum:      202.96.63.97 - 202.96.63.127
netname:      CAIMARNET

domain:       123.93.203.in-addr.arpa
descr:        Reverse zone for 203.93.123.0/24

domain:       140.4.221.in-addr.arpa
descr:        reverse delegation for 221.4.140/24

domain:       250.5.221.in-addr.arpa
descr:        China Network Communications Group Co. ChongQing

这是一段whois3程序生成的输出例子，其中保存的是中国网通使用的的部分IP网段信息。这里编写的这段程序将对他们进行处理，得到我们需要的结果。

whois3程序可以从

下载并编译生成。用

./whois3 -h whois.apnic.net -l -i mb MAINT-CNCGROUP > cnc.txt
./whois3 -h whois.apnic.net -l -i ml MAINT-CNCGROUP >> cnc.txt
./whois3 -h whois.apnic.net -l -i mu MAINT-CNCGROUP >> cnc.txt
./whois3 -h whois.apnic.net -l -i mb MAINT-CHINANET > chinanet.txt
./whois3 -h whois.apnic.net -l -i mb MAINT-CN-CRTC > crtc.txt

可以获得类似上面的结果文件。 

_sample_whois = """
inetnum:      202.96.63.97 - 202.96.63.127
netname:      CAIMARNET

domain:       123.93.203.in-addr.arpa
descr:        Reverse zone for 203.93.123.0/24

domain:       140.4.221.in-addr.arpa
descr:        reverse delegation for 221.4.140/24

domain:       250.5.221.in-addr.arpa
descr:        China Network Communications Group Co. ChongQing
"""

从示例的数据中可以看出，数据的格式一共有4类，read_chunk从输入中分析出这四类格式，并读取相应的有用信息。 {{#!python def read_chunk(whois_file):

}}} 用三个双引号括起来的，叫做doc，是python语言中函数等对象的特殊属性。其中，可以保存对该代码的描述等信息。关于doc的更多信息，请参考...。这段代码里，也包含doctest的测试代码，它看起来就像是我们在python中执行函数时的输入和输出，供 doctest 读取和验证函数的行为是否符合要求。随时编写测试代码是一个非常好的习惯，一旦养成，会终生受益。采用doctest书写的测试用例，在文件中添加如下语句，就可以作为一个单独的程序来执行： 

if __name__ == '__main___':
    import doctest
    doctest.testmod()

如果文件的名字是 net_segm.py，则执行 python net_segm.py；如果没有看到任何输出，那么恭喜你，所有测试用例均已通过。作为UNIX哲学的一部分，像测试程序这样的一类程序的原则是：没有消息（输出）就是好消息。如果你想了解更多信息，可以输入：python net_segm.py -v，就可以看到每个测试用例执行的情况了。

这个函数首先以一个循环开始，从已经打开的文件中一行行读取数据，放到line变量中。从函数名可以知道，这个函数每次从文件中读取“一片”数据。只有一个换行符'\n'的空行就是标志，表示下面一个新的片断开始。根据四种数据格式的不同，程序判断逻辑为： 

如果第一行以 'inetnum:' 开始：
    （那么它是用两个ip标识一个网段）
    把第一行的后面数据从'-'字符切开，返回 'inetnum' 和两个ip
如果第一行以 'domain:' 开始：
   （那么是另外三种格式）
   先把第一行中倒排的arp地址保存到domain变量中
   读取第二行
   如果第二行以'descr:'开始：
       取 'descr:' 后面的数据中符合网段写法的部分
       如果取得网段：
           返回 'descr' 和网段
    其他所有情况返回 'domain' 和 domain 变量内容

请对照以上伪代码描述阅读 read_chunk 函数。获取类似 '192.168.1/24' 的网段字符的代码，使用了正则表达式模块 re，关于这个模块的更详细介绍，请参考...。在该函数中，返回数据使用 yield 而不是 return，它使我们不须从函数退出即可返回数据给调用者，这个特性给我们的编程带来了极大的便利。包含yield的函数被称作生成器（generator），它是python在函数式编程方面引入的一个重要特性。这些名词看起来很深奥，但yield使用起来其实很简单：用yield返回数据，用for来遍历从函数返回的数据，这样立刻可以用起来了。关于yield的更多信息，请参考...。

下面是read_chunk的调用者network_segment函数，从中可以看到一行'for chunk in read_chunk(whois):'即可使用read_chunk读取信息，使用起来很是方便。 

   1 def network_segment(whois_file):
   2     """read network segments from whois file
   3 
   4     >>> from StringIO import StringIO
   5     >>> list(network_segment(StringIO(_sample_whois)))
   6     ['202.96.63.0/24', '203.93.123.0/24', '221.4.140.0/24', '221.5.250.0/24']
   7     """
   8     if isinstance(whois_file, str):
   9         whois = file(whois_file)
  10     else:
  11         whois = whois_file
  12     for chunk in read_chunk(whois):
  13         name, segment = chunk
  14         if name=='descr':
  15             yield fix_segment(segment)
  16         elif name=='domain':
  17             inverted_network = segment
  18             yield reverse_segment(inverted_network)
  19         elif name=='inetnum':
  20             ip1, ip2 = segment
  21             yield max_mask24(get_network(ip1, ip2))
  22         else:
  23             yield chunk

这个函数根据每个片断的类型--变量"name"，分别使用不同的函数进行处理网段信息--变量segment，最后生成型如'202.96.63.0/24'这样我们需要的标准格式：后面的/24是这个网段的掩码的缩写方式，表示掩码中为1的比特共24位--这个例子是一个C类子网。函数开始部分是一段判断输入参数的代码，如果传入的参数是一个字符串，那么就把它作为一个文件名来打开；否则默认传入的是一个file类型的对象，从中读取每行数据。下面是不同类型数据的几个处理函数代码。 

   1 def fix_segment(segment):
   2     """
   3     >>> fix_segment('221.4.140/24')
   4     '221.4.140.0/24'
   5     >>> fix_segment('127/8')
   6     '127.0.0.0/8'
   7     """
   8     list_segm = segment.split('/')[0].split('.')
   9     if len(list_segm) < 4:
  10         segment = "%s%s/%s" % (
  11                 segment.split('/')[0],
  12                 '.0' * (4-len(list_segm)),
  13                 segment.split('/')[1],
  14                 )
  15     return segment

第一种格式，从descr中获得的信息，它的网段是缩写格式，例如： '221.4.140/24'。我们需要进行修复，扩展成 '221.4.140.0/24' 这样。首先，用split按照'/'字符把信息切开，前面的子网地址部分再用'.'字符切开；如果子网地址部分切开后少于4段，则说明这是个缩写格式，需要补全。把失掉的几段'.0'部分、缩写部分、'/'后的子网掩码部分统统合在一起，就可以得到完全格式的网段。 

   1 def reverse_segment(inverted_network):
   2     """
   3     >>> reverse_segment('250.5.221')
   4     '221.5.250.0/24'
   5     >>> reverse_segment('127')
   6     '127.0.0.0/8'
   7     """
   8     segment = inverted_network.split('.')[::-1]
   9     lr = len(segment)
  10     segment = '.'.join(segment) + '.0'*(4-lr) + '/' + str(lr*8)
  11     return segment

第二种格式，是arp的倒排的网段，例如：'250.5.221'。首先把地址用'.'字符切开，然后倒序排列。这里倒排是利用了列表类型的切片（slice）功能的第三个参数：如果该值为-1，则返回列表为倒序方式。这样修改并补全网段地址和子网掩码后，倒排格式就被修复为标准格式：'221.5.250.0/24'。 

   1 def get_network(ip1, ip2):
   2     """
   3     >>> get_network('218.106.0.0', '218.106.255.255')
   4     '218.106.0.0/16'
   5     >>> get_network('218.106.1.0', '218.106.1.255')
   6     '218.106.1.0/24'
   7     >>> get_network('219.158.32.0', '219.158.63.255')
   8     '219.158.32.0/19'
   9     >>> get_network('218.106.96.0', '218.106.99.255')
  10     '218.106.96.0/22'
  11     >>> get_network('218.106.208.0', '218.106.223.255')
  12     '218.106.208.0/20'
  13     >>> get_network('202.96.63.97', '202.96.63.127')
  14     '202.96.63.96/28'
  15     """
  16 
  17     ip1 = [int(i) for i in ip1.split('.')]
  18     ip2 = [int(i) for i in ip2.split('.')]
  19 
  20     def same_bit_length(i1, i2):
  21         return int(log((i2-i1+1), 2))
  22 
  23     same = 0
  24     for i1, i2 in zip(ip1, ip2):
  25         if i1==i2:
  26             same += 1
  27         else:
  28             break
  29 
  30     same_bit = same_bit_length(ip1[same], ip2[same])
  31     bit_mask_len = 2**same_bit
  32     mask_len = 8*same+(8-same_bit)
  33 
  34     ip = '.'.join([str(i) for i in ip1[:same]])
  35     ip += '.' + str(ip1[same]/(bit_mask_len)*(bit_mask_len))
  36     ip += '.0' * (4-same-1)
  37     return ip + '/' + str(mask_len)

第三种格式，数据中只有该网段的起始和结束ip地址。这段转换代码稍微复杂一些，它的逻辑是以二进制方式比较两个ip数字，找到它们相同部分的最大比特长度，从而得到标准写法。首先，把每个ip地址都以'.'字符切分成四个整形数字；然后从前往后挨个比较对应的数字，把相同数字的个数存入变量same。用内嵌的函数same_bit_length来计算第一对不相等的两个数字中，相同部分的比特个数，存入same_bit变量。这样，通过这两个数字，就可以得到这个网段地址的子网掩码mask_len。在函数的最后，变量ip中保存网段地址，和子网掩码连接在一起就是我们需要的标准格式了。 

   1 def max_mask24(segment):
   2     """
   3     >>> max_mask24('202.96.63.96/28')
   4     '202.96.63.0/24'
   5     """
   6     network, mask = segment.split('/')
   7     if int(mask) > 24:
   8         return '%s.0/24' % '.'.join(network.split('.')[:3])
   9     else:
  10         return segment

最后，我们希望网段最小的单位是C类。这个函数用来修正网段数据，如果不足一个C类的网段则补足。逻辑很简单，如果子网掩码小于24，则把网段第四部分置为零，并直接把掩码修改为24--也就是把它扩大到一个C类网段。

最后，下面的代码调用network_segment，从命令行输入的参数中读取一个文件，并把最终转换成的标准格式打印出来： 

if __name__ == '__main__':
    import sys
    whois_filename = sys.argv[1]
    for segm in network_segment(whois_filename):
        print segm

1.2.1. netsegm.py

   1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 
   4 from math import log
   5 import re
   6 import sys
   7 
   8 _sample_whois = """
   9 inetnum:      202.96.63.97 - 202.96.63.127
  10 netname:      CAIMARNET
  11 
  12 domain:       123.93.203.in-addr.arpa
  13 descr:        Reverse zone for 203.93.123.0/24
  14 
  15 domain:       140.4.221.in-addr.arpa
  16 descr:        reverse delegation for 221.4.140/24
  17 
  18 domain:       250.5.221.in-addr.arpa
  19 descr:        China Network Communications Group Co. ChongQing
  20 """
  21 
  22 def read_chunk(whois_file):
  23     """read one chunk from whois file once
  24 
  25     >>> from StringIO import StringIO
  26     >>> list(read_chunk(StringIO(_sample_whois)))
  27     [('inetnum', ['202.96.63.97', '202.96.63.127']), ('descr', '203.93.123.0/24'), ('descr', '221.4.140/24'), ('domain', '250.5.221')]
  28     """
  29     while True:
  30         line = whois_file.readline()
  31         if not line:
  32             break
  33         if line == '\n':
  34             line = whois_file.readline()
  35             if line.startswith('inetnum:'):
  36                 inetnum = line[len('inetnum:'):].strip()
  37                 inetnum = inetnum.replace(' ', '').split('-')
  38                 yield ('inetnum', inetnum)
  39             elif line.startswith('domain:'):
  40                 domain = line[len('domain:'):].strip()
  41                 domain = domain.replace('.in-addr.arpa', '')
  42                 line = whois_file.readline()
  43                 if line.startswith('descr:'):
  44                     descr = line[len('descr:'):].strip()
  45                     segm = re.findall('[0-9.]+/[0-9]+', descr)
  46                     if segm and len(segm) == 1:
  47                         segm = segm[0]
  48                         yield('descr', segm)
  49                         continue
  50                 yield ('domain', domain)
  51 
  52 def network_segment(whois_file):
  53     """read network segments from whois file
  54 
  55     >>> from StringIO import StringIO
  56     >>> list(network_segment(StringIO(_sample_whois)))
  57     ['202.96.63.0/24', '203.93.123.0/24', '221.4.140.0/24', '221.5.250.0/24']
  58     """
  59     if isinstance(whois_file, str):
  60         whois = file(whois_file)
  61     else:
  62         whois = whois_file
  63     for chunk in read_chunk(whois):
  64         name, segment = chunk
  65         if name=='descr':
  66             yield fix_segment(segment)
  67         elif name=='domain':
  68             yield reverse_segment(segment)
  69         elif name=='inetnum':
  70             ip1, ip2 = segment
  71             yield max_mask24(get_network(ip1, ip2))
  72         else:
  73             yield chunk
  74 
  75 def fix_segment(segment):
  76     """
  77     >>> fix_segment('221.4.140/24')
  78     '221.4.140.0/24'
  79     >>> fix_segment('127/8')
  80     '127.0.0.0/8'
  81     """
  82     list_segm = segment.split('/')[0].split('.')
  83     if len(list_segm) < 4:
  84         segment = "%s%s/%s" % (
  85                 segment.split('/')[0],
  86                 '.0' * (4-len(list_segm)),
  87                 segment.split('/')[1],
  88                 )
  89     return segment
  90 
  91 def reverse_segment(inverted_network):
  92     """
  93     >>> reverse_segment('250.5.221')
  94     '221.5.250.0/24'
  95     >>> reverse_segment('127')
  96     '127.0.0.0/8'
  97     """
  98     segment = inverted_network.split('.')[::-1]
  99     lr = len(segment)
 100     segment = '.'.join(segment) + '.0'*(4-lr) + '/' + str(lr*8)
 101     return segment
 102 
 103 def get_network(ip1, ip2):
 104     """
 105     >>> get_network('218.106.0.0', '218.106.255.255')
 106     '218.106.0.0/16'
 107     >>> get_network('218.106.1.0', '218.106.1.255')
 108     '218.106.1.0/24'
 109     >>> get_network('219.158.32.0', '219.158.63.255')
 110     '219.158.32.0/19'
 111     >>> get_network('218.106.96.0', '218.106.99.255')
 112     '218.106.96.0/22'
 113     >>> get_network('218.106.208.0', '218.106.223.255')
 114     '218.106.208.0/20'
 115     >>> get_network('202.96.63.97', '202.96.63.127')
 116     '202.96.63.96/28'
 117     """
 118 
 119     ip1 = [int(i) for i in ip1.split('.')]
 120     ip2 = [int(i) for i in ip2.split('.')]
 121 
 122     def same_bit_length(i1, i2):
 123         return int(log((i2-i1+1), 2))
 124 
 125     same = 0
 126     for i1, i2 in zip(ip1, ip2):
 127         if i1==i2:
 128             same += 1
 129         else:
 130             break
 131 
 132     same_bit = same_bit_length(ip1[same], ip2[same])
 133     bit_mask_len = 2**same_bit
 134     mask_len = 8*same+(8-same_bit)
 135 
 136     ip = '.'.join([str(i) for i in ip1[:same]])
 137     ip += '.' + str(ip1[same]/(bit_mask_len)*(bit_mask_len))
 138     ip += '.0' * (4-same-1)
 139     return ip + '/' + str(mask_len)
 140 
 141 def max_mask24(segment):
 142     """
 143     >>> max_mask24('202.96.63.96/28')
 144     '202.96.63.0/24'
 145     """
 146     network, mask = segment.split('/')
 147     if int(mask) > 24:
 148         return '%s.0/24' % '.'.join(network.split('.')[:3])
 149     else:
 150         return segment
 151 
 152 def test():
 153     import doctest
 154     doctest.testmod()
 155 
 156 if __name__ == '__main__':
 157     import sys
 158     if sys.argv[1] == 'test':
 159         test()
 160         sys.exit()
 161     whois_filename = sys.argv[1]
 162     for segm in network_segment(whois_filename):
 163         print segm

1.3. 找出两个文件中不同部分

文件A和文件B是两组人名单，每行是一个人的名字。这里我们要完成一个任务，把在文件A中出现，但没有在文件B中的人都找出来。

首先读取文件内容：

>>> a = file('a.txt').readlines()
>>> b = file('b.txt').readlines()
>>> a
['a\n', 'b\n', 'd\n', 'f\n', 'g\n', 'h\n']
>>> b
['b\n', 'c\n', 'e\n', 'f\n']

然后是比较过程：

>>> for i in a:
...     if i not in b:
...         print i.rstrip('\n')
... 
a
d
g
h
>>>

甚至连写程序都不用，我们就可以在python命令行里直接快速完成。file.readlines可以把文件中所有内容一次读取出来，放到内存中来处理。只有小文件才可以这样用，如果文件过大，内存就会被文件内容吃光，这样程序执行效率返回会下降。然后对文件a中的每一行内容，检查是否在文件b中存在，不存在就直接打印到屏幕上。

如果两个文件的数据量多起来的时候，用list的in操作来判断a里的一个名字在b里是否存在，效率就太差了；这时可以引进一个数据结构：集合(set)。读取文件内容的部分就变成了这样： 

>>> a = set(file('a'))
>>> b = set(file('b'))
>>> a
set(['d\n', 'a\n', 'b\n', 'h\n', 'f\n', 'g\n'])
>>> b
set(['c\n', 'f\n', 'b\n', 'e\n'])

这样，比较的部分还是可以继续使用in操作符。读取文件的部分省略了readlines函数，set会自动从文件中读取所有数据。

数据多了，输出也可能会变得多起来，直接打印到屏幕已经不够用了，需要保存到文件中： 

>>> f = file('output.txt', 'w')
>>> for i in a:
...     if i not in b:
...         print >>> f, i.rstrip('\n')
>>>

但是，当文件内容大到超出内存的大小时，上面的方法就无法使用了。这时怎么办呢？我们可以先排序，再比较。一旦两个文件被以相同的顺序排列好了，我们就可以“顺流而下”，逐行比较，而不用一次全部装载到内存来了。

1.3.1. 大文件排序

一般情况下，我们可以使用系统的sort命令对文件进行排序，但使用python排序文件也是很方便的：

>>> file('sorted.txt', 'w').writelines(sorted(file('filename.txt')))

这一行命令就可以按照升序对文件排序，并保存在一个新文件中。

但对于超大文件，受限于内存的大小，不论是系统提供的sort命令，还是上面使用的python函数，处理起来效率都非常差，甚至因为需要的内存超出系统内存大小无法完成任务。不过不用担心，我们还是有办法来解决的。通过化整为零，把大文件的排序降低难度为多个小文件的排序，然后通过合并算法就可把组合成一个完整的结果了。只要每个小文件足够放到内存中，再加上合并算法对内存的占用也很少，如此一来，大文件处理遇到的内存限制也就迎刃而解。 

   1 LINES = 10000
   2 def split_sort(filename):
   3     f = file(filename)
   4     num = 0
   5     while True:
   6         lines = []
   7         for i in range(LINES):
   8             line = f.readline()
   9             if not line:
  10                 break
  11             lines.append(line)
  12         if not lines:
  13             break
  14         lines.sort()
  15         num += 1
  16         file(filename + '.%d'%num, 'w').writelines(lines)
  17     return num

这段代码把文件分割成多个排好序的小文件。返回值是文件的个数。首先打开文件，在while循环读取每行数据，直到再没有任何数据，退出循环。在循环中，每读取10000行，就把它们排序，并写入到一个新的文件中，文件名是原名后缀文件序号数字。 

   1 from heapq import heappop, heappush
   2 
   3 def merge_sorted(filename, num):
   4     lines = []
   5     for i in range(num):
   6         f = file(filename + '.%d'%(i+1))
   7         line = f.readline()
   8         if line:
   9             heappush(lines, (line, f))
  10     while lines:
  11         line, f = heappop(lines)
  12         yield line
  13         line = f.readline()
  14         if line:
  15             heappush(lines, (line, f))

这段代码是把多个排好序的小文件合并成一个文件。首先，从每个文件中读取第一行，把数据和打开的文件一起存入列表lines。while循环把列表当成一个自动排序的队列，每次从里面取第一个元素（也是最小的一个元素），然后返回该值并从这个数据所在的文件中取下一个数据，重新放入队列中。这个过程保证了每次得到的都是当前几个文件中数据里最小的一个，当遍历完所有的已排序文件，这个函数返回的也就是所有数据按照顺序合后的结果。

这个过程使用到了一个特殊的模块：heapq。它是一个把列表当做特殊的队列使用，用heappush把新元素存入队列，用heappop从队列中取出第一个元素；通过这种方法操作，它就可以自动保持队列中的最小值始终排在队列的最前面，这样我们逐个取出的数据就可以保证是顺序排序的。实际上，把heappush的代码替换为： 

lines.append((line, f))
lines.sort()
把heappop替换为：
lines.pop(0)

也可以完成同样的功能，但列表排序的执行效率很一般，这在我们处理大数据量时会多花很多不必要的时间，所以我们采用heapq来优化代码、提高执行效率、节省运行时间。 

if __name__ == '__main__':
    import sys
    num = split_sort(sys.argv[1])
    output = file(sys.argv[2])
    for line in merge_sorted(sys.argv[1], num):
        outputu.write(line)

这段是把第一个参数的文件进行排序，并把结果保存到第二个参数的文件中。

上面的代码中还缺少一部分功能。看出来了吗？排序过程中生成了许多临时的小文件，但在程序里并没有及时删除。如果读者您有兴趣，不妨试试亲自修改一下这段程序，给它增加删除临时文件的功能。

1.3.2. 大文件比较

   1 import sys
   2 
   3 def notin(sorted_file_a, sorted_file_b):
   4     r"""compare two file
   5 
   6     >>> from StringIO import StringIO
   7     >>>
   8     >>> a = '\n'.join('abdfgh')
   9     >>> b = '\n'.join('bcef')
  10     >>> list(notin(StringIO(a), StringIO(b)))
  11     ['a', 'd', 'g', 'h']
  12     """
  13     fa = sorted_file_a
  14     fb = sorted_file_b
  15     fa = isinstance(fa, str) and open(fa) or fa
  16     fb = isinstance(fb, str) and open(fb) or fb
  17 
  18     sa = fa.readline()
  19     sb = fb.readline()
  20     while True:
  21         if not sa: break
  22         if not sb: break
  23         sa = sa.rstrip('\n')
  24         sb = sb.rstrip('\n')
  25 
  26         compare = cmp(sa, sb)
  27         if (compare < 0):
  28             # FILE A only
  29             yield sa
  30             sa = fa.readline()
  31         elif (compare == 0):
  32             # both
  33             sa = fa.readline()
  34             sb = fb.readline()
  35         else:
  36             # FILE B only
  37             sb = fb.readline()
  38 
  39     # print more FILEA
  40     if sa:
  41         yield sa.rstrip('\n')
  42         for sa in fa:
  43             yield sa

把大文件排好顺序以后，我们就可以按照顺序来逐行读取两个文件；这样，只需顺序读取一次，我们就可以找出A文件中哪些行在B文件中从来没有出现过。在函数的开头，打开两个文件，并读取第一行数据。在下面的while循环中，如果任何一个文件中没有更多数据了，就退出循环。然后用python自带的cmp函数比较两个文件中的当前数据。根据cmp的返回值，如果A的数据小于B的数据，则说明这行数据只在A中存在，它就是我们的目标，把它返回，并读取A中的下一个数据。如果A和B的数据相等，那么这个数据恰好在两个文件中都存在，那么跳过它们，并从A和B两个文件中读取下一个数据，用于下一轮比较。如果A的数据大于B，那么说明这个数据是只有B中存在的，则忽略它，并从B中读取下一个数据。经过这样的循环和比较，大部分的数据就被筛选了出来；但有可能当B中已经读完数据了，而A中还有多余的数据，那么我们就可以肯定，剩下的肯定全部都是A中所特有的，那么就需要把它们依次读取，全部返回。 

if __name__ == '__main__':
    notin(sys.argv[1], sys.argv[2])

1.3.3. notin.py

   1 #!/usr/bin/env python
   2 # -*- coding: GB2312 -*-
   3 
   4 """Print the lines in FILEA and not in FILEB.
   5 
   6 notin.py FILEA FILEB
   7 FILEA and FILEB must be sorted
   8 """
   9 
  10 __revision__ = '1.0'
  11 
  12 import sys
  13 
  14 def notin(sorted_file_a, sorted_file_b):
  15     r"""compare two file
  16 
  17     >>> from StringIO import StringIO
  18     >>>
  19     >>> a = '\n'.join('abdfgh')
  20     >>> b = '\n'.join('bcef')
  21     >>> list(notin(StringIO(a), StringIO(b)))
  22     ['a', 'd', 'g', 'h']
  23     """
  24     fa = sorted_file_a
  25     fb = sorted_file_b
  26     fa = isinstance(fa, str) and open(fa) or fa
  27     fb = isinstance(fb, str) and open(fb) or fb
  28 
  29     sa = fa.readline()
  30     sb = fb.readline()
  31     while True:
  32         if not sa: break
  33         if not sb: break
  34         sa = sa.rstrip('\n')
  35         sb = sb.rstrip('\n')
  36 
  37         compare = cmp(sa, sb)
  38         if (compare < 0):
  39             # FILE A only
  40             yield sa
  41             sa = fa.readline()
  42         elif (compare == 0):
  43             # both
  44             sa = fa.readline()
  45             sb = fb.readline()
  46         else:
  47             # FILE B only
  48             sb = fb.readline()
  49 
  50     # print more FILEA
  51     if sa:
  52         yield sa.rstrip('\n')
  53         for sa in fa:
  54             yield sa
  55 
  56 def test():
  57     import doctest
  58     doctest.testmod()
  59 
  60 if __name__ == '__main__':
  61     import sys
  62     if sys.argv[1] == 'test':
  63         test()
  64         sys.exit()
  65     for i in notin(sys.argv[1], sys.argv[2]):
  66         print i

1.3.4. sortfile.py

   1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 
   4 from heapq import heappop, heappush
   5 LINES = 2
   6 
   7 def split_sort(filename):
   8     f = file(filename)
   9     num = 0
  10     while True:
  11         lines = []
  12         for i in range(LINES):
  13             line = f.readline()
  14             if not line:
  15                 break
  16             lines.append(line)
  17         if not lines:
  18             break
  19         lines.sort()
  20         num += 1
  21         file(filename + '.%d'%num, 'w').writelines(lines)
  22     return num
  23 
  24 def merge_sorted(filename, num):
  25     lines = []
  26     for i in range(num):
  27         f = file(filename + '.%d'%(i+1))
  28         line = f.readline()
  29         if line:
  30             heappush(lines, (line, f))
  31     while lines:
  32         line, f = heappop(lines)
  33         yield line
  34         line = f.readline()
  35         if line:
  36             heappush(lines, (line, f))
  37 
  38 if __name__ == '__main__':
  39     import sys
  40     num = split_sort(sys.argv[1])
  41     for line in merge_sorted(sys.argv[1], num):
  42         sys.stdout.write(line)

2. 小结

2.1. 练习

::-- ZoomQuiet [2007-09-01 04:13:30]

ObpLovelyPython/LpyAttach-CookBook (last edited 2009-12-25 07:12:33 by localhost)