1 list 列表

1.1 多维列表初始化

假设现在我们要初始化一个元素都为 0 三维 list（更高维的同理），有两种方式：

  1. 嵌套定义

    1. # dim_i 代表 list 每一个维度的元素数量
    2. >>> dim1, dim2, dim3 = 3, 4, 5
    3. >>> lst1 = [ [ [0] * dim3 ] * dim2 ] * dim1

  2. 循环定义

    1. # dim_i 代表 list 每一个维度的元素数量
    2. >>> dim1, dim2, dim3 = 3, 4, 5
    3. >>> lst2 = [ [ [0] * dim3 for j in range(dim2) ] for i in range(dim1)]

乍一眼看起来，第一种方式更加简便，其实不然，这里有一个大坑：

  1. >>> lst1[1][1][2] = 111
  3. >>> lst1
  4. [[[0, 0, 111, 0, 0], [0, 0, 111, 0, 0], [0, 0, 111, 0, 0], [0, 0, 111, 0, 0]],
  5.  [[0, 0, 111, 0, 0], [0, 0, 111, 0, 0], [0, 0, 111, 0, 0], [0, 0, 111, 0, 0]],
  6.  [[0, 0, 111, 0, 0], [0, 0, 111, 0, 0], [0, 0, 111, 0, 0], [0, 0, 111, 0, 0]]]

我们发现 lst[*][*][2] 都被修改成了 111。而第二种方式就不会：

  1. >>> lst2[1][1][2] = 111
  3. >>> lst2
  4. [[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]],
  5.  [[0, 0, 0, 0, 0], [0, 0, 111, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]],
  6.  [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]]

具体原因就是，Python 中一切皆对象，所以变量存储的也都是对象的引用。嵌套定义中，最内层的 list 没有问题，因为存的都是普通变量的引用，Python 跟 Java 一样，对于值相同的普通变量都使用相同的引用（所以用 id() 函数查看最内层 list 所有的元素的地址，都是一样的）：

  1. >>> l = [1 for _ in range(5)]
  2. >>> for i in l:
  3. ...       print(id(i))
  4. 140710307309344
  5. 140710307309344
  6. 140710307309344
  7. 140710307309344
  8. 140710307309344

如果修改了一个元素，那地址就不一样了：

  1. >>> l[1:3] = [2, 2]
  2. >>> l[3:] = [3, 3]
  4. >>> for i in l:
  5. ...        print(id(i))
  6. 140710307309344
  7. 140710307309376
  8. 140710307309376
  9. 140710307309408
  10. 140710307309408

而外面两层的 list 就有问题了，因为*运算符对于 list 而言，就是拷贝，所以相同 list 的引用就被拷贝了。所以在执行 dp[i][j][k] = 111 时，相当于将所有的 dp[*][*][k] 都改成了 111。
而第二种定义中，在每一个 range() 循环中 list 都是新创建的，地址不同。

  1. >>> for lst in lst1:
  2. ...        print(id(lst))
  3. 2229828960768
  4. 2229828960768
  5. 2229828960768
  7. >>> for lst in lst2:
  8. ...     print(id(lst))
  9. 2229834800384
  10. 2229830061056
  11. 2229834368576

所以，以后还是老实使用循环定义来初始化 list 吧。

1.2 自定义排序规则

在 Python 中，实现对 list 的排序有两种方法：

  • 使用 Python 的内置函数 sorted() —- 创建一个新的 list，其内容为原 list 排序后的结果；
  • 使用 list 类的成员方法 sort() —- 在原 list 上（in-place）进行排序。 ```python

    lst = [3, 4, 2, 1]

lst_s = sorted(lst)

id(lst_s) 1524928932672

id(lst) 1524929164160 # 发现两个 list 的地址不同

lst [3, 4, 2, 1]

lst_s [1, 2, 3, 4]

lst.sort()

lst [1, 2, 3, 4]

id(lst) 1524929164160 # 与之前 list 的地址相同 ```

