第1章数据结构与算法

1-1 如何在列表, 字典, 集合中根据条件筛选数据

实际案例
1）过滤掉列表[3,9,-1,10,20,-2…]中的负数
2）筛出字典{'Lilei':79,'jim':88,'Lucy':92}中值高于90的项
3）筛出集合{77,89,32,20}中能被3整除的元素
通常的做法是用迭代，举例如下：

data=[1,5,-3,-2,6,0,9,100,67]
res=[]
for x in data:
    if x>=0:
        res.append(x)
print res

新的思路：
第一种方式，利用filter函数
filter

from random import randint
data2=[randint(-10,10) for _ in xrange(10)]
print data2
f=filter(lambda x:x>=0,data2)
print f

第二种方式，用列表解析

b=[x for x in data2 if x>=0]
print b

以上两种方式，列表解析更快一些。
下面可以这样测试

timeit filter(lambda x:x>=0,data2)
print c

2)EX:某班有20个人，得到一个字典

from random import randint
d={x:randint(60,100) for x in xrange(1,21)}
print d

采用字典解析

dd={k:v for k,v in d.iteritems() if v>90}
print dd

1-2 如何为元组中的每个元素命名, 提高程序可读性

如何为元组中的每个元素命名，提高程序可读性？
方案1：定义类似与其他语言的枚举类型，也就是定义一系列数值常量。

NAME = 0
AGE = 1
SEX = 2
EMAIL = 3
student = ('Jim',16,'male','jim8721@qq.com')
#name
print student[NAME]
#AGE
if student[AGE] >= 18:
    print True
else:
    print False

    #...
#SEX
if student[SEX] == 'male':
    #...
    pass

上面是是第一种方案，接下来看第二种方案
方案2：使用标准库中collections.namedtuple替代内置tuple

from collections import namedtuple
NAME,AGE,SEX,EMAIL = xrange(4)
Student = namedtuple('Student',['name','age','sex','email'])
s=Student('Jim',16,'male','jim8721@qq.com')
print s
s2 = Student('Jim',16,'male','jim8721@qq.com')

print s.name
print s.age
print s.sex

print isinstance(s,tuple)

补充

Python中存储系列数据，比较常见的数据类型有list，除此之外，还有tuple数据类型。相比与list，tuple中的元素不可修改，在映射中可以当键使用。tuple元组的item只能通过index访问，collections模块的namedtuple子类不仅可以使用item的index访问item，还可以通过item的name进行访问。可以将namedtuple理解为c中的struct结构，其首先将各个item命名，然后对每个item赋予数据。

1-3如何统计序列中元素的出现频度？

实际案例
1.某随机序列[12,5,6,4,6,5,5,7,…]中，找到出现次数最高的3个元素，它们出现次数是多少？
2.对某英文文章的单词，进行词频统计，找到出现次数最高的10个单词，它们出现次数是多少？
解决办法

1.首先我们创建这个随机序列，导入random模块下的randint

from random import randint

利用列表解析randint产生一个随机序列，值在0-20之间，产生30个元素，然后将值赋给变量data

from random import randint
data=[randint(0,20) for _ in xrange(30)]
print data
输出：
[2, 15, 15, 17, 11, 13, 16, 20, 7, 13, 18, 3, 9, 6, 12, 4, 3, 20, 5, 7, 14, 3, 13, 6, 2, 17, 6, 15, 20, 7]

这样序列就有了。
思考：
最终的结果肯定是一个字典。

以data作为字典的键，以0作为初始值，创建一个新字典c

c=dict.fromkeys(data,0)
print c

{1: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0, 11: 0, 13: 0, 16: 0, 19: 0, 20: 0}

得到这样的字典后，我们可以对data进行迭代。
每碰到一个x，就到c中相应的位置加1，也就是在它值上加1就可以了。

这个循环运行完后，就是我们c中统计的结果

for x in data:
    c[x] += 1

{0: 1, 1: 1, 2: 3, 3: 1, 5: 2, 6: 3, 8: 1, 9: 3, 10: 3, 11: 1, 12: 4, 13: 1, 14: 2, 15: 1, 16: 2, 18: 1}

上面这是一种方法，但是要找到频度最高的3个元素，也就是根据字典的值，对字典进行排序。

另一种方法：
使用collections.Counter对象：
将序列传入Counter的构造器，得到Counter对象是元素频度的字典。
Counter.most_common(n)方法得到频度最高的n个元素的列表。

