規則性の低い数列表に対する無検索逆引き

比較を繰り返す検索処理を避けたい

数に規則性のない数列（テーブル）からインデックスを得るとき、高級言語（死語？）では検索機能(table.index(N)など)がありますが、できれば検索なしでインデックスを得たいときがあります。（ここでの「検索」は比較を繰り返す処理とします）

テーブル中の数値が重複して出てこないとき、剰余（と逆引き表）を使うと検索なしにインデックスを得られる場合があります。

例(除数は45)

>>> table = [57183, 26302, 12855, 61489, 21256, 14532, 24168, 37683, 18386, 35798, 7211]
>>> [n % 45 for n in table]
[33, 22, 30, 19, 16, 42, 3, 18, 26, 23, 11]
>>> rtab = [
...       -1, -1, -1,  6, -1, -1, -1, -1, -1, -1,
...       -1, 10, -1, -1, -1, -1,  4, -1,  7,  3,
...       -1, -1,  1,  9, -1, -1,  8, -1, -1, -1,
...       +2, -1, -1,  0, -1, -1, -1, -1, -1, -1,
...       -1, -1,  5, -1, -1, -1
...       ]
>>> [rtab[n % 45] for n in table]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

例では、table の値を除数 45 で剰余したリストも中の数が重複していません（単射）。

目的の数列の剰余が単射になれば、逆引き表を作って検索不要にできます。

この方法の利点と欠点は以下のとおりです。

利点

• 高速化が期待できる
  • 比較を繰り返す検索ではなくなるため
    • 例: dict より速い読み取り専用辞書
• 単純な逆引き表より小さな逆引き表を期待できる
  • rtab[N] より rtab[N % d] の rtab は小さいかも

欠点

• テーブル中の数値は重複してはいけない (set に変換しても同じサイズ)
• 逆引き表の前準備が必要
  • 逆引き表はテーブル（正引き）より大きい
• 単純逆引きに比べると剰余逆引きは遅い
  • rtab[N] より rtab[N % d] は剰余の分だけ遅い

その他

• 逆引き表は辞書(dictなど)相当なので、インデックス以外に置換えも可

除数の求め方

求めたい除数は「逆引き表の大きさ」でもあるので

　　初期値： テーブルの大きさ (len(table))
　　増加値： 1

として、テーブルの剰余が単射になるまで除数を増やして検索します。

除数の最大値は、テーブル内の最大値 (max(table)) になるので、単純逆引き表を用いた方が良いです。

除数の検索と逆引き表の生成プログラム

コマンドライン引数に数列を渡すと、除数の検索と逆引き表の生成を行います。

オプションで以下のことができます。

　　逆引きでの無効を示す値の変更 (-d N)
　　除数の上限を設定 (-l N)

findivisor.py

#!/usr/bin/env python3

def create_remainder_table(table, divisor_max=None, invalid_value=None):
    "除数検索と逆引き表の生成"

    tlen = len(table)
    if not tlen:
        return (0, tuple())

    if type(table) in (tuple, list, set):
        ltab = tuple(table)
        table = {ltab[i]: i for i in range(tlen)}
        tlen = len(table)

    divisor = tlen
    if divisor_max is None:
        divisor_max = max(table)
    keys = tuple(table.keys())
    while True:
        rtab = {(n % divisor) for n in keys}
        injective = (len(rtab) == tlen)
        if injective or divisor >= divisor_max:
            break
        divisor += 1
    if not injective:
        return (0, tuple())

    vals = tuple(table.values())
    rtab = [(tlen if invalid_value is None else invalid_value)] * divisor
    for i in range(tlen):
        rtab[keys[i] % divisor] = vals[i]

    return (divisor, rtab)


