キーを int 型とする辞書(dict)の派生クラスを剰余と逆引き表で作る

記事「規則性の低い数列表に対する無検索逆引き」の方法を使います。

辞書のキーが int 型であれば、剰余による単射が期待できます。そこで dict の派生クラスを作ってみました。

辞書(dict)の派生クラス remdict

表面的な dict との違いは

• divisor() 剰余の除数を返す
• modkeys(value=None) 剰余とキーの対応表を返す
  • キーがないところは value
• mkvalues(value=None) 剰余と値の対応を返す
  • キーがないところは value
• remainder_index(value=None) 剰余とデータ順の対応を返す
  • キーがないところは value
• forindex(iterable) 配列の逆引き用として remdict を作る
• suspended() 剰余逆引処理の中断状態を返す
• suspend() で剰余逆引処理を中止（dict と同じ動作になる）
• resume() で剰余逆引処理を再開

になります。各コードは短いので詳細はコードを読んでください。

このクラスは dict より効率は良くありません。C 言語でモジュールにするとマシになるかもしれませんが…
下記のC 言語モジュールにしたものはこちら。マシになったけど dict の方が速い…

remdict.py

class remdict(dict):
    def __init__(self, *args):
        super().__init__(*args)
        self._remdict_suspend = False
        self._remdict_modified = False
        self._remdict_divisor = None
        self._remdict_keys = None
        self._remdict_values = None
        self._remdict_remainder = None
        self._remdict_update()

    # override

    def __contains__(self, key):
        avail, has, rem = self._remdict_contains(key)
        return has if avail else dict.__contains__(self.key)

    def __getitem__(self, key):
        avail, has, rem = self._remdict_contains(key)
        if has:
            return self._remdict_keys[rem]
        return dict.__getitem__(self, key)

    def __setitem__(self, key, val):
        self._remdict_modified = True
        return dict.__setitem__(self, key, val)

    def __delitem__(self, key):
        self._remdict_modified = True
        return dict.__delitem__(self, key)

    def __or__(self, other):
        return remdict(dict.__or__(self, other))

    def __ior__(self, other):
        self._remdict_modified = True
        return dict.__ior__(self, other)

    def clear(self):
        self._remdict_modified = True
        return dict.clear(self)

    def get(self, key, defval=None):
        avail, has, rem = self._remdict_contains(key)
        if avail:
            return defval if not has else self._remdict_keys[rem]
        return dict.get(self, key, defval)

    def pop(self, key, value=None):
        self._remdict_modified = True
        return dict.pop(self, key, value)

    def popitem(self):
        self._remdict_modified = True
        return dict.popitem(self)

    def setdefault(self, key, value=None):
        avail, has, rem = self._remdict_contains(key)
        if has:
            return self._remdict_keys[rem]
        return dict.setdefault(sefl, key, value)

    def update(self, *other):
        self._remdict_modified = True
        return dict.update(self, *other)

    def copy(self):
        return remdict(dict.copy(self))

    @classmethod
    def fromkeys(self, keys, value=None):
        return remdict(dict.fromkeys(keys, value))

    # remdict

    def _remdict_check(self):
        if self._remdict_modified:
            self._remdict_update()

    def _remdict_contains(self, key):
        if type(key) is not int:
            return (False, False, 0)
        if self._remdict_suspend:
            return (False, False, 0)
        if self._remdict_modified:
            self._remdict_update()
        if not self._remdict_divisor:
            return (False, False, 0)
        rem = key % self._remdict_divisor
        return (True, key == self._remdict_keys[rem], rem)

    def _remdict_update(self):
        self._remdict_modified = False
        self._remdict_divisor = None
        self._remdict_keys = None
        self._remdict_values = None
        self._remdict_remainder = None

        keys = tuple(self.keys())
        tablen = len(keys)
        if tablen == 0 or sum([int(type(k) is int) for k in keys]) != tablen:
            return
        vals = tuple(dict.get(self, k) for k in keys)

        divisor = tablen
        divisor_max = max(keys)
        while True:
            if (len({(n % divisor) for n in keys}) == tablen):
                break
            if divisor >= divisor_max:
                return
            divisor += 1

        rkeys = [None] * divisor
        rvals = [None] * divisor
        ridx = [None] * divisor
        for i in range(tablen):
            rem = keys[i] % divisor
            ridx[rem] = i
            rkeys[rem] = keys[i]
            rvals[rem] = vals[i]

        self._remdict_divisor = divisor
        self._remdict_keys = tuple(rkeys)
        self._remdict_values = tuple(rvals)
        self._remdict_remainder = tuple(ridx)

    def divisor(self):
        self._remdict_check()
        return self._remdict_divisor

    def modkeys(self, invalid=None):
        self._remdict_check()
        return tuple((d if d != None else invalid) for d in self._remdict_keys)

    def mkvalues(self, invalid=None):
        self._remdict_check()
        return tuple((d if d != None else invalid) for d in self._remdict_values)

    def remainder_index(self, invalid=None):
        self._remdict_check()
        return tuple((d if d != None else invalid) for d in self._remdict_remainder)

    def suspended(self):
        return self._remdict_suspend

    def suspend(self):
        self._remdict_suspend = True

    def resume(self):
        self._remdict_suspend = False

    @classmethod
    def forindex(self, iterable):
        keys = tuple(iterable)
        return remdict({keys[i]: i for i in range(len(keys))})

テスト(1)

>>> m = remdict({2: 'A', 3:'B', 5:'C', 7:'D', 11:'E', 13:'F'})
>>> m.divisor()
7
>>> m.modkeys()
(7, None, 2, 3, 11, 5, 13)
>>> m.modkeys(-1)
(7, -1, 2, 3, 11, 5, 13)
>>> m.mkvalues()
('D', None, 'A', 'B', 'E', 'C', 'F')
>>> m.mkvalues(-1)
('D', -1, 'A', 'B', 'E', 'C', 'F')
>>> m.remainder_index()
(3, None, 0, 1, 4, 2, 5)
>>> m.remainder_index(-1)
(3, -1, 0, 1, 4, 2, 5)

テスト(2)

>>> m = remdict.forindex((2,3,5,7,11,13))
>>> m.divisor()
7
>>> m.modkeys(-1)
(7, -1, 2, 3, 11, 5, 13)
>>> m.mkvalues(-1)
(3, -1, 0, 1, 4, 2, 5)
>>> m.remainder_index(-1)
(3, -1, 0, 1, 4, 2, 5)