具体操作
首先从collections下导入Counter，这个Counter专门用来处理这类问题。

from collections import Counter

c2 = Counter(data)直接将data传给Counter的构造器
，让这个变量为c2，它也是一个字典，与c一样。

from collections import Counter
c2 = Counter(data)

接下来，使用Counter.most_common(n)，也就是common方法
找到频度最高的3个元素
将3传进去
c2.most_common(3)

#输出：
Counter({3: 5, 17: 4, 12: 3, 14: 3, 15: 3, 0: 2, 5: 2, 1: 1, 4: 1, 6: 1, 8: 1, 10: 1, 13: 1, 16: 1, 20: 1})
0
1
[(3, 5), (17, 4), (12, 3)]

2.我们先找一个文本文件，mytest.txt

对其进行词频统计
先导入正则表达式的re模块,打开它并读进来，整个作为一个字符串。

import re
txt=open('mytest.txt').read()
然后进行分割，将每个词取出来，放在一个序列当中
我们使用正则表达式的分割方法

re.split('\W+',txt)

这个列表得到之后，我们可以传给Counter并赋给c3这个变量

import re
txt = open('mytest.txt').read()
c3 = Counter(re.split('\W+',txt))

【知识补充】

collections模块的Counter类

Counter类的目的是用来跟踪值出现的次数。它是一个无序的容器类型，以字典的键值对形式存储，其中元素作为key，其计数作为value。计数值可以是任意的Interger（包括0和负数）。Counter类和其他语言的bags或multisets很相似。

1-4如何根据字典中值的大小，对字典中的项排序

【实际案例】
某班英语成绩以字典形式存储为：
{'LiLei':79,'Jim':88,'Lucy':92…}
根据成绩高低，计算学生排名。

【解决方案】
使用Python的内置函数sorted
1.利用zip将字典数据转化元组
2.传递sorted函数的key参数

In [10]: sorted([9,1,2,8,5,4])
Out[10]: [1, 2, 4, 5, 8, 9]

首先我们采用随机函数创建随机的成绩表，
我们用xyzabc代表6个人
将生成的成绩表，然后将它赋给变量d

from random import randint

d={x: randint(60,100) for x in 'xyzabc'}
print d

结果：
{'a': 65, 'c': 73, 'b': 96, 'y': 91, 'x': 83, 'z': 84}

我们首先看直接排序

dd=sorted(d)
print dd

结果：
['a', 'b', 'c', 'x', 'y', 'z']

======

In [17]: d={x: randint(60,100) for x in 'xyzabc'}

In [18]: iter(d)
Out[18]: <dictionary-keyiterator at 0x3f787c8>

In [19]: list(iter(d))
Out[19]: ['a', 'c', 'b', 'y', 'x', 'z']

In [20]:

这是我们不需要的结果，所以此时要将字典进行某种转换，让它变成sorted可以排序的结构
字典的项无非就是一个键和一个值
我们想到了元组
假设我们将其转换成这种形式，将值放在前面
(97,'a')(69,'b')
思考：
我们为什么要将值放在前面？

因为元组的比较，是先比较第0个元素

In [20]: (97,'a')> (69,'b')
Out[20]: True

In [22]: (97,'a')> (97,'b')
Out[22]: False

这样我们思路有了：
就是将字典变成上面这样的元组的一个列表，(97,'b')，每一个都变成这样一个元组
先看一下：得到键和值的方法：

In [23]: d.keys()
Out[23]: ['a', 'c', 'b', 'y', 'x', 'z']

In [24]: d.values()
Out[24]: [92, 94, 61, 60, 80, 72]

这样，我们用ZIP函数给拼起来，做成一个:

In [25]: zip(d.values(),d.keys())
Out[25]: [(92, 'a'), (94, 'c'), (61, 'b'), (60, 'y'), (80, 'x'), (72, 'z')]

这样就构成了一个元组的列表

可以进行内存优化一下：

In [26]: zip(d.itervalues(),d.iterkeys())
Out[26]: [(92, 'a'), (94, 'c'), (61, 'b'), (60, 'y'), (80, 'x'), (72, 'z')]

然后对zip(d.itervalues(),d.iterkeys())进行sorted()

In [27]: sorted(zip(d.itervalues(),d.iterkeys()))
Out[27]: [(60, 'y'), (61, 'b'), (72, 'z'), (80, 'x'), (92, 'a'), (94, 'c')]

