分类： python

python函数中*args 和**kwargs的用法

函数的参数数量不确定时，可以使用*args 和**kwargs，*args 没有key值，**kwargs有key值。

这样说吧：这个是Python函数可变参数args及kwargs *args表示任何多个无名参数，它是一个tuple **kwargs表示关键字参数，它是一个dict

示例:

def highschool_class(number,*args):

 print("the highschool_class  has %s "%number)  #高中一个班级的人数    
 print(*args)    
 return (args)

highschool_class(59,30,29)

结果：

the highschool_class has 59
30 29

Process finished with exit code 0

def highschool_class(number,*args,**kwargs): print(“the highschool_class has %s “%number) #高中一个班级的人数 print(args)
print(kwargs)
return (args,kwargs)

highschool_class(59,30,29,male = ’30’,female = ’29’)

结果：

the highschool_class has 59
30 29
{‘male’: ’30’, ‘female’: ’29’}

Process finished with exit code 0

PyTorch中model.modules(), model.named_modules(), model.children(), model.named_children(), model.parameters(), model.named_parameters(), model.state_dict()

本文通过一个例子实验来观察并讲解PyTorch中model.modules(), model.named_modules(), model.children(), model.named_children(), model.parameters(), model.named_parameters(), model.state_dict()这些model实例方法的返回值。例子如下：

import torch 
import torch.nn as nn 

class Net(nn.Module):

    def __init__(self, num_class=10):
        super().__init__()
        self.features = nn.Sequential(
            nn.Conv2d(in_channels=3, out_channels=6, kernel_size=3),
            nn.BatchNorm2d(6),
            nn.ReLU(inplace=True),
            nn.MaxPool2d(kernel_size=2, stride=2),
            nn.Conv2d(in_channels=6, out_channels=9, kernel_size=3),
            nn.BatchNorm2d(9),
            nn.ReLU(inplace=True),
            nn.MaxPool2d(kernel_size=2, stride=2)
        )

        self.classifier = nn.Sequential(
            nn.Linear(9*8*8, 128),
            nn.ReLU(inplace=True),
            nn.Dropout(),
            nn.Linear(128, num_class)
        )

    def forward(self, x):
        output = self.features(x)
        output = output.view(output.size()[0], -1)
        output = self.classifier(output)
    
        return output

model = Net()

如上代码定义了一个由两层卷积层，两层全连接层组成的网络模型。值得注意的是，这个Net由外到内有3个层次：

Net:

----features:

------------Conv2d
------------BatchNorm2d
------------ReLU
------------MaxPool2d
------------Conv2d
------------BatchNorm2d
------------ReLU
------------MaxPool2d

----classifier:

------------Linear
------------ReLU
------------Dropout
------------Linear

网络Net本身是一个nn.Module的子类，它又包含了features和classifier两个由Sequential容器组成的nn.Module子类，features和classifier各自又包含众多的网络层，它们都属于nn.Module子类，所以从外到内共有3个层次。
下面我们来看这几个实例方法的返回值都是什么。

In [7]: model.named_modules()                                                                                                       
Out[7]: <generator object Module.named_modules at 0x7f5db88f3840>

In [8]: model.modules()                                                         
Out[8]: <generator object Module.modules at 0x7f5db3f53c00>

In [9]: model.children()                                                        
Out[9]: <generator object Module.children at 0x7f5db3f53408>

In [10]: model.named_children()                                                 
Out[10]: <generator object Module.named_children at 0x7f5db80305e8>

In [11]: model.parameters()                                                     
Out[11]: <generator object Module.parameters at 0x7f5db3f534f8>

In [12]: model.named_parameters()                                               
Out[12]: <generator object Module.named_parameters at 0x7f5d42da7570>

