二分探索のための遅延評価リストを作った

docs.python.org

標準ライブラリに二分探索が用意されているが，sortと違ってkeyが指定できない．

毎回二分探索を書いても良いが，境界条件などで足を救われがち． よって，クラス継承の練習を兼ねてgetitemしたときだけfuncで遅延評価されるリストを作った．

ほぼlistを継承してgetitem()だけ変更しているのでそのままbisect_lightなどに渡せる．あまりそのようなことはないが元のリストはsortされている必要はなく，funcの結果として単調増加になっていればok．

class lazy_eval_list(list):
    # when used with bisect method, func must be monotonically increasing function.
    # not compatible with insort method.
    def __init__(self, func, a, memorize=True):
        super().__init__(a)
        self._func = func
        self._eval = {}
        
    def __getitem__(self, key):
        if type(key) is int:
            return self.__evaluate__(super().__getitem__(key))
        elif type(key) is slice:
            return [self.__evaluate__(item) for item in super().__getitem__(key)]
        
    def __evaluate__(self, item):
        if item not in self._eval:
            self._eval[item] = self._func(item)
        return self._eval[item] 
    
    def __repr__(self):
        return 'lazy_eval_list({}, {})'.format(self._func, super().__repr__())

上記は，一度計算した結果を保持していたり，スライスでの入力に対応したりしているが，より簡単には以下．

競プロで使うならこちらが良いかも．

class lazy_eval_list(list):
    def __init__(self, func, a):
        super().__init__(a)
        self._func = func
        
    def __getitem__(self, key):
        return self._func(super().__getitem__(key))

いずれにせよ，

ll = lazy_eval_list(lambda x:x**2, [10,20,30])

import bisect
bisect.bisect_left(ll, 400)
>>> 1

と，インデックスを得ることができる．

なお，insert, appendやextendは問題ないが，いくつかの場面でリスト自体を返すので，ll = ll + [100]や ll+=[100]，ll=ll*3などはただのリストになってしまう．

bisect.insort_left(a, x) も，内部でxが直接aと比較されてしまうので意図した動きにならない．

GitHub - tmitanitky/lazy_eval_list: lazy evaluation list for bisect