上面是第一种方式
下面我们看第二种方式

同样需要这样一个元组的列表进行排序

In [28]: d.items()
Out[28]: [('a', 92), ('c', 94), ('b', 61), ('y', 60), ('x', 80), ('z', 72)]

这里边我们就可以使用sorted的一个参数key
传递一个lambda匿名函数，我们可以定义哪个作为比较的键

In [29]: sorted(d.items(),key=lambda x:x[1])
Out[29]: [('y', 60), ('b', 61), ('z', 72), ('x', 80), ('a', 92), ('c', 94)]

【知识补充】

一、lambda函数也叫匿名函数，即，函数没有具体的名称。先来看一个最简单例子：

def f(x):
return x**2
print f(4)
# Python中使用lambda的话，写成这样
g = lambda x : x**2
print g(4)

二、lambda和普通的函数相比，就是省去了函数名称而已，同时这样的匿名函数，又不能共享在别的地方调用。
其实说的没错，lambda在Python这种动态的语言中确实没有起到什么惊天动地的作用，因为有很多别的方法能够代替lambda。

1. 使用Python写一些执行脚本时，使用lambda可以省去定义函数的过程，让代码更加精简。
2. 对于一些抽象的，不会别的地方再复用的函数，有时候给函数起个名字也是个难题，使用lambda不需要考虑命名的问题。
3. 使用lambda在某些时候让代码更容易理解。
   lambda基础
   lambda语句中，冒号前是参数，可以有多个，用逗号隔开，冒号右边的返回值。lambda语句构建的其实是一个函数对象，见证一下：

foo = [2, 18, 9, 22, 17, 24, 8, 12, 27]
print filter(lambda x: x % 3 == 0, foo)

print map(lambda x: x * 2 + 10, foo)

print reduce(lambda x, y: x + y, foo)

1-5 如何快速找到多个字典中的公共键

什么是公共键？
就是在每个字典中都出现的键。
【实际案例】
西班牙足球队甲级联赛，每一轮球员进球统计：

第一轮:{'苏亚雷斯':1,'梅西':2,'本泽马':1,'C罗':3…}

第二轮:{'苏亚雷斯':2,'C罗':1,'格里兹曼':2,'贝尔':2…}

第三轮:{'苏亚雷斯':1,'托雷斯':2,'贝尔':2,'内马尔':1…}

……

统计出前N轮，每场比赛都有进球的球员。

【解决办法】
方法一：使用简单的遍历
我们先用随机函数
先随机产生进球球员
假设有7名球员：abcdefg，然后用sample函数进行随机取样，产生进球的球员
比如产生3个

>>> sample('abcdefg',3)
['a', 'b', 'd']

数字不是固定的，不是每轮都是3个人进球，这样我们再改一下，让进球的球员数目也是随机的
3-6个人进球

>>> sample('abcdefg',randint(3,6))
['a', 'c', 'f']
>>> sample('abcdefg',randint(3,6))
['e', 'a', 'f', 'b', 'c']
>>> 

之后，我们就可以用字典解析产生每轮的数据

我们可以这样做：
我们限定每一轮的进球数为1-4个，
第一轮：

>>> s1={x: randint(1,4) for x in sample('abcdefg',randint(3,6))}
>>> s1
{'a': 3, 'd': 3, 'g': 4}

这样s1的数据就产生了。
我们用相同的方法产生第二轮，第三轮的数据

>>> s2={x: randint(1,4) for x in sample('abcdefg',randint(3,6))}
>>> s3={x: randint(1,4) for x in sample('abcdefg',randint(3,6))}
>>> 

然后我们分别看一下：

>>> s1
{'a': 3, 'd': 3, 'g': 4}
>>> s2
{'c': 3, 'b': 3, 'e': 2, 'd': 1, 'g': 3, 'f': 3}
>>> s3
{'a': 3, 'b': 4, 'e': 4, 'd': 1, 'f': 1}
>>> 

我们看到d球员每轮都有进球
解决的办法是我们迭代其中的键
先定义一个res：

>>> res = []
>>> for k in s1:
    if k in s2 and k in s3:
        res.append(k)

        
>>> res
['d']
>>> 

从而找到了公共键
方法二：利用集合（set）的交集操作：

step1：使用字典的viewkeys()方法，得到一个字典keys的集合
（这是python2的做法，python3使用keys()方法获得所有的键）
step2：使用map函数，得到所有的字典的keys的集合
step3：使用reduce函数，取得所有字典的keys的集合的交集