In [13]: model.state_dict()                                                     
Out[13]: 
OrderedDict([('features.0.weight', tensor([[[[ 0.1200, -0.1627, -0.0841],
                        [-0.1369, -0.1525,  0.0541],
                        [ 0.1203,  0.0564,  0.0908]],
                      ……

可以看出，除了model.state_dict()返回的是一个字典，其他几个方法返回值都显示的是一个生成器，是一个可迭代变量，我们通过列表推导式用for循环将返回值取出来进一步进行观察：

In [14]: model_modules = [x for x in model.modules()]                                                                                

In [15]: model_named_modules = [x for x in model.named_modules()]        

In [16]: model_children = [x for x in model.children()]                                                                              

In [17]: model_named_children = [x for x in model.named_children()]                                                                  

In [18]: model_parameters = [x for x in model.parameters()]                                                                          

In [19]: model_named_parameters = [x for x in model.named_parameters()]
1. model.modules()

model.modules()迭代遍历模型的所有子层，所有子层即指nn.Module子类，在本文的例子中，Net(), features(), classifier(),以及nn.xxx构成的卷积，池化，ReLU, Linear, BN, Dropout等都是nn.Module子类，也就是model.modules()会迭代的遍历它们所有对象。我们看一下列表model_modules:

In [20]: model_modules                                                                                                               
Out[20]: 
[Net(
   (features): Sequential(
     (0): Conv2d(3, 6, kernel_size=(3, 3), stride=(1, 1))
     (1): BatchNorm2d(6, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
     (2): ReLU(inplace)
     (3): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
     (4): Conv2d(6, 9, kernel_size=(3, 3), stride=(1, 1))
     (5): BatchNorm2d(9, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
     (6): ReLU(inplace)
     (7): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
   )
   (classifier): Sequential(
     (0): Linear(in_features=576, out_features=128, bias=True)
     (1): ReLU(inplace)
     (2): Dropout(p=0.5)
     (3): Linear(in_features=128, out_features=10, bias=True)
   )
 ), 
Sequential(
   (0): Conv2d(3, 6, kernel_size=(3, 3), stride=(1, 1))
   (1): BatchNorm2d(6, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
   (2): ReLU(inplace)
   (3): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
   (4): Conv2d(6, 9, kernel_size=(3, 3), stride=(1, 1))
   (5): BatchNorm2d(9, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
   (6): ReLU(inplace)
   (7): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
 ), 
Conv2d(3, 6, kernel_size=(3, 3), stride=(1, 1)), 
BatchNorm2d(6, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True), 
ReLU(inplace), 
MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False), 
Conv2d(6, 9, kernel_size=(3, 3), stride=(1, 1)), 
BatchNorm2d(9, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True), 
ReLU(inplace), 
MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False), 
Sequential(
   (0): Linear(in_features=576, out_features=128, bias=True)
   (1): ReLU(inplace)
   (2): Dropout(p=0.5)
   (3): Linear(in_features=128, out_features=10, bias=True)
 ), 
Linear(in_features=576, out_features=128, bias=True), 
ReLU(inplace), 
Dropout(p=0.5), 
Linear(in_features=128, out_features=10, bias=True)]

In [21]: len(model_modules)                                                                                                          
Out[21]: 15

可以看出，model_modules列表中共有15个元素，首先是整个Net，然后遍历了Net下的features子层，进一步遍历了feature下的所有层，然后又遍历了classifier子层以及其下的所有层。所以说model.modules()能够迭代地遍历模型的所有子层。

2. model.named_modules()

顾名思义，它就是有名字的model.modules()。model.named_modules()不但返回模型的所有子层，还会返回这些层的名字：

In [28]: len(model_named_modules)                                                                                                    
Out[28]: 15

In [29]: model_named_modules                                                                                                         
Out[29]: 
[('', Net(
    (features): Sequential(
      (0): Conv2d(3, 6, kernel_size=(3, 3), stride=(1, 1))
      (1): BatchNorm2d(6, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
      (2): ReLU(inplace)
      (3): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
      (4): Conv2d(6, 9, kernel_size=(3, 3), stride=(1, 1))
      (5): BatchNorm2d(9, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
      (6): ReLU(inplace)
      (7): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
    )
    (classifier): Sequential(
      (0): Linear(in_features=576, out_features=128, bias=True)
      (1): ReLU(inplace)
      (2): Dropout(p=0.5)
      (3): Linear(in_features=128, out_features=10, bias=True)
    )
  )), 
('features', Sequential(
    (0): Conv2d(3, 6, kernel_size=(3, 3), stride=(1, 1))
    (1): BatchNorm2d(6, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
    (2): ReLU(inplace)
    (3): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
    (4): Conv2d(6, 9, kernel_size=(3, 3), stride=(1, 1))
    (5): BatchNorm2d(9, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
    (6): ReLU(inplace)
    (7): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
  )), 
('features.0', Conv2d(3, 6, kernel_size=(3, 3), stride=(1, 1))), 
('features.1', BatchNorm2d(6, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)), ('features.2', ReLU(inplace)), 
('features.3', MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)), 
('features.4', Conv2d(6, 9, kernel_size=(3, 3), stride=(1, 1))), 
('features.5', BatchNorm2d(9, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)), ('features.6', ReLU(inplace)), 
('features.7', MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)), 
('classifier',
  Sequential(
    (0): Linear(in_features=576, out_features=128, bias=True)
    (1): ReLU(inplace)
    (2): Dropout(p=0.5)
    (3): Linear(in_features=128, out_features=10, bias=True)
  )), 
('classifier.0', Linear(in_features=576, out_features=128, bias=True)), 
('classifier.1', ReLU(inplace)), 
('classifier.2', Dropout(p=0.5)), 
('classifier.3', Linear(in_features=128, out_features=10, bias=True))]

可以看出，model.named_modules()也遍历了15个元素，但每个元素都有了自己的名字，从名字可以看出，除了在模型定义时有命名的features和classifier，其它层的名字都是PyTorch内部按一定规则自动命名的。返回层以及层的名字的好处是可以按名字通过迭代的方法修改特定的层，如果在模型定义的时候就给每个层起了名字，比如卷积层都是conv1,conv2…的形式，那么我们可以这样处理：

for name, layer in model.named_modules():
    if 'conv' in name:
        对layer进行处理

当然，在没有返回名字的情形中，采用isinstance()函数也可以完成上述操作：

for layer in model.modules():
    if isinstance(layer, nn.Conv2d):
        对layer进行处理
3. model.children()

如果把这个网络模型Net按层次从外到内进行划分的话，features和classifier是Net的子层，而conv2d, ReLU, BatchNorm, Maxpool2d这些有时features的子层， Linear, Dropout, ReLU等是classifier的子层，上面的model.modules()不但会遍历模型的子层，还会遍历子层的子层，以及所有子层。
而model.children()只会遍历模型的子层，这里即是features和classifier。

In [22]: len(model_children)                                                                                                         
Out[22]: 2

In [22]: model_children                                                                                                              
Out[22]: 
[Sequential(
   (0): Conv2d(3, 6, kernel_size=(3, 3), stride=(1, 1))
   (1): BatchNorm2d(6, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
   (2): ReLU(inplace)
   (3): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
   (4): Conv2d(6, 9, kernel_size=(3, 3), stride=(1, 1))
   (5): BatchNorm2d(9, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
   (6): ReLU(inplace)
   (7): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
 ), 
Sequential(
   (0): Linear(in_features=576, out_features=128, bias=True)
   (1): ReLU(inplace)
   (2): Dropout(p=0.5)
   (3): Linear(in_features=128, out_features=10, bias=True)
 )]

可以看出，它只遍历了两个元素，即features和classifier。

4. model.named_children()

model.named_children()就是带名字的model.children(), 相比model.children()， model.named_children()不但迭代的遍历模型的子层，还会返回子层的名字：

In [23]: len(model_named_children)                                                                                                   
Out[23]: 2

In [24]: model_named_children                                                                                                        
Out[24]: 
[('features', Sequential(
    (0): Conv2d(3, 6, kernel_size=(3, 3), stride=(1, 1))
    (1): BatchNorm2d(6, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
    (2): ReLU(inplace)
    (3): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
    (4): Conv2d(6, 9, kernel_size=(3, 3), stride=(1, 1))
    (5): BatchNorm2d(9, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
    (6): ReLU(inplace)
    (7): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
  )), 
('classifier', Sequential(
    (0): Linear(in_features=576, out_features=128, bias=True)
    (1): ReLU(inplace)
    (2): Dropout(p=0.5)
    (3): Linear(in_features=128, out_features=10, bias=True)
  ))]

对比上面的model.children(), 这里的model.named_children()还返回了两个子层的名称：features 和 classifier .

5. model.parameters()

迭代地返回模型的所有参数。

In [30]: len(model_parameters)                                                                                                       
Out[30]: 12

In [31]: model_parameters                                                                                                            
Out[31]: 
[Parameter containing:
 tensor([[[[ 0.1200, -0.1627, -0.0841],
           [-0.1369, -0.1525,  0.0541],
           [ 0.1203,  0.0564,  0.0908]],
           ……
          [[-0.1587,  0.0735, -0.0066],
           [ 0.0210,  0.0257, -0.0838],
           [-0.1797,  0.0675,  0.1282]]]], requires_grad=True),
 Parameter containing:
 tensor([-0.1251,  0.1673,  0.1241, -0.1876,  0.0683,  0.0346],
        requires_grad=True),
 Parameter containing:
 tensor([0.0072, 0.0272, 0.8620, 0.0633, 0.9411, 0.2971], requires_grad=True),
 Parameter containing:
 tensor([0., 0., 0., 0., 0., 0.], requires_grad=True),
 Parameter containing:
 tensor([[[[ 0.0632, -0.1078, -0.0800],
           [-0.0488,  0.0167,  0.0473],
           [-0.0743,  0.0469, -0.1214]],
           …… 
          [[-0.1067, -0.0851,  0.0498],
           [-0.0695,  0.0380, -0.0289],
           [-0.0700,  0.0969, -0.0557]]]], requires_grad=True),
 Parameter containing:
 tensor([-0.0608,  0.0154,  0.0231,  0.0886, -0.0577,  0.0658, -0.1135, -0.0221,
          0.0991], requires_grad=True),
 Parameter containing:
 tensor([0.2514, 0.1924, 0.9139, 0.8075, 0.6851, 0.4522, 0.5963, 0.8135, 0.4010],
        requires_grad=True),
 Parameter containing:
 tensor([0., 0., 0., 0., 0., 0., 0., 0., 0.], requires_grad=True),
 Parameter containing:
 tensor([[ 0.0223,  0.0079, -0.0332,  ..., -0.0394,  0.0291,  0.0068],
         [ 0.0037, -0.0079,  0.0011,  ..., -0.0277, -0.0273,  0.0009],
         [ 0.0150, -0.0110,  0.0319,  ..., -0.0110, -0.0072, -0.0333],
         ...,
         [-0.0274, -0.0296, -0.0156,  ...,  0.0359, -0.0303, -0.0114],
         [ 0.0222,  0.0243, -0.0115,  ...,  0.0369, -0.0347,  0.0291],
         [ 0.0045,  0.0156,  0.0281,  ..., -0.0348, -0.0370, -0.0152]],
        requires_grad=True),
 Parameter containing:
 tensor([ 0.0072, -0.0399, -0.0138,  0.0062, -0.0099, -0.0006, -0.0142, -0.0337,
          ……
         -0.0370, -0.0121, -0.0348, -0.0200, -0.0285,  0.0367,  0.0050, -0.0166],
        requires_grad=True),
 Parameter containing:
 tensor([[-0.0130,  0.0301,  0.0721,  ..., -0.0634,  0.0325, -0.0830],
         [-0.0086, -0.0374, -0.0281,  ..., -0.0543,  0.0105,  0.0822],
         [-0.0305,  0.0047, -0.0090,  ...,  0.0370, -0.0187,  0.0824],
         ...,
         [ 0.0529, -0.0236,  0.0219,  ...,  0.0250,  0.0620, -0.0446],
         [ 0.0077, -0.0576,  0.0600,  ..., -0.0412, -0.0290,  0.0103],
         [ 0.0375, -0.0147,  0.0622,  ...,  0.0350,  0.0179,  0.0667]],
        requires_grad=True),
 Parameter containing:
 tensor([-0.0709, -0.0675, -0.0492,  0.0694,  0.0390, -0.0861, -0.0427, -0.0638,
         -0.0123,  0.0845], requires_grad=True)]
6. model.named_parameters()

如果你是从前面看过来的，就会知道，这里就是迭代的返回带有名字的参数，会给每个参数加上带有 .weight或 .bias的名字以区分权重和偏置：

In [32]: len(model.named_parameters)                                                                                                 
Out[32]: 12

In [33]: model_named_parameters                                                                                                      
Out[33]: 
[('features.0.weight', Parameter containing:
  tensor([[[[ 0.1200, -0.1627, -0.0841],
            [-0.1369, -0.1525,  0.0541],
            [ 0.1203,  0.0564,  0.0908]],
           ……
           [[-0.1587,  0.0735, -0.0066],
            [ 0.0210,  0.0257, -0.0838],
            [-0.1797,  0.0675,  0.1282]]]], requires_grad=True)),
 ('features.0.bias', Parameter containing:
  tensor([-0.1251,  0.1673,  0.1241, -0.1876,  0.0683,  0.0346],
         requires_grad=True)),
 ('features.1.weight', Parameter containing:
  tensor([0.0072, 0.0272, 0.8620, 0.0633, 0.9411, 0.2971], requires_grad=True)),
 ('features.1.bias', Parameter containing:
  tensor([0., 0., 0., 0., 0., 0.], requires_grad=True)),
 ('features.4.weight', Parameter containing:
  tensor([[[[ 0.0632, -0.1078, -0.0800],
            [-0.0488,  0.0167,  0.0473],
            [-0.0743,  0.0469, -0.1214]],
           ……
           [[-0.1067, -0.0851,  0.0498],
            [-0.0695,  0.0380, -0.0289],
            [-0.0700,  0.0969, -0.0557]]]], requires_grad=True)),
 ('features.4.bias', Parameter containing:
  tensor([-0.0608,  0.0154,  0.0231,  0.0886, -0.0577,  0.0658, -0.1135, -0.0221,
           0.0991], requires_grad=True)),
 ('features.5.weight', Parameter containing:
  tensor([0.2514, 0.1924, 0.9139, 0.8075, 0.6851, 0.4522, 0.5963, 0.8135, 0.4010],
         requires_grad=True)),
 ('features.5.bias', Parameter containing:
  tensor([0., 0., 0., 0., 0., 0., 0., 0., 0.], requires_grad=True)),
 ('classifier.0.weight', Parameter containing:
  tensor([[ 0.0223,  0.0079, -0.0332,  ..., -0.0394,  0.0291,  0.0068],
          ……
          [ 0.0045,  0.0156,  0.0281,  ..., -0.0348, -0.0370, -0.0152]],
         requires_grad=True)),
 ('classifier.0.bias', Parameter containing:
  tensor([ 0.0072, -0.0399, -0.0138,  0.0062, -0.0099, -0.0006, -0.0142, -0.0337,
           ……
          -0.0370, -0.0121, -0.0348, -0.0200, -0.0285,  0.0367,  0.0050, -0.0166],
         requires_grad=True)),
 ('classifier.3.weight', Parameter containing:
  tensor([[-0.0130,  0.0301,  0.0721,  ..., -0.0634,  0.0325, -0.0830],
          [-0.0086, -0.0374, -0.0281,  ..., -0.0543,  0.0105,  0.0822],
          [-0.0305,  0.0047, -0.0090,  ...,  0.0370, -0.0187,  0.0824],
          ...,
          [ 0.0529, -0.0236,  0.0219,  ...,  0.0250,  0.0620, -0.0446],
          [ 0.0077, -0.0576,  0.0600,  ..., -0.0412, -0.0290,  0.0103],
          [ 0.0375, -0.0147,  0.0622,  ...,  0.0350,  0.0179,  0.0667]],
         requires_grad=True)),
 ('classifier.3.bias', Parameter containing:
  tensor([-0.0709, -0.0675, -0.0492,  0.0694,  0.0390, -0.0861, -0.0427, -0.0638,
          -0.0123,  0.0845], requires_grad=True))]
7. model.state_dict()

model.state_dict()直接返回模型的字典，和前面几个方法不同的是这里不需要迭代，它本身就是一个字典，可以直接通过修改state_dict来修改模型各层的参数，用于参数剪枝特别方便。

IPython（jupyter）中的常用工具

ipython是一个python的交互式shell，比默认的python shell好用得多，支持变量自动补全，自动缩进，支持bash shell命令，内置了许多很有用的功能和函数。学习ipython将会让我们以一种更高的效率来使用python。同时它也是利用Python进行科学计算和交互可视化的一个最佳的平台。

IPython提供了两个主要的组件：

1.一个强大的python交互式shell
2.供Jupyter notebooks使用的一个Jupyter内核（IPython notebook）

IPython的主要功能如下：

1.运行ipython控制台
2.使用ipython作为系统shell
3.使用历史输入(history)
4.Tab补全
5.使用%run命令运行脚本
6.使用%timeit命令快速测量时间
7.使用%pdb命令快速debug
8.使用pylab进行交互计算
9.使用IPython Notebook

Tab键自动补全

在shell中输入表达式时，只要按下Tab键，当前命名空间中任何与输入的字符串相匹配的变量(对象或者函数等)就会被找出来

 内省

在变量的前面或者后面加上一个问号?，就可以将有关该对象的一些通用信息显示出来，这就叫做对象的内省

如果对象是一个函数或者实例方法，则它的docstring也会被显示出来

使用历史命令history

在IPython shell中，使用历史命令可以简单地使用上下翻页键即可，另外我们也可以使用hist命令(或者history命令)查看所有的历史输入。（正确的做法是使用%hist，在这里，%hist也是一个魔法命令）

使用%run命令运行脚本

在ipython会话环境中，所有文件都可以通过%run命令当做Python程序来运行，输入%run 路径+python文件名称即可

使用%timeit命令快速测量代码运行时间

在一个交互式会话中，我们可以使用%timeit魔法命令快速测量代码运行时间。相同的命令会在一个循环中多次执行，多次运行时长的平均值作为该命令的最终评估时长。-n 选项可以控制命令在单词循环中执行的次数，-r选项控制执行循环的次数。

使用%debug命令进行快速debug

ipython带有一个强大的调试器。无论何时控制台抛出了一个异常，我们都可以使用%debug魔法命令在异常点启动调试器。接着你就能调试模式下访问所有的本地变量和整个栈回溯。使用u和d向上和向下访问栈，使用q退出调试器。在调试器中输入?可以查看所有的可用命令列表。

 在IPython中使用系统shell

我们可以在IPython中直接使用系统shell，并获取读取结果作为一个Python字符串列表。为了实现这种功能，我们需要使用感叹号!作为shell命令的前缀。比如现在在我的windows系统中，直接在IPython中ping百度

重点：display 模块

官方教程 https://ipython.readthedocs.io/en/stable/api/generated/IPython.display.html

之前想要在jupyter中显示图像 、视频 or voice、html，可能不知道该怎么办，有了IP display模块，可以解决该问题。

1、audio

from IPython.display import Audio,display
sound_file = '../taobao427.mp3'
display(Audio(sound_file))

2、ipython.display.image



from IPython.display import display, Image

path = "1.jpg"

display( Image( filename = path) )

3、播放视频

from IPython.display import clear_output,  display, HTML
from PIL import Image
import matplotlib.pyplot as plt
import time
import cv2
import os

def show_video(video_path:str,small:int=2):
    if not os.path.exists(video_path):
        print("视频文件不存在")
    video = cv2.VideoCapture(video_path)
    current_time = 0
    while(True):
        try:
            clear_output(wait=True)
            ret, frame = video.read()
            if not ret:
                break
            lines, columns, _ = frame.shape
            #########do img preprocess##########
            
            # 画出一个框
            #     cv2.rectangle(img, (500, 300), (800, 400), (0, 0, 255), 5, 1, 0)
             # 上下翻转
             # img= cv2.flip(img, 0)
            
            ###################################
            
            if current_time == 0:
                current_time = time.time()
            else:
                last_time = current_time
                current_time = time.time()
                fps = 1. / (current_time - last_time)
                text = "FPS: %d" % int(fps)
                cv2.putText(frame, text , (0,100), cv2.FONT_HERSHEY_TRIPLEX, 3.65, (255, 0, 0), 2)
                
          #     img = cv2.resize(img,(1080,1080))
                frame = cv2.cvtColor(frame, cv2.COLOR_BGR2RGB)
            frame = cv2.resize(frame, (int(columns / small), int(lines / small)))

            img = Image.fromarray(frame)

            display(img)
            # 控制帧率
            time.sleep(0.02)
        except KeyboardInterrupt:
            video.release()

4、htlm（视频）

# ########## display
from IPython.display import display, HTML

html_str = '''
<video controls width=\"500\" height=\"500\" src=\"{}\">animation</video>
'''.format("./dataset/vid****8726.mp4")
print(html_str)
display(HTML(html_str))

5、插入参考的网页或者论文 iframe

from IPython.display import IFrame IFrame(src='https://www.baidu.com/',width=800,height=500)

from IPython.display import HTML
HTML("""

Example Domain

This domain is for use in illustrative examples in documents. You may use this domain in literature without prior coordination or asking for permission.

More information...

""")

6、插入iframe标签

from IPython.display import HTML
HTML('')

NVIDIA训练深度学习模型加速:APEX库

最近在跑目标检测和图像分类模型，发现很多时候教程里需要 安装apex库，于是我就去网上搜索一下这个，发现apex大有来头；

官方：

https://nvidia.github.io/apex/amp.html

https://docs.nvidia.com/deeplearning/performance/mixed-precision-training/index.html

APEX 是来自英伟达 (NVIDIA) 的一个很好用的深度学习加速库。由英伟达开源，完美支持PyTorch框架，用于改变数据格式来减小模型显存占用的工具。其中最有价值的是 amp (Automatic Mixed Precision) ，将模型的大部分操作都用 Float16 数据类型测试，一些特别操作仍然使用 Float32。并且用户仅仅通过三行代码即可完美将自己的训练代码迁移到该模型。实验证明，使用 Float16 作为大部分操作的数据类型，并没有降低参数，在一些实验中，反而由于可以增大 Batch size，带来精度上的提升，以及训练速度上的提升。

使用理由

使用精度低于32位浮点的数值格式有许多好处。首先，它们需要更少的内存，从而能够训练和部署更大的神经网络。其次，它们需要较少的内存带宽，从而加快数据传输操作。第三，数学运算在降低精度方面运行得更快，特别是在具有TensorCore支持的GPU上。混合精度训练（Mixed Precision Training）实现了所有这些好处，同时确保与完全精度训练相比，不会丢失特定任务的准确性。它这样做的方法是识别需要完全精度的步骤，只对这些步骤使用32位浮点，而在其他地方使用16位浮点。

在PyTorch中的使用：
首先需要安装其apex库（我还没装过），其github地址：https://github.com/NVIDIA/apex。
然后在训练的脚本（代码）中简单添加几句就可以了

from apex import amp

amp.init()
amp.init_trainer(trainer)
with amp.scale_loss(loss, trainer) as scaled_loss:
   autograd.backward(scaled_loss)

APEX的配置

前提是你安装好了CUDA和CUDNN，以及你的系统是Ubuntu系统。

git clone https://github.com/NVIDIA/apex
cd apex
pip install -v --no-cache-dir --global-option="--cpp_ext" --global-option="--cuda_ext"

Apex 还通过以下方式支持仅 Python 构建 (Pytorch 0.4 需要)。

pip install -v --disable-pip-version-check --no-cache-dir ./

安装之后，clone下来的apex文件夹就可以删除了。

查看能否正确导入apex：

from apex import amp

Bellman-Ford 单源最短路径（回路）算法

Bellman-ford 算法比dijkstra算法更具普遍性，因为它对边没有要求，可以处理负权边与负权回路。缺点是时间复杂度过高，高达O(VE), V为顶点数，E为边数。

特点：支持有环，负权重，但不能存在负权重环。

其主要思想：对所有的边进行n-1轮松弛操作，因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1边。换句话说，第1轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离；第2轮在对所有的边进行松弛后，得到的是源点最多经过两条边到达其他顶点的最短距离；第3轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离……

Bellman-Ford 算法描述：

  1. 创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，初始均为 Infinite，源顶点距离为 0；
  2. 计算最短路径，执行 V – 1 次遍历；
    • 对于图中的每条边：如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d，则更新终点 v 的距离值 d；
  3. 检测图中是否有负权边形成了环，遍历图中的所有边，计算 u 至 v 的距离，如果对于 v 存在更小的距离，则说明存在环；
for (var i = 0; i < n - 1; i++) {
    for (var j = 0; j < m; j++) {//对m条边进行循环
      var edge = edges[j];
      // 松弛操作
      if (distance[edge.to] > distance[edge.from] + edge.weight ){ 
        distance[edge.to] = distance[edge.from] + edge.weight;
      }
    }
}

其中， n为顶点的个数，m为边的个数，edges数组储存了所有边，distance数组是源点到所有点的距离估计值，循环结束后就是最小值。

算法过程：首先初始化，对所有的节点V来说，所有的边E进行松弛操作，再然后循环遍历每条边，如果d[v] > d[u] + w(u,v),表示有一个负权重的环路存在。

 最后如果没有负权重环路，那么d[v] 是最小路径值。

python 实现：


def bellman_ford(graph, source):
    dist = {}
    p = {}
    max = 10000
    for v in graph:
        dist[v] = max  #赋值为负无穷完成初始化
        p[v] = None
    dist[source] = 0
 
    for i in range(len( graph ) - 1):
        for u in graph:
            for v in graph[u]:
                if dist[v] > graph[u][v] + dist[u]:
                    dist[v] = graph[u][v] + dist[u]
                    p[v] = u    #完成松弛操作，p为前驱节点
 
    for u in graph:
        for v in graph[u]:
            if dist[v] > dist[u] + graph[u][v]:
                return None, None  #判断是否存在环路
 
    return dist, p
 
def test():
    graph = {
        'a': {'b': -1, 'c':  4},
        'b': {'c':  2, 'd':  3, 'e':  2},
        'c': {},
        'd': {'b':  3, 'c':  5},
        'e': {'d': -3}
    }
    dist, p = bellman_ford(graph, 'a')
    print(dist)
    print(p)
def testfail():
    graph = {
        'a': {'b': -1, 'c':  4},
        'b': {'c':  2, 'd':  3, 'e':  2},
        'c': {'d': -5},
        'd': {'b':  3},
        'e': {'d': -3}
    }
    dist, p = bellman_ford(graph, 'a')
    print(dist)
    print(p)
 
test()
testfail()

Floyd算法：求多源解负权图最短路径问题

思想：动态规划

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。

Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。

算法描述

1) 算法思想原理：

Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。

从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）

从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

2) 算法描述：

a. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　

b. 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

Floyd算法过程矩阵的计算—-十字交叉法

方法：两条线，从左上角开始计算一直到右下角 如下所示

先来简单分析下,由于矩阵中对角线上的元素始终为0,因此以k为中间点时,从上一个矩阵到下一个矩阵变化时,矩阵的第k行,第k列和对角线上的元素是不发生改变的（对角线上都是0，因为一个顶点到自己的距离就是0，一直不变；而当k为中间点时，k到其他顶点（第k行）和其他顶点到k（第k列）的距离是不变的）。

因此每一步中我们只需要判断4*4-3*4+2=6个元素是否发生改变即可,也就是要判断既不在第k行第k列又不在对角线上的元素。具体计算步骤如下：以k为中间点（1）“三条线”：划去第k行，第k列，对角线（2）“十字交叉法”：对于任一个不在三条线上的元素x，均可与另外在k行k列上的3个元素构成一个2阶矩阵，x是否发生改变与2阶矩阵中不包含x的那条对角线上2个元素的和有关，若二者之和小于x，则用它们的和替换x，对应的Path矩阵中的与x相对应的位置用k来替代。。

给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点（指的是u->….->该点->v）

分别以每一个点作为K点转接v

image
image
image
image

代码实现

java 版本

核心代码只有 4 行，实在令人赞叹。  [java]

private void floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = Math.min(a[i][j], a[i][k] + a[k][j]);
            }
        }
    }

    // 打印
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            System.out.println(i + " " + j + ":" + a[i][j]);
        }
    }
}

正确性分析

核心代码只有四行，三行循环，一行更新，的确十分简洁优雅，可是这四行代码为什么就能求出任意两点的最短路径呢？

看代码的特点，很显然特别像是一种动态规划，确实，之前也说过该算法是基于动态规划的。

我们从动态规划的角度考虑，解动态规划题目的重点就是合理的定义状态，划分阶段，我们定义 f[k][i][j] 为经过前k的节点，从i到j所能得到的最短路径，f[k][i][j]可以从f[k-1][i][j]转移过来，即不经过第k个节点，也可以从f[k-1][i][k]+f[k-1][k][j]转移过来，即经过第k个节点。

观察一下这个状态的定义，满足不满足最优子结构和无后效性原则。

  • 最优子结构

图结构中一个显而易见的定理：

最短路径的子路径仍然是最短路径, 这个定理显而易见，比如一条从a到e的最短路a->b->c->d->e 那么 a->b->c 一定是a到c的最短路c->d->e一定是c到e的最短路，反过来，如果说一条最短路必须要经过点k，那么i->k的最短路加上k->j的最短路一定是i->j 经过k的最短路，因此，最优子结构可以保证。

  • 无后效性

状态f[k][i][j]由f[k-1][i][j]，f[k-1][i,k] 以及f[k-1][k][j]转移过来，很容易可以看出，f[k] 的状态完全由f[k-1]转移过来，只要我们把k放倒最外层循环中，就能保证无后效性。

满足以上两个要求，我们即证明了Floyd算法是正确的。

我们最后得出一个状态转移方程：f[k][i][j] = min(f[k-1][i][k],f[k-1][i][k],f[k-1][k][j]) ，可以观察到，这个三维的状态转移方程可以使用滚动数组进行优化。

K 为什么要放在最外层

采用动态规划思想，f[k][i][j] 表示 i 和 j 之间可以通过编号为 1…k 的节点的最短路径。

f[0][i][j] 初值为原图的邻接矩阵。

f[k][i][j]则可以从f[k-1][i][j]转移来，表示 i 到 j 不经过 k 这个节点。

也可以 f[k-1][i][k]+f[k-1][k][j] 从转移过来，表示经过 k 这个点。

意思即 f[k][i][j]=min(f[k-1][i][j], f[k-1][i][k]+f[k-1][k][j])

然后你就会发现 f 最外层一维空间可以省略，因为 f[k] 只与 f[k-1] 有关。

虽然这个算法非常简单，但也需要找点时间理解这个算法，就不会再有这种问题啦。

Floyd算法的本质是DP，而k是DP的阶段，因此要写最外面。

想象一个图，讨论的是要从1点到达3点，是直接走还是经过中间点2，从而确定两点之间的最短路径。

滚动数组优化

滚动数组是一种动态规划中常见的降维优化的方式，应用广泛（背包dp等），可以极大的减少空间复杂度。

在我们求出的状态转移方程中，我们在更新f[k]层状态的时候，用到f[k-1]层的值，f[k-2] f[k-3]层的值就直接废弃了。

所以我们大可让第一层的大小从n变成2,再进一步，我们在f[k]层更新f[k][i][j]的时候，f[k-1][i][k] 和 f[k-1][k][j] 我们如果能保证，在更新k层另外一组路径m->n的时候，不受前面更新过的f[k][i][j]的影响，就可以把第一维度去掉了。

我们现在去掉第一个维度，写成我们在代码中的那样，就是f[i][j] 依赖 f[i][k] + f[k][j] 我们在更新f[m][n]的时候，用到了f[m][k] + f[k][n] 假设f[i][j]的更新影响到了f[m][k] 或者 f[k][m] 即 {m=i,k=j} 或者 {k=i,n=j} 这时候有两种情况，j和k是同一个点，或者i和k是同一个点，那么 f[i][j] = f[i][j] + f[j][j]，或者f[i][j] = f[i][i]+f[i][j] 这时候，我们所谓的“前面更新的点对”还是这两个点本来的路径，也就是说，唯一两种在某一层先更新的点，影响到后更新的点的情况，是完全合理的，所以说，我们即时把第一维去掉，也满足无后效性原则。

因此可以用滚动数组优化。

优化之后的状态转移方程即为：f[i][j] = min(f[i][j],f[i][k]+f[k][j])。

求具体路径：

我们上面仅仅是知道了最短路径的长度，实际应用中我们常常是需要知道具体的路径，在Floyd算法中怎么求具体路径呢，很简单，我们只需要记录下来在更新f[i][j]的时候，用到的中间节点是哪个就可以了。

假设我们用path[i][j]记录从i到j松弛的节点k，那么从i到j,肯定是先从i到k，然后再从k到j， 那么我们在找出path[i][k] , path[k][j]即可。

即 i到k的最短路是 i -> path[i][k] -> k -> path[k][j] -> k q` 然后求path[i][k]和path[k][j] ，一直到某两个节点没有中间节点为止，代码如下：

在更新路径的时候：  [java]

if(a[i][k]>temp){
    a[i][j] = temp;
    path[i][j] = k;
}

求路径的时候：  [java]

public String getPath(int[][] path, int i, int j) {
    if (path[i][j] == -1) {
        return " "+i+" "+j;
    } else {
        int k = path[i][j];
        return getPath(path, i, k)+" "+getPath(path, k, j)+" ";
    }
}

总结

Floyd算法只能在不存在负权环的情况下使用，因为其并不能判断负权环，上面也说过，如果有负权环，那么最短路将无意义，因为我们可以不断走负权环，这样最短路径值便成为了负无穷。

但是其可以处理带负权边但是无负权环的情况。

以上就是求多源最短路的Floyd算法，基于动态规划，十分优雅。

但是其复杂度确实是不敢恭维，因为要维护一个路径矩阵，因此空间复杂度达到了O(n^2)，时间复杂度达到了O(n^3)，只有在数据规模很小的时候，才适合使用这个算法，但是在实际的应用中，求单源最短路是最常见的，比如在路由算法中，某个节点仅需要知道从这个节点出发到达其他节点的最短路径，而不需要知道其他点的情况，因此在路由算法中最适合的应该是单源最短路算法，Dijkstra算法。

Hierholzer 算法 —有向图求解欧拉路径（环路）

  • 欧拉路径：
    如果在一张图中，可以从一点出发遍历所有的边，那么遍历过程中的这条路径就叫做欧拉路径。如果这条路径是闭合的，那就称为欧拉回路。
    简单地说，如果一张图可以被“一笔画”，那么“一笔画”的那个轨迹就叫做欧拉路径。
  • 欧拉图判定定理：
    含有欧拉回路的图称为欧拉图，含有欧拉路径的图称为半欧拉图。
    无向图中，如果所有顶点的度数都为偶数，则为欧拉图；如果有两个顶点的度数为奇数，其他的为偶数，则为半欧拉图。
    有向图中，如果所有顶点的入度等于出度，那么就是欧拉图。判定半欧拉图的方法也很简单，大家可以自行推理。

Hierholzer 算法

问题简述：现给出一个有向图，且为欧拉图。求欧拉回路。

Hierholzer 算法过程：

  1. 选择任一顶点为起点，遍历所有相邻边。
  2. 深度搜索，访问相邻顶点。将经过的边都删除。
  3. 如果当前顶点没有相邻边，则将顶点入栈。
  4. 栈中的顶点倒序输出，就是从起点出发的欧拉回路。

从一个可能的起点出发，进行深度优先搜索，但是每次沿着辅助边从某个顶点移动到另外一个顶点的时候，都需要删除这个辅助边。如果没有可移动的路径，则将所在结点加入到栈中，并返回。

dfs(node, trace){
	while(!node.adj.isEmpty()){
		Node next = node.adj.removeLast();
		dfs(next, trace);
	}
	trace.addLast(node);
}

最后得到的栈中保存的就是整个欧拉闭迹中的顶点。（要恢复我们需要不断出栈，因此如果你用列表来存欧垃迹的话需要反转一次）。

重新安排行程：给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次且只能用一次。

在这里插入图片描述
class Solution:
    ''' Hierholzer 算法
    '''
    def findItinerary(self, tickets):
        def dfs(cur, graph, res):
            while graph[cur]: # 遍历所有边
                dfs(graph[cur].pop(), graph, res) # 访问并删除
            if not graph[cur]: # 将顶点入栈
                res.append(cur)
        import collections
        # 建图
        graph = collections.defaultdict(list)
        for start, end in sorted(tickets)[::-1]:
            graph[start].append(end)
        res = []
        dfs("JFK", graph, res)
        return res[::-1] # 倒序输出

dijkstra算法求最短路径

基本思想

dijkstra的算法思想是从以上最短距离数组中每次选择一个最近的点，将其作为下一个点，然后重新计算从起始点经过该点到其他所有点的距离，更新最短距离数据。已经选取过的点就是确定了最短路径的点，不再参与下一次计算。

  1. 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。
  2. 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
  3. 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。

操作步骤

  1. 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
  2. 从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k。
  3. 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
  4. 重复步骤(2)和(3)，直到遍历完所有顶点。

第1步：初始化距离，其实指与D直接连接的点的距离。dis[c]代表D到C点的最短距离，因而初始dis[C]=3，dis[E]=4，dis[D]=0，其余为无穷大。设置集合S用来表示已经找到的最短路径。此时，S={D}。现在得到D到各点距离{D(0)，C(3)，E（4），F（*），G（*），B（*），A(*)}，其中*代表未知数也可以说是无穷大，括号里面的数值代表D点到该点的最短距离。

第2步：不考虑集合S中的值，因为dis[C]=3，是当中距离最短的，所以此时更新S，S={D,C}。接着我们看与C连接的点，分别有B，E，F，已经在集合S中的不看，dis[C-B]=10，因而dis[B]=dis[C]+10=13，dis[F]=dis[C]+dis[C-F]=9，dis[E]=dis[C]+dis[C-E]=3+5=8>4(初始化时的dis[E]=4)不更新。此时{D(0)，C(3)，E（4），F（9），G（*），B（13），A(*)}。

第3步：在第2步中，E点的值4最小，更新S={D，C，E}，此时看与E点直接连接的点，分别有F，G。dis[F]=dis[E]+dis[E-F]=4+2=6（比原来的值小，得到更新），dis[G]=dis[E]+dis[E-G]=4+8=12（更新）。此时{D(0)，C(3)，E（4），F（6），G（12），B（13），A(*)}。

第4步：在第3步中，F点的值6最小，更新S={D，C，E，F}，此时看与F点直接连接的点，分别有B，A，G。dis[B]=dis[F]+dis[F-B]=6+7=13，dis[A]=dis[F]+dis[F-A]=6+16=22，dis[G]=dis[F]+dis[F-G]=6+9=15>12（不更新）。此时{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

第5步：在第4步中，G点的值12最小，更新S={D，C，E，F，G}，此时看与G点直接连接的点，只有A。dis[A]=dis[G]+dis[G-A]=12+14=26>22(不更新)。{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

第6步：在第5步中，B点的值13最小，更新S={D，C，E，F，G，B}，此时看与B点直接连接的点，只有A。dis[A]=dis[B]+dis[B-A]=13+12=25>22(不更新)。{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

第6步：最后只剩下A值，直接进入集合S={D，C，E，F，G，B，A}，此时所有的点都已经遍历结束，得到最终结果{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

python实现：

将以上的过程使用python来实现。
首先总结一个Dijkstra算法的核心思想，分成两步走：

  1. 构造一个最短路径数组，每次找到数组中未访问的节点里最小的点
  2. 以上一步的节点为最新节点，更新起始点到所有点的距离

使用python就是实现这两步即可



MAX= float('inf')

matrix = [
    [0,10,MAX,4,MAX,MAX],
    [10,0,8,2,6,MAX],
    [MAX,8,10,15,1,5],
    [4,2,15,0,6,MAX],
    [MAX,6,1,6,0,12],
    [MAX,MAX,5,MAX,12,0]
    ]


def dijkstra(matrix, start_node):
    
    #矩阵一维数组的长度，即节点的个数
    matrix_length = len(matrix)

    #访问过的节点数组
    used_node = [False] * matrix_length

    #最短路径距离数组
    distance = [MAX] * matrix_length

    #初始化，将起始节点的最短路径修改成0
    distance[start_node] = 0
    
    #将访问节点中未访问的个数作为循环值，其实也可以用个点长度代替。
    while used_node.count(False):
        min_value = float('inf')
        min_value_index = 999
        
        #在最短路径节点中找到最小值，已经访问过的不在参与循环。
        #得到最小值下标，每循环一次肯定有一个最小值
        for index in range(matrix_length):
            if not used_node[index] and distance[index] < min_value:
                min_value = distance[index]
                min_value_index = index
        
        #将访问节点数组对应的值修改成True，标志其已经访问过了
        used_node[min_value_index] = True

        #更新distance数组。
        #以B点为例：distance[x] 起始点达到B点的距离，
        #distance[min_value_index] + matrix[min_value_index][index] 是起始点经过某点达到B点的距离，比较两个值，取较小的那个。
        for index in range(matrix_length):
            distance[index] = min(distance[index], distance[min_value_index] + matrix[min_value_index][index])

    return distance




start_node = int(input('请输入起始节点:'))
result = dijkstra(matrix,start_node)
print('起始节点到其他点距离：%s' % result)

数据结构 — 单调队列

顾名思义，单调队列的重点分为 “单调” 和 “队列”

“单调” 指的是元素的的 “规律”——递增（或递减）

“队列” 指的是元素只能从队头和队尾进行操作

  • 单调递增队列：保证队列头元素一定是当前队列的最小值，用于维护区间的最小值。
  • 单调递减队列：保证队列头元素一定是当前队列的最大值，用于维护区间的最大值。

1、对于单调递增队列，对于一个元素如果它大于等于队尾元素， 那么直接把元素进队， 如果这个元素小于队尾元素，则将队尾元素出队列，直到满足这个元素大于等于队尾元素。

2、对于单调递减队列，对于一个元素如果它小于等于队尾元素， 那么直接把元素进队， 如果这个元素大于队尾元素，则将队尾元素出队列，直到满足这个元素小于等于队尾元素。

3、判断队头元素是否在待求解的区间之内，如果不在，就将其删除。（这个很好理解呀，因为单调队列的队头元素就是待求解区间的极值）

4、经过上面两个操作，取出 队列的头元素 ，就是 当前区间的极值 。

可以发现队列中的元素都是单调递减的（不然也就不叫单调递减队列啦），同时既有入队列的操作、也有出队列的操作。

实现单调队列，主要分为三个部分：

  • 去尾操作 ：队尾元素出队列。当队列有新元素待入队，需要从队尾开始，删除影响队列单调性的元素，维护队列的单调性。(删除一个队尾元素后，就重新判断新的队尾元素)

去尾操作结束后，将该新元素入队列。

  • 删头操作 ：队头元素出队列。判断队头元素是否在待求解的区间之内，如果不在，就将其删除。（这个很好理解呀，因为单调队列的队头元素就是待求解区间的极值）
  • 取解操作 ：经过上面两个操作，取出 队列的头元素 ，就是 当前区间的极值 。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define maxn 1000100
using namespace std;
int q[maxn], a[maxn];
int n, k;

void getmin() {  // 得到这个队列里的最小值，直接找到最后的就行了
  int head = 0, tail = 0;
  for (int i = 1; i < k; i++) {
    while (head <= tail && a[q[tail]] >= a[i]) tail--;
    q[++tail] = i;
  }
  for (int i = k; i <= n; i++) {
    while (head <= tail && a[q[tail]] >= a[i]) tail--;
    q[++tail] = i;
    while (q[head] <= i - k) head++;
    printf("%d ", a[q[head]]);
  }
}

void getmax() {  // 和上面同理
  int head = 0, tail = 0;
  for (int i = 1; i < k; i++) {
    while (head <= tail && a[q[tail]] <= a[i]) tail--;
    q[++tail] = i;
  }
  for (int i = k; i <= n; i++) {
    while (head <= tail && a[q[tail]] <= a[i]) tail--;
    q[++tail] = i;
    while (q[head] <= i - k) head++;
    printf("%d ", a[q[head]]);
  }
}

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  getmin();
  printf("\n");
  getmax();
  printf("\n");
  return 0;
}

Python3 迭代器与生成器

迭代器

迭代是Python最强大的功能之一，是访问集合元素的一种方式。

迭代器是一个可以记住遍历的位置的对象。

迭代器对象从集合的第一个元素开始访问，直到所有的元素被访问完结束。迭代器只能往前不会后退。

迭代器有两个基本的方法：iter() 用于生成迭代器 和 next() 求迭代器的值。

字符串，列表或元组对象都可用于创建迭代器：

>>> list=[1,2,3,4]
>>> it = iter(list)    # 创建迭代器对象
>>> print (next(it))   # 输出迭代器的下一个元素
1
>>> print (next(it))
2
>>>

迭代器对象可以使用常规for语句进行遍历：

list=[1,2,3,4]
it = iter(list)    # 创建迭代器对象
for x in it:
    print (x, end=" ")

执行以上程序，输出结果如下：

1 2 3 4

也可以使用 next() 函数：

import sys         # 引入 sys 模块
 
list=[1,2,3,4]
it = iter(list)    # 创建迭代器对象
 
while True:
    try:
        print (next(it))
    except StopIteration:
        sys.exit()

执行以上程序，输出结果如下：

1
2
3
4

创建一个迭代器

把一个类作为一个迭代器使用需要在类中实现两个方法 __iter__() 与 __next__() 。

如果你已经了解的面向对象编程，就知道类都有一个构造函数，Python 的构造函数为 __init__(), 它会在对象初始化的时候执行。

更多内容查阅：Python3 面向对象

__iter__() 方法返回一个特殊的迭代器对象， 这个迭代器对象实现了 __next__() 方法并通过 StopIteration 异常标识迭代的完成。

__next__() 方法（Python 2 里是 next()）会返回下一个迭代器对象。

创建一个返回数字的迭代器，初始值为 1，逐步递增 1：

class MyNumbers:
  def __iter__(self):
    self.a = 1
    return self
 
  def __next__(self):
    x = self.a
    self.a += 1
    return x
 
myclass = MyNumbers()
myiter = iter(myclass)
 
print(next(myiter))
print(next(myiter))
print(next(myiter))
print(next(myiter))
print(next(myiter))

执行输出结果为：

1
2
3
4
5

StopIteration

StopIteration 异常用于标识迭代的完成，防止出现无限循环的情况，在 __next__() 方法中我们可以设置在完成指定循环次数后触发 StopIteration 异常来结束迭代。

在 20 次迭代后停止执行：

class MyNumbers:
  def __iter__(self):
    self.a = 1
    return self
 
  def __next__(self):
    if self.a <= 20:
      x = self.a
      self.a += 1
      return x
    else:
      raise StopIteration
 
myclass = MyNumbers()
myiter = iter(myclass)
 
for x in myiter:
  print(x)

执行输出结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

生成器

yield是python的一个关键字，本质上是一个生成器generator。

生成器是一种特殊的函数，它会返回一个迭代器。定义一个生成器函数同定义一个普通函数没有什么区别，特殊之处在于生成器函数内部会包含yield表达式，专门用于生成一个序列。当一个生成器函数被调用时，它会返回一个迭代器。之后就由这个迭代器来控制生成器函数的执行。当生成器函数被调用后，首先会执行到第一个yield表达式处，然后会将生成器函数挂起，将yield生成的表达式的值返回给生成器函数的调用者。当生成器函数被挂起时，它的所有局部状态都会被保存起来，包括当前绑定的局部变量、指令指针、内部栈和异常处理的状态。当调用迭代器的方法时，一般都是调用next()方法，将会恢复生成器函数的执行，并且是从上次被挂起的地方继续执行，直到遇到另外一次yield调用，生成器函数将再次被挂起。

在一个生成器函数中，如果没有 return，则默认执行至函数完毕，如果在执行过程中 return，则直接抛出 StopIteration 终止迭代。

可以中断一个函数的执行，跳转到调用的地方

在 Python 中，使用了 yield 的函数被称为生成器（generator）。

跟普通函数不同的是，生成器是一个返回迭代器的函数，只能用于迭代操作，更简单点理解生成器就是一个迭代器。

在调用生成器运行的过程中，每次遇到 yield 时函数会暂停并保存当前所有的运行信息，返回 yield 的值, 并在下一次执行 next() 方法时从当前位置继续运行。

调用一个生成器函数，返回的是一个迭代器对象。

以下实例使用 yield 实现斐波那契数列：

import sys
 
def fibonacci(n): # 生成器函数 - 斐波那契
    a, b, counter = 0, 1, 0
    while True:
        if (counter > n): 
            return
        yield a
        a, b = b, a + b
        counter += 1
f = fibonacci(10) # f 是一个迭代器，由生成器返回生成
 
while True:
    try:
        print (next(f), end=" ")
    except StopIteration:
        sys.exit()

执行以上程序，输出结果如下：

0 1 1 2 3 5 8 13 21 34 55