[数据结构与算法]Python实用编程技巧（一）

简介

• 这里将从数据结构、字符串、迭代器、文件IO、类与对象、多线程、装饰器等问题入手
• 以写代码为主，讲述实用编程技巧，不多谈概念（需要有较好基础）
• 面试可用！

数据结构

问题：过滤列表中的负数

• 一般的解决方案是列表循环（代码过于简单不写了）
• 1.使用列表解析

  import random
  
  alist = [random.randint(-10,10) for _ in range(10)] # 列表推导式/生成式
  print(alist)
  
  blist = [i for i in alist if i>=0]   # 列表解析
  print(blist)
  

• 2.使用filter

  import random
  
  alist = [random.randint(-10,10) for _ in range(10)]
  print(alist)
  
  gen = filter(lambda x:x>=0, alist)	# 返回生成器
  # next(gen)
  blist = list(gen)	# 列表构造方法
  print(blist)
  

• 顺便搞一下字典的相关操作

  # 学生成绩表
  adict = {'person%d'%i:random.randint(50,100) for i in range(1,11)}
  print(adict)
  
  bdict = {k:v for k,v in adict.items() if v>60}	# 字典还有keys() 和values()
  print(bdict)
  
  gen = filter(lambda item:item[1]>90, adict.items())   # 当只有一个形参时，多参数会以元祖形式传入
  bdict = dict(gen)
  print(bdict)
  
  # 匿名函数可以用变量接受并调用	
  calc = lambda x,y:x**y	# 返回值就是表达式的结果，不用return
  print(calc(2,5))
  

• 同理：集合也可以解析

问题：如何为元组的每个元素命名，提高可读性

• 元祖格式固定，对于确定字段的数据存储节省空间效率高
• 但是要通过index读取数据，比较烦
• 1.定义数值常量作为索引

  NAME = 0
  AGE = 1
  HOBBY = 2
  
  t1 = ('Roy', 18, 'basketball')
  print(t1[NAME])
  

• 2.使用枚举类

  from enum import IntEnum
  
  class PersonEnum(IntEnum):
      NAME = 0
      AGE = 1
      HOBBY = 2
  
  print(t1[PersonEnum.NAME])
  

• 3.较好的方法，使用collections.namedtuple具名元组

  from collections import namedtuple
  
  # 元祖名称typename(不重要)，字段名称
  Student = namedtuple('Person',['name', 'age', 'hobby'])
  t2 = Student('Roy', 18, 'basketball')   # 按字段顺序赋值
  print(isinstance(t2, tuple))    # True
  print(t2.name)	# 更像类的形式
  

问题：如何对字典排序

• 字典集合是无序的，就是说和存入顺序不一致
• 这里排序是根据字典的值进行的（并不是搞成存入顺序）
• 1.转换为元祖

  # 元组比大小：先比第一个，直接返回结果；第一个相等比第二个，类推
  print((3,2)>(1,3))  # True
  print((3,2)>(3,4))  # False
  
  adict = {k:random.randint(60,100) for k in 'abcdefg'}
  print(adict)
  alist = [(v,k) for k,v in adict.items()]
  print(alist)
  blist = sorted(alist)   # reverse=True 逆序
  print(blist)    # [(60, 'c'), (70, 'a'), (77, 'e'), (93, 'b'), (95, 'g'), (96, 'f'), (98, 'd')]
  
  # 除了列表生成器（解析），还可以用zip
  z = zip([1,2,3], [4,5,6])
  clist = list(z)
  print(clist)    # [(1, 4), (2, 5), (3, 6)] 看懂了吗
  dlist = list(zip(adict.values(), adict.keys()))
  print(dlist)
  sorted(dlist, reverse=True)
  

• 直接使用sorted函数和lambda

  # 使用匿名函数处理,得到比较时用的key
  alist = sorted(adict.items(), key=lambda item:item[1], reverse=True)
  print(alist)
  
  # 改造为带有排名的字典
  for i,(k,v) in enumerate(alist, 1): # (k,v) 才能拆包； 1表示i从1开始计数
      adict[k] = (i, v)
  print(adict)    # {'a': (6, 64), 'b': (7, 62), 'c': (5, 80), 'd': (3, 83), 'e': (1, 95), 'f': (2, 84), 'g': (4, 83)}
  

问题：找出列表中出现次数最多的三个元素

