16.2 按照“辈分”顺序取出元素

通过以上修改，在进行普通计算(即正向传播)时，变量和函数中会设置好generation的值。下面来看图16-3所示的计算图。

图16-3 计算图中“辈分”的例子

从图16-3可以看到，函数A的generation的值是0，函数B和函数C的

generation的值是1，函数D的generation的值是2。按照这种方式设置之后，DeZero在反向传播中就可以按照正确的顺序取出函数了。例如，generation的值更大的函数B和函数C可以先于函数A被取出。

如前所述，在Variable类的backward方法中，我们把要处理的候补函数放入funcs列表中。之后从列表中取出函数时，首先取出generation的值最大的函数，这样就可以按照正确的顺序进行函数的反向传播了。

接下来要实现的是按照“辈分”顺序取出函数。在此之前，我们先用一个虚拟的DeZero函数做一个简单的实验。

>>>generations  $= [2$  ，0，1，4，2]  
>>>funcs  $= []$    
>>>for g in generations:  
... f  $=$  Function() #虚拟的函数类  
... f_generation  $=$  g  
...funcs.append(f)  
>>>[f_generation for f infuncs][2，0，1，4，2]

上面的代码准备了虚拟的函数，并将其添加到了funcs列表中。下面我们从这个列表中取出generation的值最大的函数。代码如下所示。

>>>funcs.sort(key=lambda x: x_generation)  
>>> [f_generation for f infuncs]  
[0, 1, 2, 2, 4]  
>>> f =funcs.pop()  
>>> f_generation  
4

上面的代码通过列表的sort方法将列表按generation的值从小到大的顺序排列。具体做法是指定key=lambda x: x_generation作为sort方法的参数，

如果 $x$ 是列表中的元素，则列表中的元素按照 $x$ .generation 的值从小到大的顺序排列。然后，使用 pop 方法取出列表的最后一个元素，这个元素就是 generation 的值最大的函数。

我们这里要做的只是取出generation的值最大的函数，所以没有必要像前面那样对所有元素重新排序。更高效的做法是使用优先队列算法，不过本书没有采用这种方法，感兴趣的读者可以自行实现（提示：Python有heapq模块）。