不管是 sorted() 函数还是 sort() 方法，它们的参数表一样，都可以接受一个参数 key 来让用户指定排序规则，这个 key 就是我们应该传入的排序函数或者类。但是这个 key 不同于 C++ 或者其他语言中的 compare 函数，我们自定义的 key 函数应该返回待排序的关键字，而不是排序的规则，比如我现在希望按照整数的个位数从小到大排序：

  1. >>> lst = [19, 25, 22, 27]
  3. >>> lst.sort(key=lambda x : x % 10)
  5. >>> lst
  6. [22, 25, 27, 19]

sort() 函数默认按照关键字从小到大的顺序进行排序，所以 key 函数返回的是关键字，而不是像下面这样返回排序规则：

  1. def cmp(lhs: int , rhs: int):
  2.     # C++ 中的写法:
  3.     # return lhs % 10 < rhs % 10
  4.     # Python 中的写法:
  5.     return (lhs % 10) - (rhs % 10)

这里可以提一嘴 Python 与 C++ 中比较大小的方式：

  • Python 中如果返回 <0 的数，代表小于；返回 0 代表等于；返回 >0 的数代表大于，返回一个整数；那么大于等于和小于等于同理啦；
  • C++ 中自定义排序规则只需要重载 **<** 运算符或者 **()** 运算符，返回值都是带比较的左值是否小于右值，返回的是一个 bool 变量。

所以当排序规则只涉及一个值时，向 key 传入一个能够返回关键字的函数就可以，但如果比较涉及多个值就麻烦了，比如现在有一个存储学生信息的 list，每个学生的信息由年龄 age 和身高 height 两个字段组成，我们希望先按照年龄升序排列，如果年龄相同则按照身高升序排列。这就需要用到 Python 内置库函数 functools.cmp_to_key。

  1. from functools import cmp_to_key
  3. def cmp(lhs: dict, rhs: dict):
  4.     if lhs['age'] == rhs['age']:
  5.         if lhs['name'] < rhs['name']:
  6.             return -1
  7.         if lhs['name'] > rhs['name']:
  8.             return 1
  9.         else:
  10.             return 0
  11.     else:
  12.         return lhs['age'] - rhs['age']
  14. students = [{'age': 21, 'name': 'RTt'},
  15.             {'age': 19, 'name': 'DL'},
  16.             {'age': 19, 'name': 'CE'}]
  18. stu_sorted = sorted(students, key=cmp_to_key(cmp))
  19. print(stu_sorted)
  21. [{'age': 19, 'name': 'CE'},
  22.  {'age': 19, 'name': 'DL'},
  23.  {'age': 21, 'name': 'RTt'}]

cmp_to_key() 函数的源码如下：主要是使用类内的成员函数 __lt__ 等重载了 < 等运算符。

  1. def cmp_to_key(mycmp):
  2.     """Convert a cmp= function into a key= function"""
  3.     class K(object):
  4.         __slots__ = ['obj']
  5.         def __init__(self, obj):
  6.             self.obj = obj
  7.         def __lt__(self, other):
  8.             return mycmp(self.obj, other.obj) < 0
  9.         def __gt__(self, other):
  10.             return mycmp(self.obj, other.obj) > 0
  11.         def __eq__(self, other):
  12.             return mycmp(self.obj, other.obj) == 0
  13.         def __le__(self, other):
  14.             return mycmp(self.obj, other.obj) <= 0
  15.         def __ge__(self, other):
  16.             return mycmp(self.obj, other.obj) >= 0
  17.         __hash__ = None

当然，使用 key 函数，返回关键字也可以实现涉及多个值的排序规则：

  1. >>> stu_sorted = sorted(students, key=lambda x: (x['age'], x['name']))
  2. [{'age': 19, 'name': 'CE'},
  3.  {'age': 19, 'name': 'DL'},
  4.  {'age': 21, 'name': 'RTt'}]