Python基础容器

一、列表

查找

• L.index(v)

• L.index(v , begin)

• L.index(v , begin, end)

  返回对应元素的索引下标, begin为开始索引，end为结束索引,当 value 不存在时触发ValueError错误

• L.count(x)

  用于统计某个元素在列表中出现的次数

• L.pop([index])

  删除索引对应的元素，如果不加索引，默认删除最后元素，同时返回删除元素的引用关系

修改

• L.insert(index, obj)

  将某个元素插放到列表中指定的位置

  有序列表的查找和插入

  # python内置bisect(对分)模块
  >>> import bisect
  >>> list1 = [1,2,3,4,6,7,10]  // 这是一个有序序列
  >>> bisect.bisect(list1, 5)  // 返回5应该在list1中的索引
  4
  >>> list1  // 但list1没变
  [1, 2, 3, 4, 6, 7, 10]
  >>> bisect.insort(list1, 5)   // 这里是insort， 不是insert, 
  >>> list1
  [1, 2, 3, 4, 5, 6, 7, 10]    // list1 结果变了
  >>> list1.insert(0, 8)     // list的insert操作不要求列表有序
  >>> list1
  [8, 1, 2, 3, 4, 5, 6, 7, 10]
  >>> list1.insert(8, 8)
  >>> list1
  [8, 1, 2, 3, 4, 5, 6, 7, 8, 10]

• L.extend(lst)

  向列表追加另一个列表

• L.remove(x)

  从列表中删除第一次出现在列表中的值 x

• L.clear()

  清空列表,等同于 L[:] = []

• L.sort(reverse=False)

  将列表中的元素进行排序，默认顺序按值的小到大的顺序排列

• L.reverse()

• 列表的反转，用来改变原列表的先后顺序

拷贝

• L.copy()

  复制此列表（只复制一层，不会复制深层对象)

获取前k大的索引

• 获取前k大的索引

通过累加函数构建前缀和列表

S = list(accumulate(nums, initial=0))
# S[Right] - S[Left] 表示区间[Left, Right)的元素和 

二、字典

查找

• get(key, default=None)
  返回指定键的值，如果值不在字典中返回default值

• setdefault(key, default=None)
  和get()类似, 但如果键不存在于字典中，将会添加键并将值设为default

• popitem()
  随机返回并删除字典中的一对键和值(一般删除末尾对)。

• items()
  以列表返回可遍历的(键, 值) 元组数组

• keys()
  返回一个迭代器，可以使用 list() 来转换为列表

• values()
  返回一个迭代器，可以使用 list() 来转换为列表

修改

• update(dict2)
  字典记录累加，把字典参数 dict2 的 key/value(键/值) 对更新到字典 dict 里。

• clear()

  删除字典内所有元素

• del dic[key]

  删除字典内单个元素

获取最大值的索引

• 获取最大值/最小值的键

  • max_key = max(my_dic, key=my_dic.get)
  • min_key = min(my_dic, key=my_dic.get)

• 获取最大值/最小值及其键

  • max_item = max(zip(my_dic.values(), my_dic,keys()))
  • min_item = min(zip(my_dic.values(), my_dic.keys()))
  • zip():将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，返回由这些元组组成的列表。如果各个迭代器的元素个数不一致，则返回列表长度与最短的对象相同。

键相同值相加的几种方法

# 方法1
from collections import Counter
dict1 = {'a': 1, 'b': 2}
dict2 = {'a': 2, 'b': 4}
x, y = Counter(dict1), Counter(dict2)
result = dict(x+y)
print(result)
输出：
{'a': 3, 'b': 6}

# 方法2
A = {'a': 1, 'b': 2, 'c': 3}
B = {'b': 4, 'c': 6, 'd': 8}
for key,value in B.items():
	if key in A:
		A[key] += value
	else:
		A[key] = value
dict(sorted(A.items(), key=lambda d:d[1]))

# 方法3
A = {'a': 1, 'b': 2, 'c': 3}
B = {'b': 4, 'c': 6, 'd': 8}
C = {}
for key in list(set(A) | set(B)):
	if A.get(key) and B.get(key):
		C.update({key: A.get(key) + B.get(key)})
	else:
		C.update({key: A.get(key) or B.get(key)})
print(C)

# 方法4
A = {'a': 1, 'b': 2, 'c': 3}
B = {'b': 4, 'c': 6, 'd': 8}
def dict_union(d1, d2):
	keys = d1.keys() | d2.keys()
	temp = {}
 	for key in keys:
	temp[key] = sum([d.get(key,0) for d in (d1, d2)])
	return temp