如下操作：

>>> s1.viewkeys()
dict_keys(['a', 'd', 'g'])
>>> 

这样我们就得到了这样一个集合
接下来我们同样对s2和s3同样取这样的集合

>>> s2.viewkeys()
dict_keys(['c', 'b', 'e', 'd', 'g', 'f'])
>>> s3.viewkeys()
dict_keys(['a', 'b', 'e', 'd', 'f'])
>>> 

既然是集合，我们就可以取它的交集

>>> s1.viewkeys() & s2.viewkeys() & s3.viewkeys()
set(['d'])
>>> 

这是我们以集合的方式解决了这个问题
上面是3轮的做法，如果是n轮怎么办？
我们可以用map函数和reduce函数处理这样的问题

>>> map(dict.viewkeys,[s1,s2,s3])#对于n轮向下添加
[dict_keys(['a', 'd', 'g']), dict_keys(['c', 'b', 'e', 'd', 'g', 'f']), dict_keys(['a', 'b', 'e', 'd', 'f'])]

具体思路1和2进行交集，其结果再与第3个交集……
总用前面一系列的结果和后面一个进行交集，进行迭代：

>>> reduce(lambda a,b: a & b,map(dict.viewkeys,[s1,s2,s3]))
set(['d'])
>>> 

用一条命令得到这样的结果

1-6如何让字典保持有序？

【实际案例】
编程竞赛系统，对参赛选手编程解题进行计时，选手完成题目后，把该选手解题用时记录到字典中，以便赛后按选手名查询成绩。
（答题时间越短，成绩越优）

{'Noodles':(2,43).'Rossum':(5,43),'Tom':(1,23)......}

比赛结束后，需按排名顺序依次打印选手成绩，如何实现?

【分析问题】
分析：
越先进入字典的，他成绩越优秀，所以我们希望能像列表那样，能按照每一个项进入字典的次序来打印它，但是python中默认的字典是不具备这样的功能的，也就是不具备这样的有序性

首先我们创建一个字典

d = {}

# 假设Jim是第一个完成比赛的人，35分钟
d['Jim'] = (1,35)
# 第二个，37分钟
d['Leo'] = (2,37)
# 第三个，40分钟
d['Bob'] = (3,40)

我们希望要的是我们在迭代这个字典d的时候，它能按照先后进入顺序进行遍历

In [5]: for k in d: print k
Bob
Jim
Leo

In [6]:

明显次序不对，所以我们不能使用这样的数据结构

我们使用一个能维护这样结果的数据字典

【解决方案】

我们使用collections.OrderedDict，它是一个有序的字典
以OrderedDict替代内置字典Dict，依次将选手成绩存OrderedDict

我们先创建这样一个字典，它也叫d

d = OrderedDict()

然后将上面的3个复制一下
之后，我们同样迭代
程序段如下：

In [7]: from collections import OrderedDict

In [8]: d = OrderedDict()

In [9]: d['Jim'] = (1,35)

In [10]: d['Leo'] = (2,37)

In [11]: d['Bob'] = (3,40)

In [12]: for k in d: print k
Jim
Leo
Bob

In [13]:

这样次序就对了。

我们这样模拟
我们创建出8名拳手

players = list('ABCDEFGH')

这里需要time模块的time函数，开始时记一下时间，结束时记一下时间。

In [13]: players = list('ABCDEFGH')

In [14]: from time import time

定义一个start用来记录考试开始的时间点

start = time()

接着等待每个人答题完毕

下面进行模拟：

from time import time
from random import randint
from collections import OrderedDict
d = OrderedDict() #创建这样一个成绩表
players = list('ABCDEFGH')
start = time()

for i in xrange(8):
    input()
    p = players.pop(randint(0,7-i))
    end = time()
    print (i+1,p,end - start)
    d[p] = (i+1,end - start) #用元组存储这种拳手排盘，用时
这里input的作用是一个阻塞函数，


结果：
(1, 'A', 1104.550999879837)
(2, 'F', 1105.4389998912811)
(3, 'H', 1106.231999874115)
(4, 'G', 1107.2069997787476)
(5, 'D', 1107.8709998130798)
(6, 'E', 1108.4069998264313)
(7, 'C', 1108.9429998397827)
(8, 'B', 1109.383999824524)

假设比赛结束了，我们要公布成绩，我们要遍历一下

