cookboo学习:1,对python数据结构和算法常用技巧

数据结构和算法

1,将序列分解成单独的变量

  • 问题需要把N个元素组成的元祖和序列,分解成N个单独的变量

  • 解决方案:使用拆包的方式分解可迭代对象

    >>> p = (4, 5)
    >>> a, b = p
    >>> a
    4
    >>> b
    5
    >>> data = ['xyb', 18, 180, ('mmm', 20, 165)]
    >>> name, age, tall, another = data
    >>> name
    'xyb'
    >>> another
    ('mmm', 20, 165)
    

    不仅仅是元组和列表,只要是可迭代对象,都是可以进行分解操作的,包括字符串,文件,迭代器、、

    >>> s = '1,2,3'
    >>> a, _, b, _, c = s
    >>> a
    '1'
    >>> b
    '2'
    >>> c
    '3'
    
  • 掌握:不需要的数据用 _ 来丢弃

2,从任意长度的可迭代对象中分解元素

  • 问题 :需要从某个可迭代对象中分解N个对象,但是这个对象的长度可能超过了N,会异常

  • 解决方案 :使用 * 来配合拆包使用

    >>> data = ['xyb', 18, 13586971744, 19857100635]
    >>> name, age, *number = data
    >>> name
    'xyb'
    >>> number
    [13586971744, 19857100635]
    
  • 掌握 :通过 *_ 截取未知的数据

    >>> one, *_, last = socres
    >>> one
    1
    >>> last
    8
    >>> _
    [5, 6, 7, 8, 10, 64, 21]
    

3,使用双向队列进行历史记录

  • 问题 :我们希望在迭代或者其他形式下保留最后几次时间内的记录,即历史记录

  • 解决方案 :使用双向队列 deque 来协助我们完成

    from collections import deque
    
    	# 1. 不给队列最大值,队列无限大
    >>> q = deque()
    >>> q.append(5)
    >>> q.append(6)
    >>> q.append(7)
    >>> q.appendleft(0)
    >>> q
    deque([0, 5, 6, 7])
    >>> q.pop()
    7
    
    	# 2. 给了最大值
    >>> q = deque(maxlen=3)
    >>> q.append(1)
    >>> q.append(2)
    >>> q.append(3)
    >>> q
    deque([1, 2, 3], maxlen=3)
    >>> q.append(4)
    >>> q
    deque([2, 3, 4], maxlen=3)
    
  • 在双向队列中,队列两端 添加弹出 的复杂度都是O[1]

4,找到最大或最小的N个元素

  • 问题 :在集合中找出最大或最小的N个元素

  • 解决方案 :使用 heapq 模块中的两个函数–nlargest()–和--nsmallest()

    >>> import heapq
    >>> nums = [1, 2, 5, 6, -8, 15, -32, 24, 6, 42, 0]
    >>> heapq.nlargest(3, nums)
    [42, 24, 15]
    >>> heapq.nsmallest(3, nums)
    [-32, -8, 0]
    
    	# 1. 他还能接受一个key,从而在更复杂的数据结构上进行操作
    >>> data = [
    ...     {'name': 'xyb', 'age': 18},
    ...     {'name': 'habby', 'age': 10},
    ...     {'name': 'yollw', 'age': 26}
    ... ]
    >>> heapq.nlargest(2, data, key=lambda x: x['age'])
    [{'name': 'yollw', 'age': 26}, {'name': 'xyb', 'age': 18}]
    >>> heapq.nsmallest(2, data, key=lambda x: x['age'])
    [{'name': 'habby', 'age': 10}, {'name': 'xyb', 'age': 18}]
    
  • 扩展 :如果要寻找的数据N远远小于总数据,那么heapq.heapify()会有更好的性能

    >>> nums = [4, 5, 6, 8,  2, 5, -5, -48, 0, -31, 51]
    >>> heap = heapq.heapify(nums)
    >>> heap = list(nums)
    >>> heapq.heapify(heap)			# 底层以栈堆的顺序排列
    >>> heap
    [-48, -31, -5, 0, 2, 5, 6, 8, 5, 4, 51]
    >>> heapq.heappop(heap)
    -48
    >>> heapq.heappop(heap)
    -31
    >>> heapq.heappop(heap)
    -5
    >>> heapq.heappop(heap)
    0
    >>> heapq.heappop(heap)
    2
    >>> heapq.heappop(heap)
    4
    

