とあるものを書いていて、
"各条件を満たす最初の要素"★以外★を抽出する
という要件が出てきた.
分解し、各動作の組み合わせで、すぐ解決できそうなものではある.
が、その過程でけっこう頭を悩ましてしまったので、解決方針の考えをまとめておく.
思ったより悩んだ要因として、以下の事がある.
- 条件は複数ある
- 最初の要素★以外★を抽出したい の以外の部分
これらの解決法としてどう表現するか?を試行錯誤したログのような記事だと思っていただきたい.
やはり例がないと何がしたいのかも分からないので、簡単な例を用意する.
前段階として考えていくに辺り、★以外★の部分もひとまず邪魔だ、
その部分をまず除き、単純化した要件で考えてみる.
"各条件を満たす最初の要素"を抽出する
こちらの動作で考えてみたい.この動作であれば至ってシンプルかと.
例題を用意する.
例題: リスト：[6,1,5,3,8,10,11]から、 5より小さい要素・８より大きい要素の、それぞれ条件を満たす最初の要素を取り出せ
つまり期待する動作としては、以下の動作だ.
f [6,1,5,3,8,10,11] -> [1,10] (3,11は対象にならない)
まずすぐに思いつく方法として、以下のfilterなどでもよくあるやり方がある.
- 条件を満たす最初の要素をリストから抽出する関数、find()関数を用意する
- 各条件のリスト（[p1,p2,...]）を用意する
- 探索対象のリスト（L）を引数としたfind関数へ、各条件を順次適用する
そしてこれは内包表記で簡単に現せる.
[ find(p,L) for p in [p1,p2..] ]
# アルゴリズムを簡易的に現そうとすると、haskellっぽく書きたくなってくる.
思考をそのまま現せれる言語という事をすごく感じる..
これで、「それぞれ条件を満たす最初の要素」のリストは得られる.
次は当初の目的の「それぞれ条件を満たす最初の要素」★以外★、
この以外の部分をどうするか、だ.
[ not find(p,L) for p in [p1,p2..] ]
などとして反転させられない点が悩みどころだ.
そこで直接的なやり方、以下のように差分を抽出することで、
目的の★以外★の部分を表現する.
[全て] - [それぞれ条件を満たす最初の要素] --> [それぞれ条件を満たす最初の要素★以外★]
pythonの場合は、set型による集合演算を用いる必要がある（リストでは集合演算ができない ）
今までの事をまとめ、★以外★のデータを得る、以下のコードを書く.
''' リスト：[6,1,5,3,8,10,11]から、 5より小さい要素・８より大きい要素の、それぞれ条件を満たす最初の要素★以外★を取り出す ''' allLis = [6,1,5,3,8,10,11] predicates = [(lambda x: x < 5),(lambda x: x > 8)] firstMatchs = [ find2(p,allList) for p in predicates ] targets = set(allList) - set(firstmatchs) >>> targets targets [6, 5, 3, 8, 11] ''' '''
上記までで、目的の動作を記述する方法が得られた.
ここで悩むポイントがある.リストの走査回数についてだ.
悩みポイント：
- 同じリストに対して何度も走査、判定処理をすることになる
- 差分抽出処理でもリストを比較し、また走査することになる
無駄な走査が何度も走ってしまっているように思える.
この無駄をなくし、以下のようにできるようしたい.
・一度の走査で、[それぞれ条件を満たす最初の要素★以外★]を抽出
1.の問題については、処理の順番を考える事で、対応できる.
具体的には以下のように処理の順番を変える.
_リストに対して、条件の判定処理をする_ それを繰り返す
ではなく、
_リストの要素ひとつづつに対して、各条件の判定処理をする_ それを繰り返す
というように変える.
この部分の、判定処理についてまだ分かりにくい. これは要は、
「条件を満たす最初の要素であるか否か」を判定する処理
というものをイメージしている.
2.の問題については、その場でfilter的な処理を施せばOKだ.
これら２点の解決方法を反映し、期待する動作を噛み砕いて言うと、
一度の走査で、「条件を満たす最初の要素であるか否か」を判定していき、 真である要素をマークしていく
という処理ができれば良いということになる.
★以外★は、ここで真にならない要素ということになる.
これは not で表現できる.
そしてできた関数が以下だ. （... 端折ってしまってすみません）
最初の要素であるかどうかを判定するための記憶装置として、
メモ化っぽいことをやっている.
def find_each(predicates,L):
"""
porpose : 各条件について、それを満たす最初の要素を、一度の走査で抽出する
contract: find_each :: [(a -> Bool)] -> [a] --> [a]
example : find_each([(lambda x: x<5),(lambda x: x>8)],[6,1,5,3,8,10,11]) --> [1,10]
"""
memo_table = {}
def find_each_aux(predicates,x):
"""
porpose : find_eachで与えられたリスト内で、条件を満たす最初の要素かどうか判定する.最初の要素であればTrue.それ以降はFalse.
contract: find_each_aux :: (a -> Bool) -> a --> Bool
example : find_each_aux(lambda x: x<5, 1) --> True
find_each_aux(lambda x: x<5, 3) --> False
"""
if predicates == []: return False
key = predicates[0] # 各条件をkeyとする
# その条件keyがtableになければ、満たす要素かどうか試行. 既にあれば次の条件へ.
if not key in memo_table:
if predicates[0](x): # 条件を満たせば、満たした最初の要素として記憶し、Trueを返す.
memo_table[key] = x
return True
else:
return find_each_aux(predicates[1:],x)
else:
return find_each_aux(predicates[1:],x)
# 最初の要素★以外★をfilterしたものを返す
return filter(lambda x: not find_each_aux(predicates,x),L)
test_find_each = find_each([(lambda x: x<5),(lambda x: x>8)],[6,1,5,3,8,10,11])
>>> test_find_each
test_find_each
[6, 5, 3, 8, 11]
'''
'''
ポイント：
- ひとつの要素に対して、各条件の判定処理を一連で行う.
- 各条件を満たす最初の要素かどうか判定するために、条件をkey,満たす要素をvalueとした辞書に、結果を登録していっている.
- 辞書の登録済み有無と、条件一致の判定を元に、辞書を参照・真偽を返す.
と走査回数の観点から,コードを書いたはいいが、本当に効率的な処理になっているかが
しっかりテストできていない. というかむしろ非効率になっているのではないか...と思う.
必要ない複雑さを持ち出してきてしまっているような気がする.
やはりアルゴリズムを体系的に勉強したいと感じた.
0 comment:
Post a Comment