とあるデータに、マスタからデータを紐づく名称を取得してセットするという仕事がありました。初めは何も考えずに線形探索でいけるかな、と考えました。が、思ったよりもデータ量、マスタが複数でこちらもデータ量が多かったので、処理に1、2日要してしまいました。
そこで、これを二分探索での方法にスイッチしたところ、3時間ほどで終わりました。アルゴリズムの知識があまりないのですが、アルゴリズムが大事であることが今更ながら身に染みました。
対象データとマスタデータ
マスタデータは総務省のサイトから「都道府県コード及び市区町村コード」を使うことにしました。コードに対して、都道府県名、市区町村名が割り振られています。
df_master
団体コード 都道府県名 市区町村名
0 10006 北海道 NaN
1 11002 北海道 札幌市
2 12025 北海道 函館市
3 12033 北海道 小樽市
4 12041 北海道 旭川市このマスタを元にして、調べたい団体コードが入っているデータから、都道府県名と市区町村名を繋げた名称をセットします。ターゲットにはマスタの最後にあるID、途中のID、そしてマスタに存在しないデータの3つを用意しました。
df_target
Id 団体コード
0 マスタの最後 473821
1 マスタの途中 14231
2 存在しないコード 500000二分探索をPythonで実装
Pythonには二分探索が簡単に行えるbisectが標準ライブラリであります。これをそのままimportします。
import bisect
import pandas as pdマスタdf_masterは、bisectを利用する際はsortしておく必要があるのでsort_valuesでソートします。
df_target = pd.read_csv("target.csv")
df_master = pd.read_csv("master.csv")
df_master = df_master.sort_values('団体コード', ascending=True)
df_master.reset_index(inplace=True, drop=True)ターゲットの名称カラムに、マスタから取得した都道府県名と市区町村名をセットします。マスタに存在しない場合は’Not Found’をセットします。
for i in range(0, len(df_target)):
print(df_target['団体コード'][i])
result = bisect.bisect(df_master['団体コード'].values.tolist(), df_target['団体コード'][i])
if df_master['団体コード'][result-1] == df_target['団体コード'][i]:
df_target.loc[df_target.index[i], 'マスタ名称'] = df_master['都道府県名'][result-1] + '-' + df_master['市区町村名'][result-1]
else:
print('Not Found')
df_target.loc[df_target.index[i], 'マスタ名称'] = 'Not Found'実装のキモはマスタのソートでしょうか。マスタが初めからソートされていれば問題ないですが、ソートされていない場合はPython上でソートをしておく必要があります。ソートをしないと二分探索がうまくできないので、Not Foundの嵐になってしまいます。
今回の例は、小さいデータセットなので時間はそこまでかかりません。ターゲットのデータ量、マスタのデータ量が増えてくると無視できないレベルになってきます。
コメント