5,将一个键映射到多个值上面

  • 问题:字典的每个键都能映射多个值

  • 解决方案:创建 defaultdict(list) 这个字典

    >>> d = defaultdict(list)
    >>> d['a'].append(1)
    >>> d
    defaultdict(<class 'list'>, {'a': [1]})
    >>> d['b'].extend([1,2,3])
    >>> d
    defaultdict(<class 'list'>, {'a': [1], 'b': [1, 2, 3]})
    

6,对字典的值进行比较

  • 问题:我们想在字典上对数据进行各式各样的操作(求最大值,最小值,排序等)

  • 解决方案① :反转过来利用zip() 讲字典的键和值

    prices = {
        'apple': 42.6,
        'binana': 42.6,
        'piple': 42.6,
        'aaa': 42.6,
    }
    
    	# 1. 最大值,最小值
    min(zip(prices.values(), prices.keys()))
    max(zip(prices.values(), prices.keys()))
    
    	# 2. 按照值进行排序
    sorted(zip(prices.values(), prices.keys()))
    

    解决方案② :对 minmax 函数传递 key 这个参数

    prices = {
        'apple': 42.6,
        'binana': 42.6,
        'piple': 42.6,
        'aaa': 42.6,
    }
    
    	# 1. 返回键名
    min(prices, key=lambda k: prices[k])
    max(prices, key=lambda k: prices[k])
    

7,寻找两个字典的相同点

  • 问题 :有两个字典,我们想要在两个字典中找出他们的共同点(相同的键,值)

  • 解决方案 :用字典的 keys()values() 来进行集合的操作,字典的 keys 支持集合操作

    k1 = {
        'x': 10,
        'y': 15,
        'z': 20,
        'b': 80
    }
    k2 = {
        'w': 10,
        'y': 15,
        'z': 30,
        'b': 80
    }
    
    	# 1. 两个字典相同的key
    k1.keys() & k2.keys()	
    	# 2. 两个字典key相同,value相同的项
    k1.items() & k2.items()  	
    	# 3. 过滤一个字典的某些项
    {key: k1[key] for key in k1.keys() - {'b', 'z'}}
    k1 = {
        'x': 10,
        'y': 15,
    }
    

8,从序列中删除重复项且保持元素键顺序不变

  • 问题:去除序列中重复项,并且保持序列的顺序不变

  • 解决方案1 :通过集合+生成器的方式实现(元素可以被hash时,能实现__hash__的对象)

    def dedupe(items):
        seen = set()
        for item in items:
            if item not in seen:
                yield item
                seen.add(item)
    
  • 解决方案2 :通过集合+生成器的方式实现(元素可以被hash时,能实现__hash__的对象)

    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 val
                seen.add(val)
    
  • 高级用法:对于高级的数据类型,照样能够去重

    a = [{'a': 1, 'y': 2}, {'a': 1, 'y': 6}, {'a': 1, 'y': 2}, {'a': 1, 'y': 2}]
    list(dedupe(a, key=lambda d: (d['a'], d['y'])))
    

9,对切片命名

  • 问题:代码中有很多的 [0: 5, 2], [-4, -3, -1] 这样的硬编码切片,不容易我们回过头来看代码.

  • 解决方案:利用 slice 函数对切片命名

    s = [1, 2, 3, 4, 5, 6, 7]
    head = slice(0, 4, 1) 
    s[head]						# [1, 2, 3, 4]
    	
    head.start					# 0
    head.stop					# 4
    head.step					# 1
    
  • 拓展 :使用 indices 能够固定一段长度,所有值都必须在一个边界范围内

    s = [1, 2, 3, 4, 5, 6, 7]
    head = slice(0, 5, 2)
    print(head.indices(len(s)))			# (0, 5, 1)
    
    for i in range(*head.indices(len(s))):
        print('下表', i)
        print('值', s[i])
       
    """
    下表 0
    值 1
    下表 2
    值 3
    下表 4
    值 5
    """
    

10,找出序列中频率最高的元素

  • 问题 :有一个元素序列,求出现次数最多的元素是什么

  • 解决方案 :利用 collection.Counter 能够轻松实现

    1. most_counter() 找出频率最高的三个元素

      from collections import Counter
      word = ['a', 'a', 'b', 'c', 'c', 'd']
      counter = Counter(word)
      counter.most_common(2)			# [('a', 2), ('c', 2)]
      
      counter['a']					# 查看次数	2
      counter['d']					# 查看次数	1
      
    2. Counter 的其他用法,counter 底层维护的是一个字典

      	# 1. 因为counter背后维护的是一个字典,用字典的赋值方式
      s = ['a', 'b', 'c', 'd', 'a', 'b', 'c']
      counter = Counter()
      for i in s:
          counter[i] += 1
         
      print(counter)	
      # Counter({'a': 2, 'b': 2, 'c': 2, 'd': 1})
      
      	# 2. 进行两个counter的数学计算
      a = ['a', 'b', 'c', 'd']
      b = ['b', 'c', 'e', 'h']
      counter_a = Counter(a)
      counter_b = Counter(b)
       
      counter_a + counter_b
      # Counter({'a': 1, 'b': 2, 'c': 2, 'd': 1, 'e': 1, 'h': 1})
      

