1.Priority Queue

情境：给定一个规则，在一个队列中选取符合规则的element。如果使用传统的queue，查找一个element的效率是O(n)，并不理想。使用heap的效率是O(logn)，所以使用heap来解决priority queue的问题。
思路是根据index建立queue中element的树状结构关系：

index  0 1 2 3 4 5 6
value  X a b c d e f
        1-a
  2-b         3-c   
4-d 5-e    6-f

即每个index的children是index*2和index*2+1，每个index的parent是index//2，再结合边界条件具体判断。将queue中element用heap来建立数据结构的好处是，不需要做相同height的value比较，从而提升算法效率，从O(n)提升到O(logn)。

1.1基本结构

注意，为了表达方便，heap中index0的位置并不适用，所以建立list的时候长度应该是capacity+1，另一个基本属性是heap中element number，实现如下：

class PriorityQueue:
    def __init__(self, capacity = 10):
        self.heap = [None] * (capacity + 1)
        self.nb_of_elements = 0

1.2 Insertion

插入的思路：首先将插入的element放入queue的最后，然后根据比较value的priority，与当前树状结构的root进行比较，如果element的priority更高，则与root swap，在新的树状结构中重复该过程（即bubble up的方法）。

class PriorityQueue:
    def insert(self, value):
        self.nb_of_elements += 1
        self.heap[self.nb_of_elements] = value
        self._bubble_up(self.nb_of_elements)
    def _bubble_up(self, i):
        if i == 1:
            return 
        if self.heap[i // 2] < self.heap[i]:
            self.heap[i // 2], self.heap[i] = self.heap[i], self.heap[i // 2]
            self._bubble_up(i // 2)
        #如果root的value小于element，则互换，再递归bubble up，直到base condition--index = 1为止

1.3 Deletion

删除的思路：把index1的element抛出处理，再把最后位置的元素放在index1的位置。接下来和insertion类似，判断当前树状结构中priority是否正确，如果正确则不动，否则将root，left_child，right_child中最大的值放在root上，root的值放在对应的位置上，再判断新的树状结构上的prioirty（即bubble down的方法）。

class PriorityQueue:
    def delete(self):
        self.heap[self.nb_of_elements], self.heap[1] = self.heap[1], self.heap[self.nb_of_elements]
        #将第一个元素和最后一个元素互换，并没有删除被处理的element，而是接着调整nb_of_elements，使其不在当前的queue可读取的范围内
        self.nb_of_elements -= 1
        self._bubble_down(1)
    def _bubble_down(self, i):
        left_child = i * 2
        if left_child > self.nb_of_elements:
            return 
        right_child = left_child + 1
        good_child = left_child
        if right_child <= self.nb_of_elements and\
            self.heap[left_child] < self.heap[right_child]:
            good_child = right_child
        if self.heap[i] < self.heap[good_child]:
            self.heap[i], self.heap[good_child] = self.heap[good_child], self.heap[i]
            self._bubble_down(good_child)

1.4 quiz_10简介

给定一个数组生成一个priority queue，目标是调整priority queue的element顺序，使得value值高的元素尽可能滞后，同时保证生成的数组产生的priority queue和原来一样。举例如下：
假设给定数组生成的priority queue是[None, 27, 12, 24]

  27
12  24

在给定条件下调整数组顺序，希望大数尽可能滞后，最大的可能是[12, 24, 27]，用这个数组生成priority queue

12      

  12            24
24    -->    12

  24           27
12  27 -->   12  24

新生成的priority queue和原来一样。反例：
如果生成的数组是[27, 24, 12]

27      

  27   
24    

  27
24  12

这样就改变了原来priority queue的顺序。

2. Decorators

decorator可以说是python最灵活的部分，甚至可以说它是检验是否精通python的判断标准之一。decorator能够俭省大量代码，当然，代价是不好理解，不容易使用。

补充背景：python函数的4种传参形式
(1)fun1(a,b,c)，直接传参，位置匹配
(2)fun2(a=1,b=2,c=3)，根据键值对的形式做实参与行参的匹配，忽略位置关系，同时设置default值，传参时允许输入参数和实际使用参数数目不等
(3)fun3(*args)，传入任意个参数，以tuples形式存储，有顺序关系
(4)fun4(**kargs)，以键值对字典的形式向函数传参，既有位置灵活性，同时数量无限制
大多数实例都是混合使用，在实践中要满足以下3个规则：
(1)args = 须在args之后
(2)*args须在args=value之后
(3)**kargs须在*args之后
赋值机理（引用网上资料）：
"(1)按顺序把传给args的实参赋值给对应的行参
(2)args = value 形式的实参赋值给行参
(3)将多余出的即键值对行后的零散实参打包组成一个tuple传递给*args
(4)将多余的key=value形式的实参打包正一个dicrionary传递给**kargs"

2.1 class decorator decorates function

用class的attribute来作为decorator的扩展功能，提高了decorator所作用的function的功能。比如下例，用class count_calls，扩展了function add_up的功能，不仅能够求参数和，还能记录执行的次数。详解如下：

class count_calls:
    def __init__(self, f):
        self.count = 0
        self.f = f
    #用class的attribute来记录count的值，初始为0，每执行一次被count_call这个class decorator修饰的函数(self.f = f)，则count值加1
    def __call__(self, *args, **kwargs):
        self.count += 1
        print(f'Count nb {self.count} to {self.f}')
        return self.f(*args, **kwargs)
        #允许被修饰函数f存在任意一种传参形式（前面补充背景介绍的）

# Equivalent to:
# add_up = count_calls(add_up)
#换言之，可以从字面理解decorator，就是在被修饰函数前加个花边，这里加的是count_calls
#type与decorator一致，所以add_up被修饰后从function变成了class，当然class中的一个属性就是add_up这个function
#也就是说，用class decorator时，__init__至少要有两个attributes
#一个是扩展的功能，这里是计数
#另一个是被修饰的function，这里是self.f = f

@count_calls
def add_up(x, y, *, a, b):
#*作为一个标记，可能代表后续的参数要以键值对形式传入。没找到说明，实验所得
    return x + y + a + b

print(add_up(1, 2, a = 2, b = 3))
#add_up在这里是一个count_calls class的instance，第一次传参后instance的default count设置为0
#执行add_up(1, 2, a = 2, b = 3)实际上运行的是instance中的__call__
#1，2传入*args形成一个tuple(1,2)
#a = 2, b =3传入**kwargs形成键值对{a:2, b:3}
#然后count属性加1，输出句子，并且调用add_up function（注意不再是class instance），在function中计算得到参数和，输出和8
print(add_up(4, 5, a = 6, b = 7))
print(add_up(8, 9, a = 10, b = 11))

>>>
Count nb 1 to <function add_up at 0x102618f28>
8
Count nb 2 to <function add_up at 0x102618f28>
22
Count nb 3 to <function add_up at 0x102618f28>
38

2.2 function decorator decorates function

除了用class的attribute作为decorator的扩展功能，还可以用high-order function的结构，使用全局变量作为decorator的扩展功能。详解如下：

def count_calls(f):
    count = 0
    #用全局变量count来记录使用次数，不影响wrap函数的使用
    def wrap(*args, **kwargs):
        nonlocal count
        count += 1
        print(f'Count nb {count} to {f}')
        return f(*args, **kwargs)
        #允许被修饰函数f存在任意一种传参形式（前面补充背景介绍的）
    return wrap


# Equivalent to:
# add_up = count_calls(add_up)
#与class decorator类似，这里也是在add_up前加个花边count_calls
#与之前不同的是type依然是function，但不再是add_up的function，而是count_calls的function

@count_calls
def add_up(x, y, *, a, b):
    return x + y + a + b

print(add_up(1, 2, a = 2, b = 3))
#add_up在这里是count_calls的function
#传入参数后先设置全局变量count = 0
#然后进入嵌套函数wrap，传参过程和class decorator一样，不再赘述
#wrap的return调用了f，也就是add_up
#在add_up里求和输出
print(add_up(4, 5, a = 6, b = 7))
print(add_up(8, 9, a = 10, b = 11))

>>>
Count nb 1 to <function add_up at 0x1026350d0>
8
Count nb 2 to <function add_up at 0x1026350d0>
22
Count nb 3 to <function add_up at 0x1026350d0>
38

2.3 fucntion decorator自身传参 decorates function

上述两种方式都没有decorator自身参数，只是在为被修饰的函数服务。这里引入decorator自身参数，进一步强大decorator的扩展功能。详解如下：

def count_calls_starting_from(start = 0):
#为了实现自身的参数，在之前函数的嵌套基础上，进一步嵌套
#default默认值是0，这样可以控制从多少开始计数，decorator功能进一步强大
    def count_calls(f):
        count = start
    
        def wrap(*args, **kwargs):
            nonlocal count
            count += 1
            print(f'Count nb {count} to {f}')
            return f(*args, **kwargs)
        
        return wrap
    
    return count_calls


# Equivalent to:
# add_up = count_calls_starting_from(1)(add_up)
@count_calls_starting_from(1)
#传入decorator的参数是1，意味着不再只能从0开始记录调用次数，可以从任意值开始计数
def add_up(x, y, *, a, b):
    return x + y + a + b

print(add_up(1, 2, a = 2, b = 3))
print(add_up(4, 5, a = 6, b = 7))
print(add_up(8, 9, a = 10, b = 11))

>>>
Count nb 2 to <function add_up at 0x102635d90>
8
Count nb 3 to <function add_up at 0x102635d90>
22
Count nb 4 to <function add_up at 0x102635d90>
38

2.4 function decorator decorates class

前面三个小节全都是decorates function的，这里进一步扩展到decorates class。详解如下：

def count_calls(cls):
    def wrap(datum):
        wrap.count += 1
        print('Count nb {} to {}'.format(wrap.count, cls))
        return cls(datum)
    
    wrap.count = 0
    return wrap
#decorator的部分和前面三个小节都是相同原理，这里依然是全局变量的思路
#不同的是，由于被修饰的是class，不需要在warp中声明nonlocal variable，而是可以直接调用class的属性来完成

# Equivalent to:
# C = count_calls(C)
@count_calls
class C:
    def __init__(self, datum):
        self.datum = datum


I1, I2, I3 = C(11), C(12), C(13)
#以I1 = C(11)为例，C(11)在这里不是class的一个instance，而是function count_calls()，warp变成了class的一个instance
#运行function count_calls(C(11))，所以cls的type是class
#其他流程和前面3个小节一致，不再赘述
print(I1.datum, I2.datum, I3.datum)

>>>
Count nb 1 to <class '__main__.C'>
Count nb 2 to <class '__main__.C'>
Count nb 3 to <class '__main__.C'>
11 12 13

2.5 class中的decorator @staticmethod

除了class与function相互作为decorator外，class中也有自己独特的decorator。
class是对一系列有共同特征个体的抽象，这就意味着使用class往往要实例化再处理。娘胎里带来的特征就是class属性不够强大，不能在class未实例化的时候调用。decorator的强大之处就是能解决这个问题，python内置了@staticmethod，他的用处就是解决前面说的问题，特点是不强制参数的情形，任意情况都可以。详解如下：

class C:
    count_1 = 0
    count_2 = 0
    
    def __init__(self):
        C.count_1 += 1
        C.count_2 += 1
    
    def display_count_1(mark):
        print('count_1' + mark, C.count_1)

    # Equivalent to:
    # display_count_2 = staticmethod(display_count_2)
    @staticmethod
    def display_count_2(mark):
        print('count_2' + mark, C.count_2)


I1, I2, I3 = C(), C(), C()
#每次实例化，都执行__init__，所以三次实例化后count_1 =3, count_2 = 3
C.display_count_1(':')
#C的属性调用，执行display_count_1，传入参数':'。
#输出'count_1'，然后是mark，这里mark = ':'，接着是count_1，这里count_1 = 3
C.display_count_2('...')
#C的属性调用，执行display_count_2，传入参数'...'
#display_count_2本不能被执行，因为C的属性调用没有实例化，但是被@staticmethod修饰后，允许非实例化的调用
#输出结果的解释和上边一条语句执行一致，不赘述
I2.display_count_2(' ')
#实例I2的属性调用，执行display_count_2，传入参数' '
#实例化之后的调用，不受到@staticmethod的修饰影响，正常调用

>>>
count_1: 3
count_2... 3
count_2  3

这个小节看到了decorator的强大作用，能够灵活的把多种情况的使用合并为一种，大大节省了代码，同时简化了逻辑。从这能够看到一些端倪，为什么一个人是否精通python能够从decorator的使用上体现出来。

2.6 class中的decorator @classmethod

@classmethod与@statcimethod非常类似，不同之处在于它强制第一个传入的参数，这个参数不是class实例，而是未实例化的class本身，例子如下：

class C:
    count = 0
    
    def __init__(self):
        C.count += 1
    
    # Equivalent to:
    # display_count = classmethod(display_count)
    @classmethod
    def display_count(cls, mark):
    #注意，这里不能省略参数cls
        print(f'count for {cls.__name__}' + mark, C.count)


I1, I2, I3 = C(), C(), C()
C.display_count('...')
I2.display_count(':')

>>>
count for C... 3
count for C: 3

3. descriptor

任何python的class都含有__init__的构造函数，descriptor是指至少有__get__(self, instance, owner), __set__(self, instance, value), __delete__(self, instance)三种方法之一的class。从字面上看，descriptor是描述符，也就是说这样的class要么能够查询__get__()，要么能够输入__set__()，要么能够删除__delete__()。与sql有点像，select, update, delete与之对应。
如果class中有__set__()方法则称为data descriptor，可以理解为能够处理数据的class。

3.1 下划线的命名规则

(1)_XX
python没有private method，所以用开头有一个下划线的命名方法来代表中间过程的method/attribute。之前的文章中用过这样的命名方法，如果一个class中的某个method需要定义其他function来实现，则中间过程的function命名以单下划线开头。
(2)__XX
双下划线开头的method用来代表private method，最主要的功能是避免被继承的subcalss所overload。
(3)XX
这样的命名方法含义是：这是python专属的方法，python读取处理，比如init是初始化函数，user不应该碰。

3.2 descriptor基本功能

class D:
    def __init__(self):
        self.datum = 'Descriptor datum'

    def __get__(self, instance, owner):
        print(self.datum)
        print(owner._datum)
        return instance._datum
        
    def __set__(self, instance, value):
        self.datum = 'New descriptor datum'
        instance._datum = value
        
    def __delete__(self, instance):
        print('Deleting instance datum')
        del instance._datum


class C:
    _datum = 'Owner datum'

    def __init__(self):
        self._datum = 'Instance datum'

    datum = D()


I = C()
#I是class C的一个instance
print(I.datum)
#I.datum调用的是class C中的datum = D()，也就是class D的一个instance
#于是调用class D的__get__()，先输出self.datum，也就是class D中__init__的datum“Descriptor datum”
#然后输出owner._datum，owner是class C，所以调用class C的_datum“Owner datum”
#最后return instance.datum，instance是class C中的instance I，所以调用class C中__init__的_datum“Instance datum”
print()
>>>
Descriptor datum
Owner datum
Instance datum


I.datum = 'New instance value'
#overload实例I的datum值为'New instance value'，datum是一个class D的instance，先在instance中更新self._datum值为'New instance value'，再传参进入class D，在__set__()中的datum复写self.datum为'New descriptor datum'
print(I.datum)
#输出实例I的datum值，也就是class D的__get__值，调用__init__()，这时datum被上一步__set__()操作改写为了'New instance value'
#执行输出owner._datum，和前面的一致，输出'Owner datum'
#再return  instance.datum，实例I的值已经改为'New instance value'
print()
>>>
New descriptor datum
Owner datum
New instance value

del I.datum
#删除实例I的datum，datum = D()，调用class D的__delete__()，输出'Deleting instance datu'
#然后del instanc._datum，也就是实例I中__init__的_datum为空
print()
>>>
Deleting instance datum

I = C()
#重新实例化I
print(I.datum)
#因为前面一次I的实例化更改了class D的self.datum值为'New descriptor datum'，所以这次输出和第一次的略有不同
>>>
New descriptor datum
Owner datum
Instance datum

4. hash

如果要在一个list中查找一个element，效率是O(n)。为了将效率提高到尽可能接近O(1)，使用hash的方式。
理想情况是每个index对应一个element，这样查询element时只去对应的index中查看value即可得到结果。
hash的实现方法常见有两种：一种是位运算，在之前hash值的基础上向左做n位的位运算再加上新的value值得到新的hash值，通过循环找到效率最高的n；另一种是用多项式计算hash值，Computes the hash code of a string x_0x_1...x_n (with x_0, x_1, ..., x_n being the ascii codes of the characters) as the number x_0a^n + x_1a^{n-1} + .... + x_n.