C = dict_union(A, B)
print(C)

# 方法5
A = {'a': 1, 'b': 2, 'c': 3}
B = {'b': 4, 'c': 6, 'd': 8}
C = {}
for key1 in A:
	for key2 in B:
		if key1 in B:
			C[key1] = A[key1] + B[key1]
		else:
			C[key1] = A[key1]
		if key2 not in A:
			C[key2] = B[key2]
print(C)

# 方法6
A = {'a': 1, 'b': 2, 'c': 3}
B = {'b': 4, 'c': 6, 'd': 8}
C = {}
for key in A:
	if B.get(key):
		C[key] = A[key] + B[key]
	else:
		C[key] = A[key]
for key in B:
	if not A.get(key):
		C[key] = B[key]
print(C)

三、集合

• update()

  给集合添加元素

• clear()

  移除集合中的所有元素

• copy()

  拷贝一个集合

• pop()

  随机移除元素

四、字符串

判断

• isspace()

  如果字符串中只包含空白，则返回 True，否则返回 False.

• startswith(substr, beg=0, end=len(string))

  检查字符串是否是以指定子字符串 substr 开头，是则返回 True，否则返回 False。如果beg 和 end 指定值，则在指定范围内检查。

• endswith(suffix, beg=0, end=len(string))

  检查字符串是否以 obj 结束，如果beg 或者 end 指定则检查指定的范围内是否以 obj 结束，如果是，返回 True,否则返回 False.

查找

• find(str, beg=0 end=len(string))

  检测 str 是否包含在字符串中，如果指定范围 beg 和 end ，则检查是否包含在指定范围内，如果包含返回开始的索引值，否则返回-1

• rfind(str, beg=0,end=len(string))

  类似于 find()函数，不过是从右边开始查找.

• count(str, beg= 0,end=len(string))

  里面出现的次数，如果 beg 或者 end 指定则返回指定范围内 str 出现的次数

修改

• replace(old, new [, max])

  把 将字符串中的 str1 替换成 str2,如果 max 指定，则替换不超过 max 次。

• lstrip()

  截掉字符串左边的空格或指定字符。

• rstrip()

  删除字符串字符串末尾的空格.

• strip([chars])

  在字符串上执行 lstrip()和 rstrip()

• lower()

  转换字符串中所有大写字符为小写.

• upper()

  转换字符串中的小写字母为大写

• swapcase()

  将字符串中大写转换为小写，小写转换为大写

对齐

• center(width, fillchar)

  返回一个指定的宽度 width 居中的字符串，fillchar 为填充的字符，默认为空格。

• zfill (width)

  返回长度为 width 的字符串，原字符串右对齐，前面填充0

• ljust(width[, fillchar])

  返回一个原字符串左对齐,并使用 fillchar 填充至长度 width 的新字符串，fillchar 默认为空格。

分割

• str.split(‘分割符’)

  将str按指定的一个分隔符进行分割

• re.split(‘分割符1|分割符2|…’, str) 或 re.split(r’[分割符1, 分割符2, …]’, str)

  ​ 将str按指定的一些分隔符进行分割，不保留分隔符

• re.split(‘(分割符1|分割符2|…)’, str) 或 re.split(r’([分割符1, 分割符2, …])’, str)

  ​ 将str按指定的一些分隔符进行分割，保留分隔符

数组转化为字符串，再还原为数组

# 例如：[1, 12, 3, 4] => '1,12,3,4' => [1, 12, 3, 4]
a = [1, 12, 3, 4]
b = ','.join(map(str, a))
c = list(map(int, b.split(',')))

五、二分查找标准库bisect

Python的标准库bisect支持了二分查找算法，可以使用二分查找在有序列表中查询或插入元素。

函数

• bisect_left(a, x, lo=0, hi=len(a))：寻找目标元素出现的最左侧位置的索引
• bisect_right(a, x, lo=0, hi=len(a))：寻找目标元素出现的最右侧位置的索引**+1**（注意当目标位置为列表末尾时，返回的索引在列表中不存在）
• insort_left(a, x, lo=0, hi=len(a))：将新元素插入到目标元素出现的最左侧位置的左侧
• insort_right(a, x, lo=0, hi=len(a))：将新元素插入到目标元素出现的最右侧位置的右侧

参数