11,通过公共键对字典列表排序

  • 问题 :有一个字典列表,根据一个或多个字典中的值来对列表排序

  • 解决方案①:使用 operator 中的 itemgetter 函数来排序

    rows = [
        {'fname': 'B', 'iname': 'bbb', 'uid': '1006'},
        {'fname': 'C', 'iname': 'aaa', 'uid': '1001'},
        {'fname': 'D', 'iname': 'ddd', 'uid': '1000'},
        {'fname': 'C', 'iname': 'ccc', 'uid': '1002'}
    ]
    
    from operator import itemgetter
    rows_by_fname = sorted(rows, key=itemgetter('fname'))
    rows_by_uid = sorted(rows, key=itemgetter('uid'))
    	# 通过多行进行排序
    rows_by_fname_uid = sorted(rows, key=itemgetter('lname', 'uid'))
    ......
    [{'fname': 'B', 'iname': 'bbb', 'uid': '1006'},
     {'fname': 'C', 'iname': 'aaa', 'uid': '1001'}, 
     {'fname': 'C', 'iname': 'ccc', 'uid': '1002'}, 
     {'fname': 'D', 'iname': 'ddd', 'uid': '1000'}]
    
    [{'fname': 'D', 'iname': 'ddd', 'uid': '1000'}, 
     {'fname': 'C', 'iname': 'aaa', 'uid': '1001'}, 
     {'fname': 'C', 'iname': 'ccc', 'uid': '1002'},
     {'fname': 'B', 'iname': 'bbb', 'uid': '1006'}]
    

    解决方案② 是要用 lambda + sorted,性能比上面的要慢一点

    rows = [
        {'fname': 'B', 'iname': 'bbb', 'uid': '1006'},
        {'fname': 'C', 'iname': 'aaa', 'uid': '1001'},
        {'fname': 'D', 'iname': 'ddd', 'uid': '1000'},
        {'fname': 'C', 'iname': 'ccc', 'uid': '1002'}
    ]
    
    from operator import itemgetter
    rows_by_fname = sorted(rows, key=lambda k: k['fname'])
    rows_by_uid = sorted(rows, key=lambda k: k['uid'])
    	# 通过多行进行排序
    rows_by_fname_uid = sorted(rows, key=lambda x:(x['fname'], x['uid']))
    ......
    [{'fname': 'B', 'iname': 'bbb', 'uid': '1006'},
     {'fname': 'C', 'iname': 'aaa', 'uid': '1001'}, 
     {'fname': 'C', 'iname': 'ccc', 'uid': '1002'}, 
     {'fname': 'D', 'iname': 'ddd', 'uid': '1000'}]
    
    [{'fname': 'D', 'iname': 'ddd', 'uid': '1000'}, 
     {'fname': 'C', 'iname': 'aaa', 'uid': '1001'}, 
     {'fname': 'C', 'iname': 'ccc', 'uid': '1002'},
     {'fname': 'B', 'iname': 'bbb', 'uid': '1006'}]
    
  • 拓展itemgetterlambda 的方法照样能够运用到 max 和 min 这两个函数上

    max(rows, key=lambda k: k['uid'])
    max(rows, key=itemgetter('uid'))
    
    {'fname': 'B', 'iname': 'bbb', 'uid': '1006'}
    

12,通过实例属性对实例排序

  • 问题 :对一个类的多个实例通过实例属性排序

  • 解决方案 :通过对 sorted 的 key 键传值,使用 lambda 或者 attrgetter

    from operator import itemgetter
    
    class User:
        def __init__(self, user_id):
            self.id = user_id
            
        def __repr__(self):
            return 'User ({})'.format(self.id)
            
    users = [User(5), User(10), User(8), User(1)]
    
    sorted(users, key=lambda u: u.id)
    sorted(users, key=attrgetter('id'))
    
    # [User (1), User (5), User (8), User (10)]
    
  • 拓展attrgetterlambda 的方法照样能够运用到 max 和 min 这两个函数上

    max(users, key=lambda u: u.id)
    max(users, key=attrgetter('u'))
    
    User (10)
    