# コマンドライン処理
if __name__ == '__main__':
    import re
    import sys
    import random
    import argparse

    def format_list(data, *, width=16, prefix='',
                    datafmt='%s', msgfmt='%#s', separator=',', space=1, suffix='\n'):
        fmtdata = [datafmt % d for d in data]
        msgfmt = msgfmt.replace('#', ('%d' % max([len(s) for s in fmtdata])))
        msglist = [(msgfmt % d) + separator for d in fmtdata]
        return (suffix.join([prefix + (' ' * space).join(msglist[i:min(i+width, len(msglist))])
                             for i in range(0, len(msglist), width)]) + suffix)

    parser = argparse.ArgumentParser(description='剰余による数列の逆引き表生成支援道具')
    parser.add_argument('N', nargs='+', help='数列の数 (-1 を一つだけ指定すると乱数によるテスト)')
    parser.add_argument('-d', '--defval', metavar='N', help='表の穴埋め値を指定します (既定:表の大きさ)')
    parser.add_argument('-l', '--limit', metavar='N', help='除数の上限を指定します (既定:表の最大値)')
    args = parser.parse_args()

    if len(args.N) == 1 and args.N[0] == '-1':
        table = {random.randint(0, 65535) for n in range(random.randint(10, 50))}
    else:
        RE_NUM = re.compile('(0b(?P<n2>[01]+)|0o(?P<n8>[0-7]+)|(?P<n10>[0-9]+)|0x(?P<n16>[0-9A-Fa-f]+)).*')
        table = []
        for arg in args.N:
            for s in arg.split(','):
                m = RE_NUM.match(s.strip())
                if not m:
                    continue
                for kv in filter(lambda kv: kv[1], m.groupdict().items()):
                    table.append(int(kv[1], int(kv[0][1:])))

        stab = set(table)
        if len(stab) != len(table):
            print('重複があります:', ','.join([
                '%d' % d for d in set(filter(lambda n: table.count(n) != 1, table))
            ]))
            sys.exit(2)

    divisor_max = None if args.limit is None else int(args.limit)
    invalid_value = len(table) if args.defval is None else int(args.defval)

    (divisor, index) = create_remainder_table(table, divisor_max, invalid_value)
    if divisor <= 0:
        print('除数を見つけられませんでした')
        sys.exit(2)
    nrem = tuple(n % divisor for n in table)
    srem = tuple('%d:%d' % (n, n % divisor) for n in table)

    print('除数:', divisor)
    print('逆引き:\n' + format_list(index, width=8, prefix=' '*4)[:-2])
    print(('元の表: %d 個\n' % len(table)) + format_list(table, width=8, prefix=' '*4)[:-2])
    print('剰余:\n' + format_list(nrem, width=8, prefix=' '*4)[:-2])
    print('被除数：剰余:\n' + format_list(srem, width=8, prefix=' '*4)[:-2])

実行結果(逆引きの8は無効を示す)

$ python3 findivisor.py  2, 3, 5, 7, 11, 13, 17, 19
除数: 13
逆引き:
    5, 8, 0, 1, 6, 2, 7, 3,
    8, 8, 8, 4, 8
元の表: 8 個
     2,  3,  5,  7, 11, 13, 17, 19
剰余:
     2,  3,  5,  7, 11,  0,  4,  6
被除数：剰余:
      2:2,   3:3,   5:5,   7:7, 11:11,  13:0,  17:4,  19:6

実行結果(逆引きの9は無効を示す)

$ python3 findivisor.py  461, 353, 419, 523, 139, 13, 31, 53, 89
除数: 37
逆引き:
    9, 9, 9, 9, 9, 3, 9, 9,
    9, 9, 9, 9, 2, 5, 9, 8,
    7, 0, 9, 9, 1, 9, 9, 9,
    9, 9, 9, 9, 4, 9, 9, 6,
    9, 9, 9, 9, 9
元の表: 9 個
    461, 353, 419, 523, 139,  13,  31,  53,
     89
剰余:
    17, 20, 12,  5, 28, 13, 31, 16,
    15
被除数：剰余:
    461:17, 353:20, 419:12,  523:5, 139:28,  13:13,  31:31,  53:16,
     89:15

テスト：数列として {-1} を与えると表は乱数生成になります。

実行結果(逆引きの-1は無効を示す)

$ python3 findivisor.py -1 -d -1
除数: 63
逆引き:
    -1, -1, -1, -1, -1, -1,  5, -1,
    -1, -1, -1, -1, -1, -1, -1, -1,
     4, -1, -1, -1, 11, -1, -1, 13,
    -1, -1, -1, -1,  2, -1,  9,  3,
    15, 12,  1, 14, -1, -1,  7,  6,
    -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, 10,  8, -1, -1, -1,
    -1, -1, -1, -1, -1,  0, -1
元の表: 16 個
    23434, 31597, 33733, 60700, 40651,  8574, 25176, 33176,
    22795, 47532, 31992, 55586,  1167, 54770, 32165, 56795
剰余:
    61, 34, 28, 31, 16,  6, 39, 38,
    52, 30, 51, 20, 33, 23, 35, 32
被除数：剰余:
    23434:61, 31597:34, 33733:28, 60700:31, 40651:16,   8574:6, 25176:39, 33176:38,
    22795:52, 47532:30, 31992:51, 55586:20,  1167:33, 54770:23, 32165:35, 56795:32

