Py3——数据结构和算法

浅浅的花香味﹌ 2022-05-31 07:29 134阅读 0赞

*[http://python3-cookbook.readthedocs.io][http_python3-cookbook.readthedocs.io]*

## 解压序列赋值给多个变量 ##

将一个包含n个元素的元组或者是序列通过赋值语句解压并赋值给多个变量。这种解压赋值可以用在任何可迭代对象上面，包括字符串，文件对象，迭代器和生成器。  
\*\*变量的数量必须跟序列元素的数量是一样的！

p = (1,2,3)
    a,b,c = p
    message = ['mary',18,'man','13162981062']
    name,age,gender,phone = message
    
    [out]: a = 1, b = 2, c = 3
           name = mary, age = 18, gender = man, phone = 13162981062

*！当变量数与元素个数不一致时将会产生一个异常*

> 当你只想解压一部分，丢弃其他的值时，可以用任意变量名区占位而不去使用。前提是你这些变量名在其他地方没有被使用到

## 解压可迭代对象赋值给多个变量 ##

？如何从可迭代对象中解压出n个元素来：

###### 情景1：N个元素，去掉第一个与最后一个，取剩余均值。 ######

def cal_avg(data):
        first,*middle,last
        return avg(middle)

###### 情景2：单独取出开头部分数据 ######

data = ('name','email','phone1','phone2')
    name,email,*phone = data

> 使用\*号解压出来的变量永远是列表类型

**\* 相当于python中的可变参数，在函数中使用可变参数与关键字参数传值时，必须放在位置参数后面**

## 保留最后N个元素 ##

？在迭代操作或者其他操作的时候，怎样只保留最后有限几个元素的历史记录：

from collections import deque
    
    def search(lines, pattern, history=5):
        previous_lines = deque(maxlen=history)
        for line in lines:
            if pattern in line:
                yield line, previous_lines
            previous_lines.append(line)
    
    # Example use on a file
    if __name__ == '__main__':
        with open(r'../../cookbook/somefile.txt') as f:
            for line, prevlines in search(f, 'python', 5):
                for pline in prevlines:
                    print(pline, end='')
                print(line, end='')
                print('-' * 20)

## 查找最大或最小的 N 个元素 ##

？怎样从一个集合中获得最大或者最小的N个元素列表

> heapq 模块有两个函数：nlargest() 和 nsmallest() 可以完美解决这个问题

import heapq
    nums = [1,8,2,23,7,-4,18,23,42,37,2]
    heapq.nlargest(3,nums)   #[42,37,23]
    heapq.nsmallest(3,nums)  #[-4,1,2]

更具体更复杂的数据结构：

portfolio = [
        {
       'name': 'IBM', 'shares': 100, 'price': 91.1},
        {
       'name': 'AAPL', 'shares': 50, 'price': 543.22},
        {
       'name': 'FB', 'shares': 200, 'price': 21.09},
        {
       'name': 'HPQ', 'shares': 35, 'price': 31.75},
        {
       'name': 'YHOO', 'shares': 45, 'price': 16.35},
        {
       'name': 'ACME', 'shares': 75, 'price': 115.65}
    ]
    cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
    expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])

————AND：

>  *  当要查找的元素个数相对比较小的时候，nlargest() 和 nsmallest() 是比较好的
>  *  当只想查找唯一的最大最小时，max() 和 min() 是比较好的
>  *  当查找的元素快接近于集合大小时，排序操作会更好。

## 实现一个优先级队列 ##

使用 heapq 模块实现一个简单的优先级队列：

import heapq
    
    class PriorityQueue:
        def __init__(self):
            self._queue = []
            self._index = 0
    
        def push(self, item, priority):
            heapq.heappush(self._queue, (-priority, self._index, item))
            self._index += 1
    
        def pop(self):
            return heapq.heappop(self._queue)[-1]

使用这个简单的队列

>>> class Item:
    ...     def __init__(self, name):
    ...         self.name = name
    ...     def __repr__(self):
    ...         return 'Item({!r})'.format(self.name)
    ...
    >>> q = PriorityQueue()
    >>> q.push(Item('foo'), 1)
    >>> q.push(Item('bar'), 5)
    >>> q.push(Item('spam'), 4)
    >>> q.push(Item('grok'), 1)
    >>> q.pop()
    Item('bar')
    >>> q.pop()
    Item('spam')
    >>> q.pop()
    Item('foo')
    >>> q.pop()
    Item('grok')
    >>>

\_\_\_\_\_\_\_\_\_AND:

> heapq模块的使用，函数heapq.heappush() 和 heapq.heappop() 分别在队列 \_queue 上插入和删除第一个元素，并且队列\_queue保证第一个元素拥有最高优先级，heappop() 函数总是返回”最小的”的元素，这就是保证队列pop操作返回正确元素的关键。 另外，由于 push 和 pop 操作时间复杂度为 O(log N)，其中 N 是堆的大小，因此就算是 N 很大的时候它们运行速度也依旧很快。

## 字典中的键映射多个值 ##

？怎样实现一个键对应多个值的字典：  
*构造思路：*

> 字典本来是一个键对应一个单值的映射，如果一个键映射多个值的话，需要将这些值放在另外的容器中。  
> *常规构造：*
> 
>     d = {
>           'a' : [1,2,3],
>           'b' : [4,5]
>     }
>     e = {
>           'a' : {
>         1,2,3},
>           'b' : {
>         4,5}
>     }
> 
> *模块构造：*

from collections import defaultdict
    #defaultdict 会自动初始化每个KEY刚开始对应的值
    d = defaultdict(list)
    d['a'].append(1)
    d['a'].append(2)
    d['b'].append(4)

## 字典排序 ##

控制字典的元素顺序

from collections import OrderedDict
    
    d = OrderedDict()
    d['foo'] = 1
    d['bar'] = 2
    d['spam'] = 3
    for key in d:
        print(key,d[key])

*!有序字典对于你将来想要序列化或编码成其他格式的映射，而又不想改变其顺序时是非常有用的*

—————AND:

> OrderedDict 内部维护着一个根据键插入顺序排序的双向链表，每当一个新元素插入进来的时候，它会被放到链表的尾部，对于一个已经存在的键的重复赋值不会改变键的顺序。  
> 一个OrderedDict类型字典大小是一个普通字典的两倍。

## 字典的运算 ##

？怎么在数据字典中执行一些计算操作（最大最小值，排序等）：

prices = {
       'ACME':45.23,'AAPL':612.78,'IBM':205.55,'HPQ':37.20,'FB':10.75}

为了对字典值执行计算操作，通常需要使用zip()函数现将键和值反转过来。  
查找最大值/最小值

> min\_price = min(zip(prices.values(),prices.keys()))  
> max\_price = max(zip(prices.values(),prices.keys()))

排序

> prices\_sorted = sorted(zip(prices.values(),prices.keys()))

! *zip()函数创建的是一个只能访问一次的迭代器*  
————AND:

> 对字典执行运算，仅仅作用于键  
> 当计算中用到了值键对，如果值恰好重复，那么键将决定返回哪一个实体

## 查找两字典的相同点 ##

？查找两字典中相同的键，相同的值等等

a = {
       'x':1,'y':2,'z':3}
    b = {
       'w':10,'x':11,'y':2}

在两字典的 keys() 或者 items() 方法返回结果上执行集合操作。

#py3环境，py2下报错
    a.keys() & b.keys()     #{‘x','y'}
    a.keys() - b.keys()     #{'z'}
    a.items() & b.items()   #{'y',2}

构造一个排除几个指定键的新字典：

c = {key:a[key] for key in a.keys() - {
       'z','w'}}

\_\_\_\_AND:

> 字典就是一个键集合与值集合的映射关系。字典的 keys() 方法返回一个展现键集合的键视图对象，键视图的一个很少被了解的特性就是他们也支持集合操作，比如集合并、交、差运算

## 删除序列相同元素并保持顺序 ##

？怎样在一个序列上保持元素孙旭的同时消除重复的值

#当序列上的值都是hashable类型时
    def dedupe(items):
        seen = set()
        for item in items:
            if item not in seen:
                yield item
                seen.add(item)

#消除元素不可hashable
    def dedupe(items, key=None):
        seen = set()
        for item in items:
            val = item if key is None else key(item)
            if val not in seen:
                yield item
                seen.add(val)

> 如果一个对象在自己的生命周期中有一哈希值（hash value）是不可改变的，那么它就是可哈希的（hashable）的

## 命名切片 ##

> record = ‘………………..100 …….513.25 ……….’  
> 取出100 和 513.25进行操作

#常规硬编码切片
    cost = int(record[20:23]) * float(record[31:37])
    
    #命名切片
    SHARES = slice(20,23)
    PRICE = slice(31,37)
    cost = int(record[SHARES]) * float(record[PRICE])

## 序列中出现次数最多的元素 ##

？怎么找出一个序列中出现次数最多的元素呢：

words = ['look','into','my', 'eyes','look','into', 'my','eyes','the','eyes','the','eyes','the','eyes','not','around','the','eyes',"don't",'look','around','the','eyes','look','into','my','eyes',"you're",'under']
    from collections import Counter
    word_counts = Counter(words)
    #出现频率最高的3个单词
    top_three = word_counts.most_common(3)
    print(top_three)

————AND:

> Counter实例可以手动增加计数，或者是使用update（）方法。  
> Counter实例有个很容易跟数学运算操作相结合的特性。  
> 它的底层实现是基于字典的键值映射。

## 通过某个关键字排序一个字典列表 ##

？根据某个或者某几个字典字段来排序一个列表

>     rows = [
>             {
>         'fname': 'Brian', 'lname': 'Jones', 'uid': 1003},
>             {
>         'fname': 'David', 'lname': 'Beazley', 'uid': 1002},
>             {
>         'fname': 'John', 'lname': 'Cleese', 'uid': 1001},
>             {
>         'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
>         ]

根据任意字典字段来排序

from operator import itemgetter
    rows_by_fname = sorted(rows,key=itemgetter('fname'))
    rows_by_uid = sorted(rows,key=itemgetter('uid'))
    #也可以根据多个字段进行排序
    rows_by_lfname = sorted(rows,key=itemgetter('lname','fname'))

## 通过某个字段将记录分组 ##

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'},
    ]
    
    #使用 date 进行排序
    from operator import itemgetter
    from itertools import groupby
    
    rows.sort(key=itemgetter('date'))
    for date,items in groupby(rows,key=itemgetter('date')):
        print(date)
        for i in items:
            print('',i)
    
    [OUT]: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'}

————AND：

> groupby()函数扫描整个序列并且查找连续相同值的元素序列  
> 分组前一定要将数据进行排序，因为groupby()仅仅检查连续的元素。

## 过滤序列元素 ##

？利用一些规则从数据序列中提取出需要的值或者是缩短序列  
简单的列表推导：

mylist = [1,4,-5,10,-7,2,3,-1]
    zero_left = [n for n in mylist if n>0]
    zero_right = [n for n in mylist if n<0]

> 当推导会产生一个非常大的结果集时，使用列表推导是一个很不明智的决定。可以使用生成器表达式迭代产生过滤的元素

pos = (n for n in mylist if n>0)

当过滤规则较为复杂时可以采用内建函数 filter() 来过滤

values = ['1', '2', '-3', '-', '4', 'N/A', '5']
    def is_int(val):
        try:
            x = int(val)
            return True
        except ValueError:
            return False
    ivals = list(filter(is_int, values))
    print(ivals)
    # Outputs ['1', '2', '-3', '4', '5']

————AND:

> 很多情况下过滤时将不符合条件的值用新值替代
> 
>     [n if n > 0 else 0 for n in mylist]
> 
> 另外还有一个过滤工具就是 itertools.compress()。它以一个iterable对象和一个相对应的Boolean选择器序列作为输入参数，然后输出iterable对象中对应选择器为True的元素。当需要用另外一个相关联的序列来过滤某个序列的时候，这个函数时非常有用的。

## 从字典中提取子集 ##

？构造一个字典，它是另外一个字典的子集  
字典推导：

prices = {
        'ACME': 45.23,
        'AAPL': 612.78,
        'IBM': 205.55,
        'HPQ': 37.20,
        'FB': 10.75
    }
    
    p1 = {key: value for key, value in prices.items() if value > 200}
    
    tech_names = {
       'AAPL', 'IBM', 'HPQ', 'MSFT'}
    p2 = {key: value for key, value in prices.items() if key in tech_names}

## 映射名称到序列元素 ##

？通过名称来访问元素比通过下标来访问元素更通俗易懂。

#collections.namedtuple()接收一个类型名和需要的字段返回一个类
    >>> from collections import namedtuple
    >>> Subscriber = namedtuple('Subscriber', ['addr', 'joined'])
    >>> sub = Subscriber('jonesy@example.com', '2012-10-19')
    >>> sub
    Subscriber(addr='jonesy@example.com', joined='2012-10-19')
    >>> sub.addr
    'jonesy@example.com'
    >>> sub.joined
    '2012-10-19'

————AND:  
命名元组在某些方面可以来替代字典。字典存储总要耗费更多的内存空间，如果需要构建一个非常大的包含字典的数据结构，那么使用命名元组会更加高效。命名元组是不可更改的！

## 合并多个字典或映射 ##

？从多个字典或映射检测某些键或值是否存在

a = {
       'x':1,'z':3}
    b = {
       'y':2,'z':4}
    
    from collections import ChainMap
    c = ChainMap(a,b)
    c['x']   # 1 
    c['y']   # 2
    c['z']   # 3
    c['i']   # 不存在将会报错

————AND:

> ChainMap 只是在逻辑上将多个字典合并成一个字典。相对于update它并不会去创建一个新的字典，update方法如果原字典做了更新是不会同步到新合并的字典中去。

[http_python3-cookbook.readthedocs.io]: http://python3-cookbook.readthedocs.io