• 将列表转换为字典，值为0，再遍历计数

  alist = [random.randint(0,15) for _ in range(30)]   # 有重复
  print(alist)
  # 放入字典，键唯一，会去重
  adict = dict.fromkeys(alist, 0) # 值都是0
  print(adict)
  # 所以要根据列表的值遍历，增加计数
  for x in alist:
      adict[x] += 1
  print(adict)    # {8: 2, 6: 4, 7: 2, 0: 2, 1: 3, 12: 2, 4: 2, 2: 1, 15: 2, 14: 1, 5: 3, 9: 1, 11: 1, 10: 2, 13: 2}
  blist = sorted(adict.items(), key=lambda item:item[1], reverse=True)[:3]    
  print(blist)# [(9, 4), (2, 3), (14, 3)]
  # blist = sorted([(v,k) for k,v in adict.items()], reverse=True)[:3]  # 一定要v,k，元组比较
  # print(blist)# [(9, 4), (2, 3), (14, 3)]
  # blist = sorted(((v,k) for k,v in adict.items()), reverse=True)[:3]  # 元组生成器（推导式）
  

• 在很大的列表中排序是比较费时的！这里推荐使用堆

  import heapq
  # 学过数据结构知道，大根堆和小根堆；可以看我的CSDN《重学算法》
  clist = heapq.nlargest(3, ((v,k) for k,v in adict.items()))	# 转成元组列表，会根据v入堆
  print(clist)
  

• 使用Counter对象

  from collections import Counter
  c = Counter(alist)
  print(c.most_common(3)) # [(8, 4), (14, 4), (9, 4)]
  

问题：如何快速找到多个字典的公共键

• 使用列表生成器（解析）

  from random import randint, sample
  
  # 队员：abcdefg
  # 成绩：值
  adict = {k:randint(1,3) for k in sample('abcdefg', randint(3,6))}
  bdict = {k:randint(1,3) for k in sample('abcdefg', randint(3,6))}
  cdict = {k:randint(1,3) for k in sample('abcdefg', randint(3,6))}
  print(adict)    # {'g': 3, 'e': 1, 'a': 2}
  print(bdict)    # {'f': 2, 'e': 1, 'a': 3, 'b': 1, 'd': 2, 'g': 3}
  print(cdict)    # {'g': 2, 'f': 3, 'd': 2, 'a': 1, 'e': 2}
  # 得到三场都得分的队员
  alist = [k for k in adict.keys() if k in bdict.keys() and k in cdict.keys()]
  print(alist)    # ['a', 'g', 'e']
  

• 利用集合（set）的交集操作

  # 求交集
  s1 = adict.keys()
  s2 = bdict.keys()
  s3 = cdict.keys()
  print(s1)   # dict_keys(['c', 'd', 'g', 'a', 'e'])
  print(type(s1)) # <class 'dict_keys'> 这不是列表
  print(s1&s2)    # {'b', 'g', 'd', 'c', 'a'} 这是个集合
  
  # reduce函数
  from functools import reduce	# python3中需要导包
  sub = reduce(lambda a,b:a*b, range(1,11))	# 每一次lambda计算的结果赋值给a，再次运算
  print(sub)  # 3628800
  
  # map函数
  def square(x):            # 计算平方数
      return x ** 2
  # 根据提供的函数对指定序列做映射    Python 3.x 返回迭代器
  map(square, [1,2,3,4,5])    # [1, 4, 9, 16, 25]
  
  # 求公共键
  s = reduce(lambda a,b:a&b, map(dict.keys, [adict,bdict,cdict]))
  print(s)    # 得到公共键
  # 完美！
  

问题：如何让字典保持有序

• 这里的排序不是根据之前的value，而是让字典元素按照添加顺序排序
• 这里使用OrderedDict

  from collections import OrderedDict
  from random import shuffle
  
  keys = 'abcdefg'
  od = OrderedDict()
  for i, v in enumerate(keys, 1):
      od[v] = i
  # 和输入顺序一致
  print(od)   # OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)])
  
  # 编写接口，按照索引返回顺序字典键（字典切片）
  from itertools import islice
  def queryByIndex(od, l,r=None):
      l -= 1  # 用户输入从1开始
      if r is None:
          r = l+1
      key_list = list(islice(od, l, r))   # islice返回字典键的切片迭代器
      return key_list
  
  alist = queryByIndex(od, 3,5)
  print(alist)
  

问题：如何实现用户的历史记录功能

• 使用容量为N的双端队列，python中提供了deque

  from collections import deque
  # 默认从左到右，右进左出，从左边挤出去
  queue = deque([], 4)    # maxlength=4
  queue.append(1)
  queue.append(2)
  queue.append(3)
  queue.append(4)
  queue.append(5)
  queue.pop() # 注意：弹出右边元素
  queue.popleft() # 弹出左边元素
  for i in queue:
      print(i)    # 3 4
  