HTML+JavaScript による生成

以下、スクリーン ショット

---

HTML

<!DOCTYPE html>
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" >
    <title>除数検索と逆引き表生成</title>
    <style>
      table {
          border: solid 1px gray;
          border-collaspe: collaspe;
          border-spacing: 0;
      }
      th, td {
          border: solid 1px gray;
          padding: 6px;
      }
      th {
          background-color: #efefef;
      }
    </style>
  </head>
  <body>
    <h1>除数検索と逆引き表生成</h1>
    <p>
      <textarea id="inp_table" rows="8" cols="80" placeholder="数列を入力"></textarea><br />
      配列の穴埋め値：<input id="inp_defval" type="text" size="8" placeholder="自動">
      <input type="button" value="更新" onclick="onUpdate();">
    </p>
    <p>入力配列の幅：
      <input id="inp_wtab" type="number" size="5" placeholder="10" style="width: 3em;">
      <input type="button" value="更新" onclick="onUpdate();">
    </p>
    <p>逆引配列の幅：
      <input id="inp_wrem" type="number" size="5" placeholder="10" style="width: 3em;">
      <input type="button" value="更新" onclick="onUpdate();">
    </p>
    <p>処理結果 => <span id="status">なし</span></p>
    <table id="result"></table>

    <h3>入力と剰余の対応</h3>
    <table id="out_table1">
      <tr><th>配列</th><th>&nbsp;</th></tr>
      <tr><th>入力</th><td>&nbsp;</td></tr>
      <tr><th>剰余</th><td>&nbsp;</td></tr>
    </table>
    <h3>逆引きと入力の対応</h3>
    <table id="out_table2">
      <tr><th>配列</th><th>&nbsp;</th></tr>
      <tr><th>逆引</th><td>&nbsp;</td></tr>
      <tr><th>入力</th><td>&nbsp;</td></tr>
    </table>

    <p></p>
    <details>
      <summary>デバッグ用</summary>
      <div>
        <p>入力文字の分解：<span id="dbg_nums"></span></p>
        <p>上記の数値化：<span id="dbg_table"></span></p>
        <p>穴埋め値：<span id="dbg_defval"></span></p>
        <p>除数：<span id="dbg_divisor"></span></p>
        <p>逆引き：<span id="dbg_index"></span></p>
      </div>
    </details>

    <script type="text/javascript">
    <!--

      function setStatus(msg) {
          document.getElementById('status').innerText = msg;
      }

      function clearChildren(tag) {
          while (tag.firstChild)
              tag.removeChild(tag.firstChild);
      }

      function setStyle(tag, style) {
          if (style) for (const s of style)
              tag.style.setProperty(s[0], s[1]);
          return tag;
      }

      function setTextRight(tag) {
          return setStyle(tag, [['text-align', 'right']]);
      }

      function trAppendChild(tr, tag, msg, style) {
          const tx = document.createElement(tag);
          tx.innerText = msg;
          tr.appendChild(tx);
          return setStyle(tx, style);
      }
      function trAppendTH(tr, msg, style) { return trAppendChild(tr, 'th', msg, style); }
      function trAppendTHRight(tr, msg, style) { return setTextRight(trAppendChild(tr, 'th', msg, style)); }
      function trAppendTD(tr, msg, style) { return trAppendChild(tr, 'td', msg, style); }
      function trAppendTDRight(tr, msg, style) { return setTextRight(trAppendChild(tr, 'td', msg, style)); }

      function getInputNumber(id, defval, limit) {
          const tag = document.getElementById(id);
          let val = Number(tag.value);
          if (val < 1 || !Number.isInteger(val))
              val = defval;
          return Math.max(Math.min(val, limit), 1);
      }

      function onUpdate() {
          setStatus('処理中');

          const inptable = document.getElementById('inp_table');
          const inpdefval = document.getElementById('inp_defval');
          const nums = [...inptable.value.matchAll(/[ox_0-9A-Fa-f]+/g)];
          const table = nums.map(s => Number(s));

          if (table.length == 0) {
              setStatus('エラー：数列を入力してください');
              return;
          }

          document.getElementById('dbg_nums').innerText = nums;
          document.getElementById('dbg_table').innerText = table;

          const tabchk = new Set(table);
          if (tabchk.has(NaN)) {
              setStatus('エラー：数列に扱えない数値があります');
              return;
          }
          if (tabchk.size != table.length) {
              setStatus('エラー：重複があります');
              return;
          }

          // 除数の検索と逆引き表の生成

          const divisor_max = Math.max.apply(null, table);
          let divisor = table.length;
          // if (divisor > divisor_max) divisor = divisor_max;
          let remains = table;
          for (; divisor <= divisor_max; divisor++) {
              remains = table.map(n => n % divisor);
              if (new Set(remains).size == table.length) break;
          }

          const sindex = [...Array(divisor)].map(() => undefined);
          for (let i = 0; i < sindex.length; i++) sindex[remains[i]] = i;

          const ndefval = Number(inpdefval.value != '' ? inpdefval.value : '--');
          const defval = (Number.isInteger(ndefval) ? ndefval : table.length);
          const index = sindex.map(n => (n != undefined) ? n : defval);

          // 結果出力

          document.getElementById('dbg_defval').innerText = defval;
          document.getElementById('dbg_divisor').innerText = divisor;
          document.getElementById('dbg_index').innerText = index;

          {
              const otag = document.getElementById('result');
              clearChildren(otag);
              {
                  const tr = document.createElement('tr');
                  trAppendTH(tr, '定数');
                  trAppendTD(tr, '除数 = ' + divisor + ',  穴埋め値 = ' + defval);
                  otag.appendChild(tr);
              }
              {
                  const tr = document.createElement('tr');
                  trAppendTH(tr, '逆引表');
                  trAppendTD(tr, ('' + index).replaceAll(',', ', '));
                  otag.appendChild(tr);
              }
              {
                  const tr = document.createElement('tr');
                  trAppendTH(tr, '正引表');
                  trAppendTD(tr, ('' + table).replaceAll(',', ', '));
                  otag.appendChild(tr);
              }
          }
          {
              const otag = document.getElementById('out_table1');
              clearChildren(otag);

              const width = getInputNumber('inp_wtab', 10, table.length);
              for (let iy = 0; iy < table.length; iy += width) {
                  const tr_idx = document.createElement('tr');
                  const tr_fwd = document.createElement('tr');
                  const tr_rem = document.createElement('tr');
                  const style = [['background-color', '#f7ffff']];

                  trAppendTH(tr_idx, '配列');
                  trAppendTH(tr_fwd, '入力');
                  trAppendTH(tr_rem, '剰余');
                  for (let ix = 0; ix < width; ix++) {
                      const i = ix + iy;
                      if ((ix + iy) < table.length) {
                          trAppendTHRight(tr_idx, ix + iy);
                          trAppendTDRight(tr_fwd, table[ix + iy], style);
                          trAppendTDRight(tr_rem, table[ix + iy] % divisor, style);
                      } else {
                          trAppendTH(tr_idx, '');
                          trAppendTD(tr_fwd, '');
                          trAppendTD(tr_rem, '');
                      }
                  }
                  otag.appendChild(tr_idx);
                  otag.appendChild(tr_fwd);
                  otag.appendChild(tr_rem);
              }
          }
          {
              const otag = document.getElementById('out_table2');
              clearChildren(otag);

              const width = getInputNumber('inp_wrem', 10, index.length);
              for (let iy = 0; iy < index.length; iy += width) {
                  const tr_idx = document.createElement('tr');
                  const tr_rev = document.createElement('tr');
                  const tr_fwd = document.createElement('tr');

                  trAppendTH(tr_idx, '配列');
                  trAppendTH(tr_rev, '逆引');
                  trAppendTH(tr_fwd, '入力');
                  for (let ix = 0; ix < width; ix++) {
                      const i = ix + iy;
                      if (i < index.length) {
                          const j = index[i];
                          const valid = (0 <= j && j < table.length);
                          let rev = j;
                          let fwd = '';
                          if (valid)
                              fwd = table[j];
                          else
                              rev = '(' + j + ')';
                          const style = [['background-color', valid ? '#f7ffff' : '#fff7f7']];
                          trAppendTHRight(tr_idx, i);
                          trAppendTDRight(tr_rev, rev, style);
                          trAppendTDRight(tr_fwd, fwd, style);
                      } else {
                          trAppendTH(tr_idx, '');
                          trAppendTD(tr_rev, '');
                          trAppendTD(tr_fwd, '');
                      }
                  }
                  otag.appendChild(tr_idx);
                  otag.appendChild(tr_rev);
                  otag.appendChild(tr_fwd);
              }
          }

          setStatus('完了');
      }

      // !-->
    </script>
  </body>
</html>