はてだBlog(仮称)

私的なブログど真ん中のつもりでしたが、気づけばWebサイト系のアプリケーション開発周りで感じたこと寄りの自分メモなどをつれづれ述べています。2020年6月現在、Elasticsearch、pandas、CMSなどに関する話題が多めです。...ですが、だんだんとより私的なプログラムのスニペット置き場になりつつあります。ブログで述べている内容は所属組織で販売している製品などに関するものではなく、また所属する組織の見解を代表するものではありません。

出身大学か出身県が同じ学生のグループ化ってどうやるんだっけの考察メモ(ひとまずPython)

はじめに

グループ化の演算の要件で、出身大学と出身県が同じ学生どうしをグループ化というのは良くある話だと思います。

しかし、

同じようなグループ化の例でも、出身大学か出身県が同じ学生のグループ化となると一気にハードルが上がりそうな気がします。

競プロ等に親しんでいる方らからすると初歩レベルの問題かもしれませんが、いややっぱり結構面白いのではと思い、うんうんうなって考察した結果、面白いかはともかく それほど難しくもない方式で実現できて、逆に落とし穴がないかさらしてみたくなったので、その結果のスニペットを貼り付けてみた...という投稿です。

f:id:azotar:20220224080904p:plain

インプットデータを一巡通過するまではグループ自体が確定しないというところが面白いと感じています。

アイディア

2つのワーク変数(ループのその時点の「分類実績」を格納する「2次元配列」のデータとこの配列の何個目のグループにより分けられているかの「索引」を保持するデータ)を使います。

なお、出身大学が違っても出身県が一緒なら、逆に出身県が違っても出身大学が同じならという繋がっていく関係を「トラバース」と呼びました。

f:id:azotar:20220224081615p:plain

Pythonでのプログラム例

一旦、グループ自体の炙り出しを行うところまでです。 なお、万能ではないものの「性能」という意味では、ハッシュ系の「型」は"速い"傾向があるというところをアテにしたものになっています。

import copy
def teamgrouping(listoftokens):
    teams =[] # チーム名簿
    tn = {}  # チーム所属台帳 TeamNumber: あるトークンの所属チーム番号(temasのインデックス値)の辞書
    for _tokens in listoftokens:
        tokens = copy.copy(_tokens)
        # 関連するチームを炙り出す ( TeamNoのリスト→ tnlist )
        tnlst = sorted(list(set([ tn[t] for t in tokens if t in tn ])))
        # 既存の関連チームの有無を考慮しながらグループ化・再編を実施
        l = len(tnlst)
        if l == 0: # 既存なしのため、新チーム結成〜名簿に登録
            teams.append(tokens)
            idx = len(teams) - 1
        if l == 1: # 既存チームに合流
            idx = tnlst[0]
            teams[idx] += tokens
        if l >= 2: # 最古参のチームに合流し、これを媒介とする他のチームもマージする
            idx = tnlst[0]
            # 新たなメンバを最古参のチームに合流させる
            teams[idx] += tokens
            # 既存のメンバも最古参のチームに合流させる
            for _i in tnlst[1:]:
                for _t in teams[_i]:
                    tn[_t] = idx
                teams[idx] += teams[_i]
                teams[_i] = [] # 役目を終えたので初期化する
        # 台帳を最新化
        for _t in tokens:
            tn[_t] = idx

    return tn,teams

# 動作確認

conf = ['AaBbCcDdEaEbBcFd', #2チーム
    'AaBbCcDdEaEbBcFdDa', #結果的に1チームにまとまる
    '東e西w南s北nEeEn'
]

for c in conf:
    a = list(c)
    aa = [[i,j] for i,j in zip(a[0::2],a[1::2])]
    tn,teams = teamgrouping(aa)
    print('')
    print(aa)
    print(tn)
    print( [sorted(set(t)) for t in teams])
    print('')

思考実験とはいえ、変数名などはもう少し整理した方がよかったかなと思いつつ、それ以外のところでは、もしもっと掘り下げるなら 以下を整備した方が良いかなという自分メモ

  • l ==1と l >=2 あたりは、もう少し、早期リターン(continue)に寄せると、見通しがよくなりそう。
  • tnのアップデートをローカル関数にした方がアルゴリズムの意図は明確になる気がする。
  • リストの結合としているが、set(集合)の演算にした方が良い。場当たり的に import copy をしているが、それも必要なくなる。