• 双端队列建立在内存中，程序执行结束历史记录就会消失，我们可以使用pickle落盘

  import pickle
  pickle.dump(queue, open('q.pkl', 'wb'))	# 二进制读写
  q2 = pickle.load(open('q.pkl', 'rb'))
  print(queue)    # deque([3, 4], maxlen=4)
  print(q2)   # deque([3, 4], maxlen=4)
  

字符串

• 复杂场景下字符串问题的处理技巧

问题：如何拆分含有多种分隔符的字符串

• 连续使用str.split()方法，借助map方法

  str = 'ab,cd;efg|hig,klmn'
  
  t = []
  list(map(t.extend, [ss.split('|') for ss in str.split(',')]))
  print(t)
  
  alist = sum([ss.split('|') for ss in str.split(',')], [])   # 空列表是传入的初值，默认为0，但是和前面的列表类型不匹配！
  print(alist)    # ['ab', 'cd;efg', 'hig', 'klmn']
  

• 封装一个接口实现上面的功能

  def my_split(str, splitList):
      '''
      指定分隔符分割字符串
      :param str: 被分割
      :param splitList: 分隔符列表
      :return:
      '''
      res = [str]
      for sp in splitList:
          t = []
          list(map(lambda ss:t.extend(ss.split(sp)), res))
          res = t	# map和lambda可以迭代处理可迭代对象！
      return res
  
  str = my_split(str, [',', ';', '|'])
  print(str)  # ['ab', 'cd', 'efg', 'hig', 'klmn']
  

• 使用re的split模块

  import re
  str1 = re.split('[,;|]', str)	# 注意第一个参数是列表字符串
  print(str1) # ['ab', 'cd', 'efg', 'hig', 'klmn']
  

问题：如何判断字符串a是否以字符串b开头或结尾

• 使用 str.startswith()和str.endswith()方法，返回True/False
• 多个匹配时参数用元组传入
• 外番：使用os包修改文件权限的故事~（chmod）

问题：如何调整字符串中文本的格式

• 案例：将文件中日期格式2021-10-01改为美国时间mm/dd/yyyy
• 使用正则的re.sub方法替换

  import re
  
  str = '2021-10-03'
  # str1 = re.sub(r'(\d{4})-(\d{2})-(\d{2})',r'\2/\3/\1' ,str)  # 使用r避免python进行转义，导致re模块出错
  str1 = re.sub(r'(?P<y>\d{4})-(?P<m>\d{2})-(?P<d>\d{2})',r'\g<m>/\g<d>/\g<y>' ,str)  # 另一种写法 分组别名 使用时要用\g<>
  print(str1) # 10/03/2021
  

问题：如何将多个小字符串拼接成大字符串

• 将列表中的所有字符串元素拼接，最常见的还是+操作

  s1 = 'abcde'
  s2 = '|fghj'
  # 使用+拼接本质是对+进行重载
  s3 = s1.__add__(s2)
  print(s1)   # abcde
  print(s3)   # abcde|fghj    会产生新对象！
  

• “累加”操作，也可以使用reduce方法

  from functools import reduce
  s = ['acd','def','ghi']
  str = reduce(str.__add__, s)
  print(str)  # acddefghi
  

• 上面的方法是有问题的！每次拼接一个子串后会得到新的子串，之前的子串对象不再使用，时间空间都浪费巨大；这里使用join()方法（推荐！）

  s = ['acd','def','ghi']
  str = ';'.join(s)	# 可以使用 ''.join(s)
  print(str)  # acd;def;ghi
  # 这里相当于创建空间，将列表各元素放入，一次到位
  

问题：如何将字符串对齐

• 使用字符串的函数

  s = 'abcd'
  s1 = s.ljust(6, '*')	# 使用* 填充到6个字符
  print(s1)	# abcd**
  s2 = s.rjust(6,'*')		# 字符串放在右边填充
  print(s2)	# **abcd
  s3 = s.center(6,'*')
  print(s3)   # *abcd*
  

• 使用format方法

  s4 = format(s, '+>6')   # >功能和rjust相同，类似的 < 左对齐， ^ 居中对齐
  print(s4)	# ++abcd
  s5 = format(s, '+^6')
  print(s5)   # +abcd+
  

• 可能我们最常见的还是使用format输出

  print("{1} {0} {1}".format("hello", "world"))	# 位置传参
  print("网站名：{name}, 地址 {url}".format(name="Roy", url="www.roykun.com"))	# 键值传参
  

