python collections

本文介绍了collections 中常用的一些数据结构:
namedtuple
deque
Counter
OrderedDict
default dict
bisect （不属于collections）
LRU

# python3 collections

import collections
log = print

# 1. namedtuple

Point = collections.namedtuple("situation", 'x,y')
p = Point(1,2)
log(p.x, p.y)
log(p.x == p[0])

1 2
True

# 2.deque
# deque can easy to implement queue/stack

de = collections.deque()
# append to right
de.append(1)
de.append(1)
# append to left
de.appendleft(0)
de.appendleft(0)
log(de)

# pop right
log(de.pop())
# pop left
log(de.popleft())

deque([0, 0, 1, 1])
1
0

# 3.Counter
# get count of each element and sort

c = collections.Counter('abcabad')
log(c)
# count of a
log(c['a'])
# sort by count desc
log(c.most_common())


c = collections.Counter(['aa', 'aaa', 'bb'])
log(c)

Counter({'a': 3, 'b': 2, 'c': 1, 'd': 1})
3
[('a', 3), ('b', 2), ('c', 1), ('d', 1)]
Counter({'aa': 1, 'aaa': 1, 'bb': 1})

# OrderedDict
# can remember key insert order,  can use it to implement LRU cache

od = collections.OrderedDict()
od['4'] = 100
od['1'] = 20
od['2'] = 100
od['3'] = 300
log(od)

log(list(od.keys()))
log(od['4'])

OrderedDict([('4', 100), ('1', 20), ('2', 100), ('3', 300)])
['4', '1', '2', '3']
100

# default dict

dd = collections.defaultdict(int)
log(dd)
log(dd['a'])

dd['b'] += 1
log(dd['b'])

# after searched 'a', this key will in this default dict, just its value is default
log(dd)

defaultdict(<class 'int'>, {})
0
1
defaultdict(<class 'int'>, {'a': 0, 'b': 1})

# bisect  it's not in collections
# when insert a element, will put it in the right place to keep the order

import bisect
from collections import deque
insert_list = deque()
bisect.insort(insert_list, 1)
bisect.insort(insert_list, 8)
bisect.insort(insert_list, 2)
bisect.insort(insert_list, 5)
bisect.insort(insert_list, 3)

log(insert_list)

deque([1, 2, 3, 5, 8])

# now let's implement a LRU cache with OrderedDict
# need to add unit test for it

from collections import OrderedDict

class LRUCache():
    def __init__(self, capacity=128):
        self.od = OrderedDict()
        self.capacity = capacity
    def get(self, key):
        if key in self.od.keys():
            val = self.od[key]
            self.od.move_to_end(key) # after checking the key, will put it to newest
            # or del key and insert it again 
            return val
        else:
            return -1
    # update key
    def put(self, key, value):
        if key in self.od.keys():
            del self.od[key]
            self.od[key] = value
        else:
            self.od[key] = value
            # then check the capacity
            if len(self.od) > self.capacity:
                # last=False  will pop item as FIFO
                # last=True  LIFO
                self.od.popitem(last=False)