[python]「各条件を満たす最初の要素」★以外★を抽出する方法

とあるものを書いていて、

"各条件を満たす最初の要素"★以外★を抽出する

という要件が出てきた.

分解し、各動作の組み合わせで、すぐ解決できそうなものではある.
が、その過程でけっこう頭を悩ましてしまったので、解決方針の考えをまとめておく.
思ったより悩んだ要因として、以下の事がある.

• 条件は複数ある
• 最初の要素★以外★を抽出したい　の以外の部分

これらの解決法としてどう表現するか?を試行錯誤したログのような記事だと思っていただきたい.

やはり例がないと何がしたいのかも分からないので、簡単な例を用意する.
前段階として考えていくに辺り、★以外★の部分もひとまず邪魔だ、
その部分をまず除き、単純化した要件で考えてみる.

"各条件を満たす最初の要素"を抽出する

こちらの動作で考えてみたい.この動作であれば至ってシンプルかと.
例題を用意する.

例題:
リスト：[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型による集合演算を用いる必要がある（リストでは集合演算ができない ）
今までの事をまとめ、★以外★のデータを得る、以下のコードを書く.

view plainprint?

1. ''''' 
2. リスト：[6,1,5,3,8,10,11]から、 
3. 5より小さい要素・８より大きい要素の、それぞれ条件を満たす最初の要素★以外★を取り出す 
4. '''  
5.   
6. allLis      = [6,1,5,3,8,10,11]  
7. predicates  = [(lambda x: x < 5),(lambda x: x > 8)]  
8. firstMatchs = [ find2(p,allList) for p in predicates ]  
9. targets     = set(allList) - set(firstmatchs)  
10.   
11. >>> targets  
12. targets  
13. [6, 5, 3, 8, 11]  
14. ''''' 
15. '''  

'''
リスト：[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. 差分抽出処理でもリストを比較し、また走査することになる

無駄な走査が何度も走ってしまっているように思える.
この無駄をなくし、以下のようにできるようしたい.

・一度の走査で、[それぞれ条件を満たす最初の要素★以外★]を抽出

1.の問題については、処理の順番を考える事で、対応できる.
具体的には以下のように処理の順番を変える.

_リストに対して、条件の判定処理をする_ それを繰り返す

ではなく、

_リストの要素ひとつづつに対して、各条件の判定処理をする_ それを繰り返す

というように変える.

この部分の、判定処理についてまだ分かりにくい. これは要は、
「条件を満たす最初の要素であるか否か」を判定する処理
というものをイメージしている.

2.の問題については、その場でfilter的な処理を施せばOKだ.

これら２点の解決方法を反映し、期待する動作を噛み砕いて言うと、

一度の走査で、「条件を満たす最初の要素であるか否か」を判定していき、
真である要素をマークしていく

という処理ができれば良いということになる.

★以外★は、ここで真にならない要素ということになる.
これは not で表現できる.
そしてできた関数が以下だ. （... 端折ってしまってすみません）
最初の要素であるかどうかを判定するための記憶装置として、
メモ化っぽいことをやっている.

view plainprint?

1. def find_each(predicates,L):  
2.     """ 
3.     porpose : 各条件について、それを満たす最初の要素を、一度の走査で抽出する 
4.     contract: find_each :: [(a -> Bool)] -> [a] --> [a] 
5.     example : find_each([(lambda x: x<5),(lambda x: x>8)],[6,1,5,3,8,10,11]) --> [1,10] 
6.     """  
7.     memo_table = {}  
8.   
9.     def find_each_aux(predicates,x):  
10.         """ 
11.         porpose : find_eachで与えられたリスト内で、条件を満たす最初の要素かどうか判定する.最初の要素であればTrue.それ以降はFalse. 
12.         contract: find_each_aux :: (a -> Bool) -> a --> Bool 
13.         example : find_each_aux(lambda x: x<5, 1) --> True 
14.                   find_each_aux(lambda x: x<5, 3) --> False 
15.         """  
16.         if predicates == []: return False   
17.         key = predicates[0]               # 各条件をkeyとする  
18.         # その条件keyがtableになければ、満たす要素かどうか試行. 既にあれば次の条件へ.  
19.         if not key in memo_table:         
20.             if predicates[0](x):  # 条件を満たせば、満たした最初の要素として記憶し、Trueを返す.  
21.                 memo_table[key] = x  
22.                 return True  
23.             else:  
24.                 return find_each_aux(predicates[1:],x)  
25.         else:  
26.             return find_each_aux(predicates[1:],x)  
27.   
28.     # 最初の要素★以外★をfilterしたものを返す  
29.     return filter(lambda x: not find_each_aux(predicates,x),L)  
30.       
31. test_find_each = find_each([(lambda x: x<5),(lambda x: x>8)],[6,1,5,3,8,10,11])   
32.   
33. >>> test_find_each  
34. test_find_each  
35. [6, 5, 3, 8, 11]  
36.   
37. ''''' 
38. '''  

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とした辞書に、結果を登録していっている.
• 辞書の登録済み有無と、条件一致の判定を元に、辞書を参照・真偽を返す.

と走査回数の観点から,コードを書いたはいいが、本当に効率的な処理になっているかが
しっかりテストできていない. というかむしろ非効率になっているのではないか...と思う.

必要ない複雑さを持ち出してきてしまっているような気がする.
やはりアルゴリズムを体系的に勉強したいと感じた.