In [21]: for k in d:
    ...:     print k,d[k]
    ...:
输出结果：

Jim (1, 35)
Leo (2, 37)
Bob (3, 40)

In [22]:

【知只补充】

pop() 函数
pop() 函数用于移除列表中的一个元素（默认最后一个元素），并且返回该元素的值。
pop()方法语法：

list.pop(obj=list[-1])

参数
obj -- 可选参数，要移除列表元素的对象。
返回值
该方法返回从列表中移除的元素对象。
实例

以下实例展示了 pop()函数的使用方法：

aList = [123, 'xyz', 'zara', 'abc']

print "A List : ", aList.pop()
print "B List : ", aList.pop(2)

以上实例输出结果如下：

In [23]: aList = [123, 'xyz', 'zara', 'abc']

In [24]: print "A List : ", aList.pop()
A List :  abc

In [25]: print "B List : ", aList.pop(2)
B List :  zara

In [26]: print "A List : ", aList.pop()
A List :  xyz

In [27]:

1-7 如何实现用户的历史记录功能

【实际问题】
很多应用程序都有浏览用户的历史记录的功能，
例如:
浏览器可以查看最近访问过的网页
视频播放器可以查看最近播放过视频文件
shell可以查看用户输入过的命令
……
现在我们制作了一个简单的猜字的小游戏，添加历史记录功能，
显示用户最近猜过的数字，如何实现？

【分析思路】
在这里我们做一个限定，历史记录不可能是无限条，我们只让他显示最近5次的历史记录

【解决办法】
我们可以使用容量为n的队列存储历史记录

使用标准库collections中的deque，它是一个双端循环队列。
程序退出前，可以使用pickle将对列对象存入文件，再次运行程序时将其导入。

首先我们导入deque
然后应用这个函数创建一个队列，前面为队列的初始值，后面为队列的容量

q = deque([],5)

对这个队列，每次从右边进行一个append操作

from collections import deque
In [32]: q.append(1)

In [33]: q
Out[33]: deque([1, 1])

In [34]: q.append(2)

In [35]: q.append(3)

In [36]: q.append(4)

In [37]: q
Out[37]: deque([1, 1, 2, 3, 4])

In [38]: q.append(5)

In [39]: q
Out[39]: deque([1, 2, 3, 4, 5])

In [40]: q.append(6)

In [41]: q
Out[41]: deque([2, 3, 4, 5, 6])

In [42]: q.append(7)

In [43]: q
Out[43]: deque([3, 4, 5, 6, 7])

In [44]:

这样，我们就可以用deque完成这样的事情。

from collections import deque 
from random import randint 

N = randint(0,100)
history = deque([],5) 

def guess(k):
    if k == N:
        print('right')
    if k < N:
        print("%s is less-than N" % k)
    else:
        print("%s is greater-than N" % k) 
    return False 

while True:
    line = raw_input("please input a number:")
    if line.isdigit():
        k = int(line)
        history.append(k)
        if guess(k):
            break
    elif line == "history" or line == 'h?':
        print(list(history)) #以列表的形式展示

please input a number:50
50 is greater-than N
please input a number:49
49 is greater-than N
please input a number:48
48 is greater-than N
please input a number:20
20 is less-than N
please input a number:h?
[50, 49, 48, 20]
please input a number:60
60 is greater-than N
please input a number:90
90 is greater-than N

please input a number:h?
[49, 48, 20, 60, 90]
please input a number:

这样这个功能就完成了，现在还有一个问题
对列deque是在内存当中的，程序退出后就消失了
这就需要将历史记录这个对象存在文件录中
即将history这个对象保存
下次再load进来

下面我们对pickle进行介绍
它可以把一个python对象存储到文件当中，也可以从文件当中load一个python对象

In [44]: import pickle

In [45]: pickle.dump?
Signature: pickle.dump(obj, file, protocol=None)
Docstring: <no docstring>
File:      c:\python27\lib\pickle.py
Type:      function

In [46]: pickle.dump(q,open('history','w'))

In [47]:

此时历史记录就保存在这个文件当中了
下一次程序打开的时候，需要一个反向操作，load

In [47]: pickle.load?
Signature: pickle.load(file)
Docstring: <no docstring>
File:      c:\python27\lib\pickle.py
Type:      function

In [48]: q2=pickle.load(open('history'))

In [49]: q2
Out[49]: deque([3, 4, 5, 6, 7])

我们发现，q2和q是一致的，完毕！