13,根据字段将记录分组

  • 解决 :有一系列的字典或实例对象,根据某个特点的字段(比如日期),来进行分组迭代

  • 解决方案① :通过 itertools.groupby() 来对数据进行分组

    rows = [
        {'address': '5412 N CLARK', 'date': '07/01/2012'},
        {'address': '5254 E CLARK', 'date': '07/01/2012'},
        {'address': '5312 N CLARK', 'date': '07/02/2012'},
        {'address': '5482 S CLARK', 'date': '07/03/2012'},
        {'address': '5484 N CLARK', 'date': '28/02/2012'}
    ]
    
    from itertools import groupby
    from operator import itemgetter
    
    rows.sort(key=itemgetter('date'))		# 这一步必须排序,否则分组会出错
    for date, items in groupby(rows, key=itemgetter('date')):
        print(date)
        for i in items:
            print(' '*4, i)
    

    cookboo学习:1,对python数据结构和算法常用技巧

  • 解决方案② :如果只是单存的对数据进行分组,不考虑内存,用 collections.defaultdict

    from collections import defaultdict
    rows_by_date = defaultdict(list)
    for row in rows:
        rows_by_date[row['date']].append(row)
    rows_by_date
    

    cookboo学习:1,对python数据结构和算法常用技巧

14,筛选序列中的元素

  • 问题 : 序列中有些数据是我们需要的,有些是不需要的,根据特定条件筛选

  • 解决方案① :使用列表推导式(原生输入不是很大的情况下)

    >>> my_list = [1, 2, 3, -5, 2, -10, -9, -12, 15]
    >>> [i for i in my_list if i > 0]
    [1, 2, 3, 2, 15]
    >>> [i for i in my_list if i < 0]
    [-5, -10, -9, -12]
    
  • 解决方案② :输入数据非常大,使用生成器表达式,惰性产生值

    >>> res = (i for i in my_list if i < 0)
    >>> res
    <generator object <genexpr> at 0x0000023C252D0E08>
    >>> for i in range(6):
    ...     print(i)
    ...
    0
    1
    2
    3
    4
    5
    
  • 解决方案③ :筛选条件过于复杂,写成函数用 filter() 函数进行过滤

    items = [', ', '**6', '-', '125', 'ss5', '12', '-10']
    
    def parse(item):
        try:
            if int(item) > 10:
                return True
        except Exception:
            return False
        
    list(filter(parse, items))
    
    # ['125', '12']
    
    • 拓展① :生成表达式\列表推到式的 数值转换,三目运算

      	# 1. 数值转换
      >>> s = [1, 2, 5, 4, 6, 1, 3, 7]
      >>> [i**2 for i in s]
      [1, 4, 25, 16, 36, 1, 9, 49]
      
      	# 2. 三目运算
      >>> s = ['1', '2', 'd', 'aa', '6.6', '0.2', '**']
      >>> [i if i.isdigit() else None for i in s]
      ['1', '2', None, None, None, None, None]
      
    • 拓展②布尔序列 + itertools.compress 进行筛选,数据超出布尔列表不予计算

      from itertools import compress
      data = [
          'aa1',
          'aa2',
          'aa3',
          'aa4',
          'aa5',
          'aa6',
          'aa7',
          'aa8',
          'aa9',
          'aa10'
      ]
      s = [1, 2, 5, 4, 6, 1, 3, 7]
      bool_list = [n > 5 for n in s]
      # [False, False, False, False, True, False, False, True]
      list(compress(data, bool_list))
      
      # ['aa5', 'aa8']
      

15,从字典中提取值创建字典

  • 问题 :我们需要创建一个字典,其本身是另外一个字典的子集

  • 解决方案① :利用字典推导式

    d = {
        'a': 1,
        'b': 2,
        'c': 3,
        'd': 4,
        'e': 5,
        'f': 6
    }
    {key: value for key, value in d.items() if value > 3}
    	# {'d': 4, 'e': 5, 'f': 6}
    {key: value for key, value in d.items() if key in ['a', 'b', 'c']} 
    	# {'a': 1, 'b': 2, 'c': 3}
    
  • 解决方案② :用 dict 函数强制转换 元组序列,速度比第一种快 2 倍!

    dict((k, v) for k, v in d.items() if v > 2)
    	# {'c': 3, 'd': 4, 'e': 5, 'f': 6}
    
  • 解决方案③ :比方案②更深奥的写法,字典取值生成,比第一种快 1.6 倍

    key = {'a', 'b', 'c'}
    {key: d[key] for key in d.keys() & key}	# 对key进行了一次交集运算
    	# {'c': 3, 'b': 2, 'a': 1}
    