问题：如何去掉字符串中不需要的字符

• 使用字符串的方法

   s = '   abcde    '
  s1 = s.lstrip()
  print(s1)   # abcde
  s2 = s.rstrip()
  print(s2)   #    abcde
  s3 = s.strip()
  print(s3)   # 去掉两端空白字符
  
  str = '+\tabcdef\n*-'
  s4 = str.strip('+\t\n-*')
  print(s4)   # abcdef
  

• 但是不能处理中间的字符，可以使用replace方法

  str = '   abc    def   gh   '
  s1 = str.replace(' ', '')	# 只能去掉一种
  print(s1)   # abcdefgh
  
  # 当然，最靠谱的还是正则替换
  import re
  str1 = ' \tabcd  \nfg * \t hij'
  s2 = re.sub('[ \t\n*]+', '', str1)
  print(s2)   # abcdfghij
  

• translate方法

  str = 'abcd'
  s1 = str.translate({ord('a'):'A'})  # 字典形式的映射表，键需要Unicode编码的
  print(s1)   # Abcd
  str.translate(str.maketrans('abc', 'ABC'))  # maketrans直接求第一个参数的ord与第二个参数组成字典映射
  

对象迭代

• 如何实现对象迭代和反迭代

问题：如何实现可迭代对象和迭代器对象

• 先从for循环说起

  from collections import Iterable, Iterator
  alist = [1,2,3,4,5]
  print(isinstance(alist, Iterable))  # True 可迭代对象
  
  for i in alist:
      print(i)
  
  it = iter(alist)    # 传入可迭代对象，产生迭代器对象 Iterator
  print(next(it)) 	# 1 使用迭代器
  

  • for循环中in后面必须是可迭代对象，默认调用iter方法得到迭代器，再使用next方法每次获取元素，知道迭代完抛出StopIterator异常
  • 迭代器是一次性的，消费完了就要重新iter
• 自定义迭代器，迭代获取列表中多个城市天气的数据

  from collections import Iterable, Iterator
  import requests
  
  class WeatherIterator(Iterator):
      def __init__(self, citys):
          self.citys = citys    # 查询的城市
          self.index = 0      # 迭代索引
  
      # 迭代器类要实现next方法，获取下一个
      def __next__(self):
          if self.index == len(self.citys):
              raise StopIteration
          city = self.citys[self.index]
          self.index += 1	# 迭代器的本质，取下一个
          # print(self.index)
          return self.get_weather(city)
  
      def get_weather(self, city):
          url = 'http://wthrcdn.etouch.cn/weather_mini?city=%s'%city
          r = requests.get(url)
          # print(r.text)  # json字符串
          data = r.json()['data']['forecast'][0]  # 只取今天
          # print(data)
          return city, data['high'], data['low']
  
  class WeatherIterable(Iterable):
      def __init__(self, citys):
          self.citys = citys
  
      # 可迭代对象类要实现iter方法，返回迭代器
      def __iter__(self):
          return WeatherIterator(self.citys)
  
  def show(w):
      for i in w:
          print(i)
  
  w = WeatherIterable(['北京', '上海', '天津']) # 有些城市没有，比如宁夏
  show(w)	# 可以直接实例化迭代器对象不经过Iterable，但是这样的迭代器只能使用一次，不能再次show
  show(w)
  

  • 直接使用iter方法得到的迭代器对象就是一次性的！相当于一个泛型的返回迭代器对象的方法
  • 需要注意这两种方式的不同！

问题：如何使用生成器函数实现可迭代对象

• 生成器是一种特殊的迭代器，生成器函数是使用yield关键字的函数
• 我们这里编写一个求素数的类
  
  • all() 函数用于判断给定的可迭代参数 iterable 中的所有元素是否都为 TRUE，如果是返回 True，否则返回 False
• 编写测试函数
  
• 很好理解，next方法会继续运行yield后面的语句，效果上和自定义的__next__相同
• 相当于可迭代对象类和迭代器类一起定义了！
• 可迭代对象(iter/__iter__)与迭代器(next/__next__)的故事到此为止！

问题：如何实现反向迭代

• 如何反向输出一个列表？

  alist = [1,2,3,4,5,6]
  alist.reverse() # 基于原列表操作
  for i in alist:
      print(i)
  
  # 方案2
  print(alist[::-1])	# 会产生新的列表
  
  # 方案3
  ralist = reversed(alist)
  print(type(ralist)) # <class 'list_reverseiterator'>
  # 这就是反向迭代器，底层实现__reversed__方法
  for i in ralist:
      print(i)
  

