Question

假设有这么个需求，希望能找出两个不同的给定目录下相同的文件名。该怎么实现呢？一个可行的方法是列出两个目录下所有的文件名，然后逐一比较找出相同的项。实现代码如下：

import os
def ListFilename(dirname,filesuffix):
     filelist = []
     os.chdir(dirname)
     for files in os.listdir("."):
        if files.endswith(filesuffix):
           filelist.append(files)   #
找出满足条件的后缀条件的文件加入到列表中
     return filelist
filelistA = ListFilename("C:\\",".log")
filelistB = ListFilename("C:\\temp\\",".log")
filelistA.sort()                #
对列表进行排序
filelistB.sort()
samefilelist=[]                 #
用来存放相同文件的列表
for a in filelistA:               #
对列表进行循环比较
     for b in filelistB:
        if a == b:
             samefilelist.append(a)
print samefilelist

示例程序选择的数据结构为列表，首先对列表进行排序，然后进行逐项比较，其算法的复杂度为O（m×n），其中m、n分别为两个列表的长度。那么请读者思考一下，有没有更好的选择呢？我们来了解一下集合（set）的基本知识点。Python中集合是通过Hash算法实现的无序不重复的元素集。创建集合通过set()方法来实现。

>>> set("hello")
set(['h', 'e', 'l', 'o'])
>>> a = [1,2,"34",(5,6)]
>>> set(a)                       #
方便地将列表转换为set
set([(5, 6), 1, 2, '34'])

集合中常见的操作以及对应的时间复杂度如表8-5所示。

表8-5　集合常见操作及时间复杂度

对表8-5时间复杂度这列仔细分析会发现，集合操作的复杂度基本为O(n)，最差的情况下时间复杂度才为O(n^2）。回过头来看本节开头的例子，你是不是会有这么一个想法：如果能够将对列表的操作改为对集合的操作，性能将会明显提高？那么事实是不是如我们所料呢？我们先来基于一些基本操作测试一下这两种数据结构在性能上的表现。

1）对list求相同的元素，set求并集。当元素规模为100的时候测试结果显示，list的耗时大约为set操作的15倍。

Python -m timeit -n 1000 "[x for x in xrange(100) if x in xrange(60, 100)]"
1000 loops, best of 3: 133 usec per loop
Python -m timeit -n 1000 "set(xrange(100)).intersection(xrange(60, 100))"
1000 loops, best of 3: 8.99 usec per loop

当元素规模为1000时的测试结果显示，list耗时大约为set操作的144倍，如表8-6所示。

Python -m timeit -n 1000 "[x for x in xrange(1000) if x in xrange(600, 1000)]"
1000 loops, best of 3: 9.93 msec per loop
Python -m timeit -n 1000 "set(xrange(1000)).intersection(xrange(600, 1000))"
1000 loops, best of 3: 68.9 usec per loop

表8-6　list和set在求相同元素操作时的性能比较

1）向list和set中添加元素，当元素规模为100的时候，list的耗时为set的9倍。

Python -m timeit -s  "testset=set()" -s  "for x in xrange(100): testset.add(x)"
  "for x in xrange(100): x in testset"
100000 loops, best of 3: 11.5 usec per loop
Python -m timeit -s  "tmp = list()" -s "for x in xrange(100): tmp.append(x)"  
  "for x in xrange(100): x in tmp"
10000 loops, best of 3: 104 usec per loop

当元素规模为1000的时候，list的耗时约为set的89倍，如表8-7所示。

表8-7　往list和set中添加元素的情况下性能比较

Python -m timeit -s  "testset=set()" -s  "for x in xrange(1000): testset.
  add(x)"  "for x in xrange(1000): x in testset"
10000 loops, best of 3: 105 usec per loop
Python -m timeit -s  "tmp = list()" -s "for x in xrange(1000): tmp.append(x)"
  "for x in xrange(1000): x in tmp"
100 loops, best of 3: 9.41 msec per loop

从表8-7所示的测试数据中可以看出，set在某些操作上明显比list更高效，实际上set的union、intersection、difference等操作要比list的迭代要快。因此如果涉及求list交集、并集或者差等问题可以转换为set来操作。因此本节最初的例子将list转换为set再求交集会更为简洁高效，可修改为print set(filelistA)&set(filelist)。修改后测试结果表明，即使规模在10左右，set的效率仍然比list高了将近3倍（读者可以自行验证）。