python再帰と装飾器
25421 ワード
一:再帰
特長
再帰アルゴリズムは、自己アルゴリズムを直接または間接的に呼び出すプロセスである.コンピュータ作成プログラムでは、再帰アルゴリズムは大きな問題を解決するのに非常に有効であり、アルゴリズムの記述を簡潔にし、理解しやすいことが多い.
再帰アルゴリズムによる問題解決の特徴:
(1)再帰とは,プロセスや関数で自身を呼び出すことである.
(2)再帰ポリシーを使用する場合、再帰出口と呼ばれる明確な再帰終了条件が必要である.
(3)再帰アルゴリズム解題は通常簡潔に見えるが,再帰アルゴリズム解題の実行効率は低い.再帰アルゴリズムでプログラムを設計することは一般的に提唱されていない.
(4)再帰呼び出しの過程において,システムは各層の戻り点,局所量などにスタックを開いて格納する.再帰回数が多すぎるとスタックオーバーフローなどが起こりやすい.再帰アルゴリズムでプログラムを設計することは一般的に提唱されていない.
要求
再帰アルゴリズムが表す「繰り返し」には、一般的に3つの要件があります.
(1)呼び出しのたびに規模が縮小する(通常は半減する).
(2)隣接する2回の繰り返しの間に密接なつながりがあり、前回は前回の準備をする(通常、前回の出力は前回の入力とする).
(3)問題の規模が極めて小さい場合は,再帰呼び出しを行わずに直接解答を与える必要があるため,再帰呼び出しのたびに条件があり(直接解答の大きさに達していないことを条件として),無条件再帰呼び出しはデッドサイクルとなり正常に終了しない.
インプリメンテーション
1.再帰による2点検索
既存リストprimes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]は,23を最速で見つけることを要求している.この質問には、Low B、Low 2 B、Low 3 Bの3人の同級生が答えてください.
a)Low B:これは簡単です.if 41 inprimes:print(「found it!」を直接使います.話が終わらないうちに先生に殴られて、あなたに自分で実現させて、あなたに既成の提供する機能を使うのではありませんて、Low Bはそこで言って、それは最初から1つ1つ数えるしかなくて、それからLow Bは除名されました.の
b)Low 2 B:このリストは秩序があるので、リストを半分切り取ることができます.
p1 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,37,41]
p2 = [ 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,97]
そしてp 1[-1]つまり41が23より大きいかどうかを見て、23より大きいと23がp 1の中にいることを意味して、さもなくばp 2の中にあることを意味します.今、私たちは23が41より小さいことを知っています.だから、23はp 1の中にあるに違いありませんが、p 1の中には依然として多くの要素があります.どうやって23を見つけますか.簡単ですが、前回の方法でp 1を2つの部分に分けて、以下のようにします.
p1_a = [2, 3, 5, 7, 11, 13,17]
p1_b = [19, 23, 29, 31, 37,41]
23対p 1_a最後の値は17で、それは23がp 1にあることを意味します.b中、p 1_bには依然として多くの要素があります.それでは、前の方法で半分に分け続けます.最終的には何度も使えません.23を見つけたに違いありません.
そう言って、Low 2 Bは達成感たっぷりに頭のフケを振った.
先生:いいですね.確かにLow Bの案よりずっと強いです.それからLow 3 Bに振り向いて、あなたはもっと良い考えがありますか?
Low 3 B:あ..ああ、私は...私はLow 2 Bの考えと同じで、結局彼に言われました.
先生:ああ、じゃ、コードを書いてください.
Low 3 Bはこの時冷や汗をかいていた.彼は全然考えていなかったので、無理に書いた...自分では考えられませんが、グーグルができますね.3時間が過ぎて、やっと以下のコードを我慢しました.
def binary_search(data_list,find_num): mid_pos = int(len(data_list)/2 ) #find the middleposition of the list mid_val = data_list[mid_pos] #get the value by it's position print(data_list) if len(data_list) >1: if mid_val> find_num: # means thefind_num is in left hand of mid_val print("[%s] should be in left of [%s]"%(find_num,mid_val)) binary_search(data_list[:mid_pos],find_num) elif mid_val< find_num: # means thefind_num is in the right hand of mid_val print("[%s] should be in right of [%s]"%(find_num,mid_val)) binary_search(data_list[mid_pos:],find_num) else: # means the mid_val == find_num print("Find ", find_num) else: print("cannot find [%s] in data_list"%find_num) if __name__ == '__main__': primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] binary_search(primes,67)
二:装飾器:
装飾器は有名な設計モデルで、断面的なニーズのあるシーンによく使われ、挿入ログ、パフォーマンステスト、トランザクションなどが古典的です.装飾器はこのような問題を解決する絶好の設計であり、装飾器があれば、多くの関数の中で関数機能自体に関係のない同じコードを抽出し、再利用を続けることができます.要約すると、装飾器の役割は、既存のオブジェクトに追加の機能を追加することです.
装飾器の定義は抽象的で、小さな例を見てみましょう.
これはつまらない関数で間違いありません.しかし、突然もっと退屈な人がいて、私たちは彼をB君と呼んで、私はこの関数を実行するのにどのくらいの時間がかかったかを見たいと言っています.いいでしょう.では、私たちはこのようにすることができます.
いいですね.機能に手抜かりがないように見えます.しかし、卵が痛いB君は今突然この関数を見たくなくなり、foo 2というもう一つの関数にもっと興味を持っています.
どうしようかな?以上新しく追加されたコードをfoo 2にコピーすると、これはタブーです~コピーなんて大嫌いじゃないですか!そして、B君が他の関数を見続けたら?
1.2. 不変で変化に応じて、変化である.
覚えていますか、関数はPythonの中で1等公民で、それでは私达は1つの関数timeitを再定义することを考えることができて、fooの引用を彼に渡して、それからtimeitの中でfooを呼び出して时间を计って、このようにして、私达はfooの定义を変更しない目的を达成して、その上、B君がどれだけの関数を见て、私达はすべて関数の定义を修正する必要はありません!
論理的には問題ないように見えますが、すべてが美しく、正常に動作しています!......など、呼び出し部分のコードを変更したようです.もともと私たちはこのように呼び出した:foo()で、修正してから:timeit(foo)になりました.そうすると、fooがNで呼び出されたら、このNのコードを修正しなければなりません.あるいは極端には、どこかで呼び出されたコードがこの状況を修正できないことを考慮します.例えば、この関数は他の人に渡されて使用されています.
1.3. 変更を最小限に!
それなら、呼び出しのコードを変更しない方法を考えてみましょう.呼び出しコードを変更しない場合は、foo()を呼び出すにはtimeit(foo)を呼び出す効果が必要であることを意味します.私たちはtimeitをfooに割り当てることを考えることができますが、timeitにはパラメータがあるようです......パラメータを統一する方法を考えましょう!timeit(foo)が直接呼び出し効果を生じるのではなく、fooパラメータリストと一致する関数を返すと・・・やりやすいので、timeit(foo)の戻り値をfooに割り当て、foo()を呼び出すコードはまったく変更しなくてもいい!
これで、簡易タイマーができました!fooを定義してfooを呼び出す前にfoo=timeit(foo)を加えるだけで、計時の目的を達成することができます.これは装飾器の概念で、fooがtimeitに装飾されているように見えます.この例では、関数の入力と終了にはタイミングが必要であり、これを横断面(Aspect)と呼び、このプログラミング方式を切断面向けプログラミング(Aspect-OrientedProgramming)と呼ぶ.従来のプログラミング習慣の上から下への実行方式と比較すると,関数実行の流れに横方向に論理が挿入されているように見える.特定のビジネス分野では、コードの重複を大幅に減らすことができます.カットプログラミングに向けてかなりの用語がありますが、ここではあまり紹介しません.興味があれば関連資料を探してもいいです.この例はプレゼンテーションにのみ使用され、fooにパラメータがあり、戻り値がある場合は考慮されず、改善の重任はあなたに任せます:)
上のコードはもう簡略化できないように見えますが、Pythonは文字入力量を減らすために文法糖を提供しました.
11行目の@timeitに注目し、定義にこの行を加えると、foo=timeit(foo)と完全に等価であり、@に別の魔力があるとは思わないでください.文字入力が少なくなったほか、装飾品のように見えるという追加のメリットもあります.
1.4最後に、前述の質問に答えます.
2、装飾器の種類
2.1無パラメータ装飾器
最初の関数decoは装飾関数であり、そのパラメータは装飾された関数オブジェクトである.入力した関数オブジェクトをdeco関数内で「装飾」して返すことができます(必ず返すことを覚えておいてください.そうしないと、外でfooを呼び出す場所には関数がありません.実際にはfoo=deco(foo))
関数の説明ドキュメントがあるかどうかを確認するために、小さな例を書きました.
2.2パラメータ付装飾器
最初の関数decomakerは装飾関数で、そのパラメータは「装飾を強化する」ために使用されます.この関数は装飾された関数オブジェクトではないため、内部に少なくとも装飾された関数を受け入れる関数を作成し、このオブジェクトに戻る必要があります(実際にはfoo=decomaker(arg)(foo))
これは本当に良い例が思いつかないが、やはり見識が少ないので、同期ロックの例を借りるしかない.
呼び出し時はupdae(data)です.
複数の装飾品を組み合わせて使用することもできます.呼び出し順序に注意してください.
2.3内蔵の装飾器
内蔵の装飾器はstaticmethod,classmethod,propertyの3つあり,クラスで定義されたインスタンスメソッドを静的メソッド,クラスメソッド,クラスプロパティに変える役割を果たす.モジュールでは関数を定義できるので、オブジェクト向けに完全にプログラミングしない限り、静的メソッドとクラスメソッドの使用は多くありません.属性も欠かせないものではなく、Javaは属性がなくても潤いがあります.個人的なPythonの経験から、propertyを使ったことがなく、staticmethodやclassmethodを使う頻度も非常に低いです.
アクセサリーは以下の参考になります.http://www.cnblogs.com/huxi/archive/2011/03/01/1967600.html
特長
再帰アルゴリズムは、自己アルゴリズムを直接または間接的に呼び出すプロセスである.コンピュータ作成プログラムでは、再帰アルゴリズムは大きな問題を解決するのに非常に有効であり、アルゴリズムの記述を簡潔にし、理解しやすいことが多い.
再帰アルゴリズムによる問題解決の特徴:
(1)再帰とは,プロセスや関数で自身を呼び出すことである.
(2)再帰ポリシーを使用する場合、再帰出口と呼ばれる明確な再帰終了条件が必要である.
(3)再帰アルゴリズム解題は通常簡潔に見えるが,再帰アルゴリズム解題の実行効率は低い.再帰アルゴリズムでプログラムを設計することは一般的に提唱されていない.
(4)再帰呼び出しの過程において,システムは各層の戻り点,局所量などにスタックを開いて格納する.再帰回数が多すぎるとスタックオーバーフローなどが起こりやすい.再帰アルゴリズムでプログラムを設計することは一般的に提唱されていない.
要求
再帰アルゴリズムが表す「繰り返し」には、一般的に3つの要件があります.
(1)呼び出しのたびに規模が縮小する(通常は半減する).
(2)隣接する2回の繰り返しの間に密接なつながりがあり、前回は前回の準備をする(通常、前回の出力は前回の入力とする).
(3)問題の規模が極めて小さい場合は,再帰呼び出しを行わずに直接解答を与える必要があるため,再帰呼び出しのたびに条件があり(直接解答の大きさに達していないことを条件として),無条件再帰呼び出しはデッドサイクルとなり正常に終了しない.
インプリメンテーション
1.再帰による2点検索
既存リストprimes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]は,23を最速で見つけることを要求している.この質問には、Low B、Low 2 B、Low 3 Bの3人の同級生が答えてください.
a)Low B:これは簡単です.if 41 inprimes:print(「found it!」を直接使います.話が終わらないうちに先生に殴られて、あなたに自分で実現させて、あなたに既成の提供する機能を使うのではありませんて、Low Bはそこで言って、それは最初から1つ1つ数えるしかなくて、それからLow Bは除名されました.の
b)Low 2 B:このリストは秩序があるので、リストを半分切り取ることができます.
p1 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,37,41]
p2 = [ 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,97]
そしてp 1[-1]つまり41が23より大きいかどうかを見て、23より大きいと23がp 1の中にいることを意味して、さもなくばp 2の中にあることを意味します.今、私たちは23が41より小さいことを知っています.だから、23はp 1の中にあるに違いありませんが、p 1の中には依然として多くの要素があります.どうやって23を見つけますか.簡単ですが、前回の方法でp 1を2つの部分に分けて、以下のようにします.
p1_a = [2, 3, 5, 7, 11, 13,17]
p1_b = [19, 23, 29, 31, 37,41]
23対p 1_a最後の値は17で、それは23がp 1にあることを意味します.b中、p 1_bには依然として多くの要素があります.それでは、前の方法で半分に分け続けます.最終的には何度も使えません.23を見つけたに違いありません.
そう言って、Low 2 Bは達成感たっぷりに頭のフケを振った.
先生:いいですね.確かにLow Bの案よりずっと強いです.それからLow 3 Bに振り向いて、あなたはもっと良い考えがありますか?
Low 3 B:あ..ああ、私は...私はLow 2 Bの考えと同じで、結局彼に言われました.
先生:ああ、じゃ、コードを書いてください.
Low 3 Bはこの時冷や汗をかいていた.彼は全然考えていなかったので、無理に書いた...自分では考えられませんが、グーグルができますね.3時間が過ぎて、やっと以下のコードを我慢しました.
def binary_search(data_list,find_num): mid_pos = int(len(data_list)/2 ) #find the middleposition of the list mid_val = data_list[mid_pos] #get the value by it's position print(data_list) if len(data_list) >1: if mid_val> find_num: # means thefind_num is in left hand of mid_val print("[%s] should be in left of [%s]"%(find_num,mid_val)) binary_search(data_list[:mid_pos],find_num) elif mid_val< find_num: # means thefind_num is in the right hand of mid_val print("[%s] should be in right of [%s]"%(find_num,mid_val)) binary_search(data_list[mid_pos:],find_num) else: # means the mid_val == find_num print("Find ", find_num) else: print("cannot find [%s] in data_list"%find_num) if __name__ == '__main__': primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] binary_search(primes,67)
二:装飾器:
装飾器は有名な設計モデルで、断面的なニーズのあるシーンによく使われ、挿入ログ、パフォーマンステスト、トランザクションなどが古典的です.装飾器はこのような問題を解決する絶好の設計であり、装飾器があれば、多くの関数の中で関数機能自体に関係のない同じコードを抽出し、再利用を続けることができます.要約すると、装飾器の役割は、既存のオブジェクトに追加の機能を追加することです.
装飾器の定義は抽象的で、小さな例を見てみましょう.
def foo():
print（'in foo()'）
foo()これはつまらない関数で間違いありません.しかし、突然もっと退屈な人がいて、私たちは彼をB君と呼んで、私はこの関数を実行するのにどのくらいの時間がかかったかを見たいと言っています.いいでしょう.では、私たちはこのようにすることができます.
import time
def foo():
start = time.clock()
print('in foo()')
end = time.clock()
print('used:',end -start)
foo()いいですね.機能に手抜かりがないように見えます.しかし、卵が痛いB君は今突然この関数を見たくなくなり、foo 2というもう一つの関数にもっと興味を持っています.
どうしようかな?以上新しく追加されたコードをfoo 2にコピーすると、これはタブーです~コピーなんて大嫌いじゃないですか!そして、B君が他の関数を見続けたら?
1.2. 不変で変化に応じて、変化である.
覚えていますか、関数はPythonの中で1等公民で、それでは私达は1つの関数timeitを再定义することを考えることができて、fooの引用を彼に渡して、それからtimeitの中でfooを呼び出して时间を计って、このようにして、私达はfooの定义を変更しない目的を达成して、その上、B君がどれだけの関数を见て、私达はすべて関数の定义を修正する必要はありません!
import time
def foo():
print('in foo()')
def timeit(func):
start = time.clock()
func()
end =time.clock()
print('used:', end-start)
timeit(foo)論理的には問題ないように見えますが、すべてが美しく、正常に動作しています!......など、呼び出し部分のコードを変更したようです.もともと私たちはこのように呼び出した:foo()で、修正してから:timeit(foo)になりました.そうすると、fooがNで呼び出されたら、このNのコードを修正しなければなりません.あるいは極端には、どこかで呼び出されたコードがこの状況を修正できないことを考慮します.例えば、この関数は他の人に渡されて使用されています.
1.3. 変更を最小限に!
それなら、呼び出しのコードを変更しない方法を考えてみましょう.呼び出しコードを変更しない場合は、foo()を呼び出すにはtimeit(foo)を呼び出す効果が必要であることを意味します.私たちはtimeitをfooに割り当てることを考えることができますが、timeitにはパラメータがあるようです......パラメータを統一する方法を考えましょう!timeit(foo)が直接呼び出し効果を生じるのではなく、fooパラメータリストと一致する関数を返すと・・・やりやすいので、timeit(foo)の戻り値をfooに割り当て、foo()を呼び出すコードはまったく変更しなくてもいい!
import time
def foo():
print('in foo()')
# ， ，
def timeit(func):
# ，
def wrapper():
start = time.clock()
func()
end =time.clock()
print('used:', end-start)
#
return wrapper
foo = timeit(foo)
foo()これで、簡易タイマーができました!fooを定義してfooを呼び出す前にfoo=timeit(foo)を加えるだけで、計時の目的を達成することができます.これは装飾器の概念で、fooがtimeitに装飾されているように見えます.この例では、関数の入力と終了にはタイミングが必要であり、これを横断面(Aspect)と呼び、このプログラミング方式を切断面向けプログラミング(Aspect-OrientedProgramming)と呼ぶ.従来のプログラミング習慣の上から下への実行方式と比較すると,関数実行の流れに横方向に論理が挿入されているように見える.特定のビジネス分野では、コードの重複を大幅に減らすことができます.カットプログラミングに向けてかなりの用語がありますが、ここではあまり紹介しません.興味があれば関連資料を探してもいいです.この例はプレゼンテーションにのみ使用され、fooにパラメータがあり、戻り値がある場合は考慮されず、改善の重任はあなたに任せます:)
上のコードはもう簡略化できないように見えますが、Pythonは文字入力量を減らすために文法糖を提供しました.
import time
def timeit(func):
def wrapper():
start = time.clock()
func()
end =time.clock()
print('used:', end - start)
return wrapper
@timeit
def foo():
print('in foo()')
foo()11行目の@timeitに注目し、定義にこの行を加えると、foo=timeit(foo)と完全に等価であり、@に別の魔力があるとは思わないでください.文字入力が少なくなったほか、装飾品のように見えるという追加のメリットもあります.
1.4最後に、前述の質問に答えます.
# makebold
def makebold(fn):
#
def wrapper():
#
return "" + fn() + ""
return wrapper
# makeitalic
def makeitalic(fn):
#
def wrapper():
#
return "" + fn() + ""
return wrapper
#
@makebold
@makeitalic
def say():
return "hello"
print(say())
# : hello
#
def say():
return "hello"
say = makebold(makeitalic(say))
print(say())
# : hello2、装飾器の種類
2.1無パラメータ装飾器
def deco(func):
print(func)
return func
@deco
def foo():
pass
foo()最初の関数decoは装飾関数であり、そのパラメータは装飾された関数オブジェクトである.入力した関数オブジェクトをdeco関数内で「装飾」して返すことができます(必ず返すことを覚えておいてください.そうしないと、外でfooを呼び出す場所には関数がありません.実際にはfoo=deco(foo))
関数の説明ドキュメントがあるかどうかを確認するために、小さな例を書きました.
#-*- coding: UTF-8 -*-
def deco_functionNeedDoc(func):
if func.__doc__ == None :
print(func, "has no __doc__, it's a bad habit." )
else:
print(func, ':', func.__doc__, '.' )
return func
@deco_functionNeedDoc
def f():
print('f() Do something')
@deco_functionNeedDoc
def g():
'I have a __doc__'
print('g() Do something')
f()
g()2.2パラメータ付装飾器
def decomaker(arg):
' arg '
""" decorator
，
"""
def newDeco(func): # decorator
print(func, arg)
return func
return newDeco
@decomaker(deco_args)
def foo():pass
foo()最初の関数decomakerは装飾関数で、そのパラメータは「装飾を強化する」ために使用されます.この関数は装飾された関数オブジェクトではないため、内部に少なくとも装飾された関数を受け入れる関数を作成し、このオブジェクトに戻る必要があります(実際にはfoo=decomaker(arg)(foo))
これは本当に良い例が思いつかないが、やはり見識が少ないので、同期ロックの例を借りるしかない.
def synchronized(lock):
"""
！lock acquire release
"""
def sync_with_lock(func):
def new_func(*args, **kwargs):
lock.acquire()
try:
return func(*args, **kwargs)
finally:
lock.release()
new_func.func_name = func.func_name
new_func.__doc__ = func.__doc__
return new_func
return sync_with_lock
@synchronized(__locker)
def update(data):
""" """
tasks = self.get_tasks()
delete_task = None
for task in tasks:
if task[PLANTASK.ID] == data[PLANTASK.ID]:
tasks.insert(tasks.index(task), data)
tasks.remove(task)
delete_task = task
r, msg = self._refresh(tasks, delete_task)
return r, msg, data[PLANTASK.ID]呼び出し時はupdae(data)です.
複数の装飾品を組み合わせて使用することもできます.呼び出し順序に注意してください.
@synchronized(__locker)
@deco_functionNeedDoc
def f():
print('f() Do something')2.3内蔵の装飾器
内蔵の装飾器はstaticmethod,classmethod,propertyの3つあり,クラスで定義されたインスタンスメソッドを静的メソッド,クラスメソッド,クラスプロパティに変える役割を果たす.モジュールでは関数を定義できるので、オブジェクト向けに完全にプログラミングしない限り、静的メソッドとクラスメソッドの使用は多くありません.属性も欠かせないものではなく、Javaは属性がなくても潤いがあります.個人的なPythonの経験から、propertyを使ったことがなく、staticmethodやclassmethodを使う頻度も非常に低いです.
アクセサリーは以下の参考になります.http://www.cnblogs.com/huxi/archive/2011/03/01/1967600.html