For this homework, we asked you to remove dead code.
That is code that could not have any effect
on the final return result of the method we’re
interested in. So, let’s go ahead and just dive right
into this. We take a fragment; if you remember
the fragments are of this shape where the first part
of the tuple is the variable to be assigned to and
then the next part of the tuple is the expression
that is being assigned to it, in this case one is
being assigned to A or A operational, one is being
assigned to B, 2 is being assigned to C etcetera.
Now we’re not really concerned with what
specifically the operations are. We don’t care
what operations are being done. We just care that
something is being done to these variables,
because if there is something being done, even if
it ends up setting them to the exact same thing, we
can’t necessarily know that ahead of time. So, if
you have a fragment of this shape, then we store
that as the old fragment, as the un-optimized
fragment. And that’s the first argument to this
method. And the return is the end return value;
it’s the list of variables returned at the end of the
fragment. And if they’re returned at the end of the
fragment, they’re automatically live, as we said
up here. Now we want to create a new optimized
fragment of just the live variables. So we start off
by initializing that to an empty list. And we set a
variable called live equal to the returned live
variables, because we know those are live.
Now for every statement in the fragment starting from
the back, so we’re working backwards from the
return statement, back up to the top, we check if
the first element of the tuple statement, that is the
left hand side of the statement, is already in live.
That is, it is one of the live variables currently.
If it is, then we add that statement to the new
optimized fragment. Otherwise we fall through
and now we take the list of live variables and we
remove the variables that we’re now assigning to.
So we take all those out. From there, we update
the live list with all the variables that are currently
on the right hand side of statement. We run
through the entire fragment doing that over and
over until we get back to the top. Once we’re
done with that, we check if the new fragment is
equal to the old fragment. If it is, then we return
the new fragment. We didn’t change anything.
So we just return and stop and we’re done. If it isn’t,
well, then we might have further optimizations as
we discussed earlier. Then we return, removing
dead of the new fragment in return. So we
recursively call this until we don’t get any
further changes, because hopefully we can
optimize further. Now we’re going to check that
removed dead gives us what we would expect if
we ran through all the optimizations by hand, and
I’m not going to bother going through all of these.
You can read them fairly easily and when we do
that, we see that we get true values for each of
these. This is a fairly involved little bit of code.
It takes a little bit to think about and this is a
very useful optimization because we can
potentially get rid of a lot of code doing this.
この宿題はデッドコードを取り除く問題でした
注目している関数の最後のreturnに
何の影響もないのがデッドコードです
やっていきましょう
まずコードの一部を作ります
このタプルの最初の部分が
代入される変数で
次が代入される式です
この場合aに1が代入され
bにaと1を計算したものが入りcに2が代入されます
この演算が何であるかは特に気にしません
どのような演算が行われたかはどうでもよいのです
変数に何かが行われたということが重要です
何かが行われていて
それが同じものになるとしても 今はどうなるかわかりません
このような形の断片があれば古いコード片や 最適化前のコード片として保存します
それがこの関数の最初の引数です
returnedは最終的な返り値
つまり最後にreturnされる式に含まれる 変数のリストです
それが最後に返されるものに入っていれば ルールどおり生きています
生きた変数についての新しいリストを作ります
まずそれを空のリストnew＿fragmentとします
変数liveは生きた変数だと 知っているものを入れるので
まず返される変数を代入します
そしてそれぞれの文ごとに コード片を後ろから始めます
つまりreturn文から始めて一番上に戻るまで
タプルの最初の要素が
既にliveに含まれているかどうか調べます
もし生きている変数なら
その文を新しいコード片に含めますが
そうでない場合そのまま無視します
今度は生きた変数のリストを取り
代入される変数を取り除きます
それをすべて取り除き
生きた変数のリストを 右側にある変数に加えて更新します
これを繰り返し一番上の行に達するまで続けます
それが終わったら 新しいコード片が古いコード片と同じかを調べます
同じなら新しいコード片を返します 何も変えませんでした
ここで最適化を止めて終わりです
同じでなければ最適化ができるかもしれないので 新しいコード片からもデッドコードを除去します
最適化が続けられるかもしれないので
再帰的に自身を呼び出し続け 更新がなくなるまで続けます
今度もデッドコードを削除したらどうなるのか
手計算したもので確かめます
簡単に読めるはずなので すべては解説しません
テストを走らせると それぞれTrueになります
かなり最適化をしたコードになりました
考えることは多いですが 多くのコードを取り除ける可能性があるので
これはとても有効な最適化の手法です
Neste execício, pedimos que você removesse código morto,
que é código que não tem nenhum efeito sobre
o resultado retornado pela função que nos interessa.
Então, vamos prosseguir, e fazer exatamente isso.
Pegamos aqui um fragmento -- e lembre-se,
fragmentos têm essa forma, onde a primeira parte
da tupla é a variável à qual atribuímos e
a parte seguinte da tupla é a expressão que
é atribuída a ela -- neste caso, atribuímos a=1,
ou b = a+1,
ou c = 2 etc.
Não estamos realmente preocupados com o que são
especificamente as operações -- não nos importa
que operações são feitas. O que nos importa é
que algo está sendo atribuído a essas variáveis,
porque, se algo está sendo atribuído,
mesmo que o resultado possa ser exatamente o mesmo,
não necessariamente sabemos isso antecipadamente.
Então, se temos um fragemento dessa forma, nós
guardamos isso como old_fragment -- como um fragmento
não otimizado -- este é o primeiro argumento desta função.
E returned é o valor retornado --
é a lista de variáveis retornadas no final do fragmento.
E se elas são retornadas no fianl do fragmento,
elas automaticamente são vivas, como dizemos aqui.
Agora, nós queremos criar um novo fragmento otimizado,
que contenha apenas variáveis vivas. Então, começamos
inicializando isso com a lista vazia e atribuindo à variável
live as variáveis retornadas -- returned --
porque sabemos que estas estão vivas.
Agora, para cada comando do fragmento, começando
do final, de modo que trabalhamos para trás, a partir
do comando return até o início, verificamos se
o primeiro elemento da tupla de comando, isto é,
o lado esquerdo do comando, é uma variável viva, isto é,
se é uma das variáveis de live correntemente.
Se for, então adicionamos este comando ao novo
fragmento otimizado. Caso contrário, descemos
e agora pegamos a lista de variáveis vivas e
removemos a variável à qual estamos fazendo a atribuição.
Então, retiramos tudo isso. Depois disso, atualizamos
a lista live com as variáveis que estão no lado direito
do comando de atribuição. Percorremos todo
o fragmento, fazendo isso repetidamente,
até que chegamos ao inicio. Quando terminamos
isso, verificamos se o novo fragmento é igual
ao antigo fragmento. Se for, então retornamos
o novo fragmento -- nós não alteramos nada e,
portanto, simplesmente retornamos e terminamos.
Se não for, então podemos teer novas otimizações a fazer,
como discutimos anteriormente. Então retornamos, removendo
código morto do novo fragmento.
Então, chamamos isso recursivamente, até que
não haja novas mudanças, já que podem haver
novas otimizações. Agora vamos verificar se
removedead nos dá o que esperamos, quando
o executamos à mào para cada uma das otimizações.
Mas eu não vou mostrar cada uma detalhadamente.
Você pode lê-las muito facilmente e, quando fazemos isso,
podemos ver que obtemos o valor True para cada uma.
Esse é um código muito interessante.
Demora um pouco para entender bem, mas isso
é uma otimização muito útil, porque você pode,
potencialmente, eleminar um bocado de código, fazendo isso.