• 如何实现一个浮点数发生器FloatRange？

  class FloatRange(Iterable):
      def __init__(self, a, b, step):
          self.a = a
          self.b = b
          self.step = step    # 步长
  
      def __iter__(self):
          t = self.a
          while t<self.b:
              yield t
              t += self.step
  
      def __reversed__(self):
          t = self.b
          while t>self.a:
              yield t
              t -= self.step
  
  fr = FloatRange(3.0, 4.0, 0.2)
  for x in fr:
      print(x)
  print('------------------')
  for i in reversed(fr):
      print(i)
  # 3.0
  # 3.2
  # 3.4000000000000004
  # 3.6000000000000005
  # 3.8000000000000007
  # 4.0
  # 3.8
  # 3.5999999999999996
  # 3.3999999999999995
  # 3.1999999999999993
  

  • 这是一个很长见的问题，浮点数默认以二进制存储，本身是有误差的，需要使用Decimal转为十进制运算

  from decimal import Decimal
  class FloatRange(Iterable):
      def __init__(self, a, b, step):
          self.a = Decimal(str(a))	# 传入字符串类型
          self.b = Decimal(str(b))
          self.step = Decimal(str(step))    # 步长
  
      def __iter__(self):
          t = self.a
          while t<self.b:
          	# print(type(t))  # <class 'decimal.Decimal'>
              yield float(t)	# 将返回的t转型	也可不转
              t += self.step
  
      def __reversed__(self):
          t = self.b
          while t>self.a:
              yield float(t)
              t -= self.step
  
  fr = FloatRange(3.0, 4.0, 0.2)
  for x in fr:
      print(x)
  print('------------------')
  for i in reversed(fr):
      print(i)
  

  • 注意：Decimal需要传入字符串类型，因为浮点数本身就是不精确的

问题：如何对可迭代对象做切片操作

• 一个500行的日志文件，open之后是可迭代对象，能否取到100-300行的数据？
• 切片的实质是实现了__getitem__方法，其中调用了slice方法

  # 使用readlines()会将所有数据加载到内存，很占用资源
  # 所以要使用迭代器切片！ei~既切片又迭代
  f = open('opera.txt', 'r', encoding='utf8')	# 注意字符编码问题，视操作系统，默认gbk需要转成utf8
  flist = f.readlines()   # 得到列表
  print(flist)
  
  from itertools import islice
  f.seek(0)   # 文件指针回退
  fs = islice(f, 2, 3)    # 上面的readlines将打开的f句柄读到了末尾
  for i in fs:
      print(i)
  

• 自定义切片方法

  def my_islice(file, start, end, step=1):
      tmp = 0 # 临时计数器     步长
      for i, f in enumerate(file):    # 索引从0开始
          if i >= end:    # 取头不取尾
              break
          if i >= start:
              if tmp==0:
                  tmp = step
                  yield f
              tmp -= 1
  fsm = my_islice(f, 2, 3)
  print(list(islice(range(0,10), 2, 8, 2)))  # [2, 4, 6]
  print(list(my_islice(range(0,10), 2, 8, 2)))   # [2, 4, 6]
  

• 从我们自定义的方法也可以看出，从中间开始切还是会迭代前面的元素的！

问题：如何在一个for语句中迭代多个对象

• 案例：语文数学英语三科成绩同时迭代统计每个学生的总分
• 可以使用zip打包

  import random
  chinese = [random.randint(60, 100) for x in range(10)]
  math = [random.randint(60, 100) for x in range(10)]
  English = [random.randint(60, 100) for x in range(10)]
  print(chinese, math, English)
  alist = list(zip(chinese, math, English))
  print(alist)
  score = []
  for c, m, e in alist:
      score.append(c+m+e)
  print(score)
  
  # 使用map实现相同功能
  blist = list(map(lambda c, m, e:c+m+e, chinese, math, English)) # 也是分别从三个列表取
  print(blist)
  # map也可以实现zip的功能
  clist = list(map(lambda *args:args, chinese, math, English) ) # *args默认打包成元组
  print(clist)
  

• 上面是并行统计的，如果要串行，可以使用chain方法优雅的串起多个容器，返回迭代器！

  from itertools import chain
  dlist = list(chain(*[[2,3], [4,5,6], [6,7,8]])) # 列表列表需要使用*打散
  print(dlist)	# [2, 3, 4, 5, 6, 6, 7, 8]
  

小结

• 问题还将继续，技巧繁多，只有领会到python编程的风格才能熟稔于心！
• 可迭代对象和迭代器的知识，以及生成器的使用是难点