pythonにて集合(リスト)の要素の文字列と部分一致しているかを効率よくおこないたい

Question

以下のように一意なidが格納されている集合(一意の場合リストより良い?)において

{"https://m001", "https://m034", ... ,"https://m993998", "https://m999959"}

文字列"m034"が集合に含まれているかを確認したいのですが、
効率の良い方法はないでしょうか。

考えたこと:
集合ではなくリストにして各要素ごとに

for element in list:
  if "m034" in element:
      処理

と考えたのですが, これではO(n)となり効率的ではないです.
やはり, 全文一致で行うしかないのでしょうか。

ご教示願います.

Answer 1

こんにちは

ご質問にある集合

{"https://m001", "https://m034", ... ,"https://m993998", "https://m999959"}

の各要素の文字列から、先頭の https:// を除去した文字列を要素とする集合を新たに作るというのは、いかがでしょうか？

urls = { 
    "https://m001", 
    "https://m034",
    "https://m993998",
    "https://m999959"
}

prefix = "https://"
domains = set([url[len(prefix):] for url in urls])

print("m034" in domains)  # => True
print("m099000" in domains)  # => False

• 動作確認用Repl.it: https://repl.it/@jun68ykt/Q259048

Answer 2

全文一致で行うしかないのでしょうか。

O(1) にしたければ、全文一致で行うしかありません。
set は要素のアクセスは O(1) ですが、部分文字列ではハッシュテーブルを参照できません。
なので、部分文字列で調べる場合、質問のコードのように各要素に指定文字が含まれるかどうか判定する必要があります。

numpy を使って判定を Python のコードとして実行するのを避ければ、同じ O(n) だとしても30倍ぐらいは高速になります。

for-loop で確認していく方法

s = []
for i in range(10000):
    s.append(f"https://m{i}")
s = set(s)

%%timeit
for val in s:
    if "m34" in val:
        pass
# 501 µs ± 1.29 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

numpy.isin() で確認する方法

import numpy as np

s = []
for i in range(10000):
    s.append(f"https://m{i}")
s = np.array(s)

%%timeit
np.isin(s2, "m34");
# 17.9 µs ± 34.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

numpy を使えば、処理は C 言語で書かれたコードで実行されるため、高速になります。
Python と C 言語だと速度に最大100倍ぐらい差があります。