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.