はやっ

ud730ネタ。

train_datasetという20万のデータ, valid_datasetという1万のデータ, test_datasetという1万のデータを格納する配列に対して、互いに幾つかのデータの重複があるという想定のもとそれを検出してみたい。
ということで以下のようなコードを書いた。

from bisect import bisect_left

def find_elem(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return True
    else:
        return False

from hashlib import md5

train_dataset_hash = sorted([md5(v).hexdigest() for v in train_dataset])
valid_dataset_hash = sorted([md5(v).hexdigest() for v in valid_dataset])
test_dataset_hash  = sorted([md5(v).hexdigest() for v in test_dataset])

dup_cnt_between_train_and_valid = 0
dup_cnt_between_train_and_test = 0
dup_cnt_between_valid_and_test = 0
for v in valid_dataset_hash:
    if find_elem(train_dataset_hash, v):
        dup_cnt_between_train_and_valid += 1
for v in test_dataset_hash:
    if find_elem(train_dataset_hash, v):
        dup_cnt_between_train_and_test += 1
for v in valid_dataset_hash:
    if find_elem(test_dataset_hash, v):
        dup_cnt_between_valid_and_test += 1
print("train_dataset and valid_dataset share", dup_cnt_between_train_and_valid, "data")
print("train_dataset and test_dataset share",  dup_cnt_between_train_and_test, "data")
print("valid_dataset and test_dataset share",  dup_cnt_between_valid_and_test, "data")

要するに、

• それぞれの配列の要素に対してmd5値を取得。
• その値を整数値として見てsortして*_hashに格納。
• sort済み配列を2分探索する形で相互に一致する要素の個数を検索。

ということをしている。
数秒で結果が出た。

train_dataset and valid_dataset share 1087 data
train_dataset and test_dataset share 1247 data
valid_dataset and test_dataset share 154 data

2分探索については8.6. bisect — 配列二分法アルゴリズム — Python 3.5.4 ドキュメントを素直に使った。
ミスってるのか？？本当にこんなに一瞬なのか？