【2017-09-06】数据结构与算法（五）

序列

• 过滤序列元素
  • 推导式，见上一篇文章，值得注意的是，如果过滤后的结果很大时，考虑到内存的占用，可以使用生成器表达式。
  • 内建的 filter() 函数使用
  • itertools模块中compress()函数的使用

>>> mylist = [1, 4, -5, 10, -7, 2, 3, -1]
>>>#列表推导式
>>> [i for i in mylist if i>0]
[1, 4, 10, 2, 3]
>>>#生成器表达式
>>> (i for i in mylist if i>0)
<generator object <genexpr> at 0x005745D0>
>>> 

   当过滤规则较复杂，不能简单用推导式或者生成器表达式处理，可以使用内建的 filter() 函数。filter()函数接收一个函数 f 和一个list，这个函数 f 的作用是对每个元素进行判断，返回 True或 False，filter()根据判断结果自动过滤掉不符合条件的元素，返回由符合条件元素组成的迭代器。

示例：利用filter()过滤出1~100中平方根是整数的数

>>> import math
>>> def isInteger(x):
    return math.sqrt(x) % 1==0
>>> filter(isInteger,range(1,101))
<filter object at 0x02315330>
>>> list(filter(isInteger,range(1,101)))
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

   itertools模块compress() 函数与filter（）类似，它以一个 iterable对象和一个相对应的 Boolean 序列作为输入参数。Boolean 序列，指示哪些元素符合条件。然后compress() 函数根据这个序列去iterable对象中选择并输出对应位置为 True 的元素。

>>> from itertools import compress
>>> compress('ABCDEF', [1,0,1,0,1,1])
<itertools.compress object at 0x023157B0>
>>> list(compress('ABCDEF', [1,0,1,0,1,1]))
['A', 'C', 'E', 'F']
>>> #当 Boolean 选择器长度小于iterable对象长度时，默认false
>>> list(compress('ABCDEF', [1,0,1]))
['A', 'C']
>>> 

• 通过某个字段将序列分组
  itertools模块groupby() 函数运用
     groupby() 函数扫描整个序列并且查找连续相同值 (或者根据指定 key 函数返回值相同) 的元素序列。在每次迭代的时候，它会返回一个值和一个迭代器对象，这个迭代器对象可以生成元素值全部等于上面那个值的组中所有对象。
     由于groupby() 函数是连续查找，当序列无序时，可能得不到想要的结果，需要事先进行排序

示例1：根据日期进行分组

>>> from operator import itemgetter
>>> from itertools import groupby
>>> rows = [
{'address': '5412 N CLARK', 'date': '07/01/2012'},
{'address': '5148 N CLARK', 'date': '07/04/2012'},
{'address': '5800 E 58TH', 'date': '07/02/2012'},
{'address': '2122 N CLARK', 'date': '07/03/2012'},
{'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'},
{'address': '1060 W ADDISON', 'date': '07/02/2012'},
{'address': '4801 N BROADWAY', 'date': '07/01/2012'},
{'address': '1039 W GRANVILLE', 'date': '07/04/2012'},
]
>>> rows.sort(key=itemgetter('date'))
>>> for date, items in groupby(rows, key=itemgetter('date')):
    print(date)
    for i in items:
        print(' ', i)

        
07/01/2012
  {'date': '07/01/2012', 'address': '5412 N CLARK'}
  {'date': '07/01/2012', 'address': '4801 N BROADWAY'}
07/02/2012
  {'date': '07/02/2012', 'address': '5800 E 58TH'}
  {'date': '07/02/2012', 'address': '5645 N RAVENSWOOD'}
  {'date': '07/02/2012', 'address': '1060 W ADDISON'}
07/03/2012
  {'date': '07/03/2012', 'address': '2122 N CLARK'}
07/04/2012
  {'date': '07/04/2012', 'address': '5148 N CLARK'}
  {'date': '07/04/2012', 'address': '1039 W GRANVILLE'}

>>> 

示例2：根据身高

>>> people=[192,156,200,185,170,166,160]
>>> def group(x):
    if x>180:
        return "hight"
    if x>170 and x<=180:
        return "middle"
    if x<=170:
        return "short"
>>> people.sort()
>>> people
[156, 160, 166, 170, 185, 192, 200]
>>> for zu, items in groupby(people, key=group):
    print(zu, list(items))

short [156, 160, 166, 170]
hight [185, 192, 200]