16,给元组的值命名

  • 问题 :我们的代码是通过下表来访问元组或列表的,但是有时候会让我们难以阅读,我们希望像访问实例的属性那样访问元组的内容

  • 解决方案① :相对普通的元组,使用 nametuple 命名元祖,只是增加极小的空间就能实现

    >>> from collections import namedtuple
    >>> User = namedtuple('User', ['name', 'gender', 'age'])
    >>> a = User('a', 'M', 20)
    >>> a.name
    'a'
    >>> a.age
    20
    

    尽管他看起来像创建了一个类并且做了一个实例化的操作,但是他支持普通元组的所有操作,列如索引和分解,拆包等等

    nametuple 的别处用法,利用for循环解包数据创造命名元组

    data = [
        ('a', 1, 5),
        ('b', 6, 3),
        ('c', 2, 5),
        ('d', 3, 7),
        ('e', 4, 8),
    ]
    	# 1. 不用命名元组,用下表取值,语义表达不明确
    def comput_cost(records):
        total = 0.0
        for rec in records:
            total += rec[1] * rec[2]
        return total
    comput_cost(data)
    # 86.0
    
    	# 2. 使用命名元组,拆包形式生成
    User = namedtuple('User', ['name', 'data1', 'data2'])
    def comput_cost(records):
        total = 0.0
        for rec in records:
            user = User(*rec)
            total += user.data1 * user.data2
        return total
    # 86.0
    
  • 拓展用法①替代字典使用,占用内存更加小,比使用 __ slits __() 属性的类低那么一点

    	# !!! 使用 nametuple 创建的替代字典用法需要是要内置 _replace() 方法才能修改值
    >>> a = User('xyb', 20, 'F')
    >>> a.age = 21
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    AttributeError: can't set attribute
    
    >>> a._replace(age=21)
    User(name='xyb', age=21, gender='F')	# 修改成功
    
  • 拓展用法② :用 _replace 配合字典创建默认值的元组

    User = namedtuple('User', ['name', 'age', 'gender', 'number', 'date'])
    default_user = User('', '', '', None, None)
    def dict_to_tuple(d):
        return default_user._replace(**d)
    
    d = {'name': 'xyb', 'age': 20}
    dict_to_tuple(d)
    # User(name='xyb', age=20, gender='', number=None, date=None)
    

17,生成器表达式作为函数单独参数

  • 问题 :我们需要调用一个换算函数,但是首先得对数据做转换和筛选

  • 解决思路 :在函数中使用生成器表达式

    	# 1. 列如 sum 函数
    nums = [1, 2, 3, 4, 5]
    sum(x * x for x in nums)
    	# 2. any函数(只要传入的iterable对象的元素中有一个True就返回True)
    import os
    files = os.listdir()
    if any(name.endswith('.py') for name in files):
        print('python file')
    else:
        print('sorry no python')
        # 3. 比出最大值
    data = [
        {'name': 'A', 'age': 64},
        {'name': 'B', 'age': 28},
        {'name': 'C', 'age': 36},
        {'name': 'D', 'age': 15},
    ]
    min(item['age'] for item in data)
    	# 4. 输出 CSV
    s = ['i', 'love', 'a', 'girl']
    print(','.join(item) for item in s)
    
  • 分析为什么生成器表达式能直接作为函数的参数

    >>> nums = [1, 2, 3, 4, 5, 6]
    >>> s = sum(x * x for x in nums)
    >>> s
    91
    >>> s = sum((x * x for x in nums))
    >>> s
    91
    
    # !!! 有没有 () 效果都是一样的
    
  • 掌握通过用生成器表达式替换函数中的 key

    data = {
        'a': 20,
        'b': 25,
        'c': 15,
        'd': 30
    }
    min(data[item] for item in data)
    min(data, key=lambda k: data[k])
    

18,将多个字典合并成单个字典

  • 问题 :有多个字典或映射,在逻辑上将他们合并成一个单独的结构,执行某种特定的操作,比如查找键,值是否存在

  • 解决方案 :使用 collections.ChainMap 将两个字典从底层联系起来

    a = {'a': 1, 'b': 1}
    b = {'c': 1, 'b': 2}
    from collections import ChainMap
    c = ChainMap(a, b)
    len(c)
    list(c.keys())		# ['b', 'c', 'a']
    list(c.values())	# [1, 1, 1]
    
    • 如果有两个字典有相同的键,值以第一个字典的键为准

    • 如果要删除组合字典里面的键值对,只能移除第一个映射或者字典上

      del c['a']		# √
      del c['c']		# ×
      
上一篇:linux-跟踪ksh多个会话的命令的历史记录


下一篇:LeetCode题解之Maximum Depth of N-ary Tree