Python厨书笔记-1

数据结构与算法（一）

1. 数据结构与算法

2. 1. 解压可迭代对象赋值

用途

  • 解压不确定个数或任意个数元素的可迭代对象
  • 字符串的分割
1
2
3
4
5
6
7
8
9
10
# list or string or tuple，not set
x = [1,2,3]
try:
    # 取首
	y,*_ = x
	# 取尾
	*_,y = x
except:
    # 可迭代对象的元素个数超过变量个数
    raise ValueError
1
2
3
4
5
6
7
8
>>> line = 'nobody:*:-2:-2:Unprivileged User:/var/empty:/usr/bin/false'
>>> uname, *fields, homedir, sh = line.split(':')
>>> uname
'nobody'
>>> homedir
'/var/empty'
>>> sh
'/usr/bin/false'

3. 2. 保留最后 N 个元素

用途

  • deque.popleft()相当于list.pop(0)，但要更快
  • deque(maxlen=N)用于构建固定大小的队列——当新的元素加入并且这个队列已满的时候， 最老的元素会自动被移除掉
1
2
3
4
5
6
>>> x=deque(maxlen=2)
>>> x.append(1)
>>> x.append(2)
>>> x.append(3)
>>> x
deque([2, 3], maxlen=2)

4. 3. 查找最大或最小的 N 个元素

用途

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

heapq.nlargest()、heapq.nsamllest()

1
2
3
4
5
6
7
8
In [1]: import heapq

In [2]: x=[1.1,2.2,3.3]

In [3]: y=heapq.nlargest(1,x,lambda n: int(n))

In [4]: print(y)
[3.3]

5. 4. 优先级队列

用途

  • 构建优先级队列

优先级队列$\neq$堆

👆这才是堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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]
    # push 和 pop 操作时间复杂度为 O(log N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
In [8]: x=PriorityQueue()

In [9]: x.push('zh-cn',1)

In [10]: x.push('zh-hans',2)

In [11]: x.push('zh-hk',3)

In [12]: pp(x)
instance(PriorityQueue):
  _index: 3,
  _queue: [
    (-3, 2, 'zh-hk'),
    (-1, 0, 'zh-cn'),
    (-2, 1, 'zh-hans'),
  ]

In [13]: x.pop()
Out[13]: 'zh-hk'

6. 5. 一键多值的字典

defaultdict(list/set/int)

7. 6. 有序字典

用途

  • 在迭代操作的时候它会保持元素被插入时的顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
In [1]: from collections import OrderedDict

In [2]: d = OrderedDict()

In [3]: d['bar'] = 2

In [4]: d['foo'] = 1

In [5]: pp(d)
{
  'bar': 2,
  'foo': 1,
}

In [6]: for key in d:
   ...:     print(key,d[key])
   ...:
bar 2
foo 1
  • OrderedDict 内部维护着一个根据键插入顺序排序的双向链表
  • 一个 OrderedDict 的大小是一个普通字典的两倍，因为它内部维护着另外一个链表。所以大型数据不要用

8. 7. 字典运算

用途

  • 对字典value进行计算操作（比如求最小值、最大值、排序等等）
  • 注意 zip() 函数创建的是一个只能访问一次的迭代器
1
2
3
4
prices_and_names = zip(prices.values(), prices.keys())
min(prices_and_names) # OK
# min_price is (10.75, 'FB')
max(prices_and_names) # ValueError: max() arg is an empty sequence

9. 8. 字典集合操作

用途

  • 两个字典中寻寻找相同点（比如相同的键、相同的值等等）
  • keys()、items()都支持集合运算，但values()不支持
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
a = {
    'x' : 1,
    'y' : 2,
    'z' : 3
}

b = {
    'w' : 10,
    'x' : 11,
    'y' : 2
}
# Find keys in common
a.keys() & b.keys() # { 'x', 'y' }
# Find keys in a that are not in b
a.keys() - b.keys() # { 'z' }
# Find (key,value) pairs in common
a.items() & b.items() # { ('y', 2) }

# Make a new dictionary with certain keys removed
c = {key:a[key] for key in a.keys() - {'z', 'w'}}
# c is {'x': 1, 'y': 2}

10. 9. 删除重复

用途

  • 在一个序列上面保持元素顺序的同时消除重复的值
  • 利用生成器

不保留顺序

set()

保留顺序且hashable

1
2
3
4
5
6
7
8
9
10
11
12
# dedupe = delete duplicate
def dedupe(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
            seen.add(item)
         
>>> a = [1, 5, 2, 1, 9, 1, 5, 10]
>>> list(dedupe(a))
[1, 5, 2, 9, 10]
>>>

保留顺序但非hashable(如dict)

1
2
3
4
5
6
7
8
9
10
11
12
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)
>>> a = [ {'x':1, 'y':2}, {'x':1, 'y':3}, {'x':1, 'y':2}, {'x':2, 'y':4}]
>>> list(dedupe(a, key=lambda d: (d['x'],d['y'])))
[{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]
>>> list(dedupe(a, key=lambda d: d['x']))
[{'x': 1, 'y': 2}, {'x': 2, 'y': 4}]

11. 10 . 分片

1
class slice(start, stop[, step])