• a : 允许存在重复值的递增列表（参数类型：需要支持insert、__len__、__item__方法）
• x : 需要查找的目标元素或需要插入的新元素（参数类型：需要支持__lt__方法）
• lo : 二分查找范围的左侧边界（包含边界元素）
• hi : 二分查找范围的右侧边界（不包含边界元素）

1. bisect_left和bisect_right的用法

array = [0, 2, 2, 2, 5]
print("bisect_left:", bisect.bisect_left(array, 2))  # 1 (结果为第1个出现的“2”的索引)
print("bisect_right:", bisect.bisect_right(array, 2))  # 4 (结果为最后1个出现的“2”的索引+1)
123

2. lo参数和hi参数的用法

array = [0, 1, 2, 3, 4, 5, 6]
print("bisect_left:", bisect.bisect_left(array, 0, lo=2))  # 2 (查找范围为第2个到最后1个，因此没有0出现，结果为最左侧的位置)
print("bisect_right:", bisect.bisect_left(array, 6, hi=5))  # 5 (查找范围为第1个到第5个，因此6没有出现，结果为最右侧的位置)
123

3. 当查找的元素不存在于列表中时

array = [1, 2, 4, 8, 16]
print("bisect_left:", bisect.bisect_left(array, 5))  # 3 (结果为大于目标元素的第1个元素的索引)
print("bisect_right:", bisect.bisect_right(array, 5))  # 3 (结果为大于目标元素的第1个元素的索引)
123

4. insort_left和insort_right的用法

我们用支持大小比较的整数和浮点数来区别列表中的数和新插入的数。

array = [0, 2, 2, 2, 5]
bisect.insort_left(array, 2.00)
print(array)  # [0, 2.0, 2, 2, 2, 5] (将2.00插入到了第1个出现的“2”的左侧)
123
array = [0, 2, 2, 2, 5]
bisect.insort_right(array, 2.00)
print(array)  # [0, 2, 2, 2, 2.0, 5] (将2.00插入到了最后1个出现的“2”的右侧)
123

5. 当插入的元素不存在于列表中时

array = [1, 2, 4, 8, 16]
bisect.insort_left(array, 5)
print(array)  # [1, 2, 4, 5, 8, 16] (将5插入到了4和8之间)
123
array = [1, 2, 4, 8, 16]
bisect.insort_right(array, 5)
print(array)  # [1, 2, 4, 5, 8, 16] (将5插入到了4和8之间)

综上，我们可以对调用方法作出如下总结：

• 当需要查找或插入的元素不存在时，bisect_left和bisect_right、insort_left和insort_right没有区别；
• bisect_right返回的索引是最后1个出现元素的索引+1

---

下面我们来看性能。因为bisect_left和bisect_right、insort_left和insort_right在时间、空间的利用上没有区别，因此可以合并处理。

依据函数源代码，我们可以计算出两个函数的渐进性能如下表。其中N表示元素的长度，K表示目标元素的索引。

操作	运行时间
bisect	O ( l o g N ) O(logN)O(log**N)
insort	O ( l o g N + ( N − K ) ) O(logN+(N-K))O(log**N+(N−K)) : 其中L o g N LogNLog**N为找到插入位置的时间，N − K N-KN−K为插入元素的时间

从性能上来说，insort函数并不适合频繁使用

有时，我们可能需要在向列表中插入元素的同时，计算当前列表中小于（或大于）插入元素的元素数量。这种情况下如果使用二分查找依次插入每一个元素，那么每次使用insort函数插入元素都需要O ( N ) O(N)O(N)的时间复杂度，总计需要O ( N 2 ) O(N^2)O(N2)的时间复杂度，这样的效率是比较低的。这时我们需要考虑使用树状数组或线段树，在O ( N l o g N ) O(NlogN)O(Nlog**N)的时间复杂度内解决这个问题。

最后，我们看一下实际运行的效率。因为bisect模块中的方法在cpython中是直接由C语言实现的（bisect模块的函数在实现上引用自_bisect模块，引用的函数将会覆盖引用前的同名函数），因此其运行效率明显高于由Python原生代码实现的运行效率。具体运行效率差异可以参考下表中的几个测试（timeit模块计算）。

操作	循环次数	cpython	Python
bisect_left([i for i in range(10000)], 1234)	1000000	0.3297	1.9943
bisect_left([i for i in range(100000)], 12345)	1000000	0.3127	2.5913
insort_left([i for i in range(10000)], 1234)	100000	2.3006	2.4779