集合型での照合の高速化
V社の担当者は、1,000万件の購買ログの会員IDそれぞれについて、10万件の除外会員リスト(Pythonのlist型)に含まれるかを「if 会員ID in 除外リスト:」で判定している。処理に非常に時間がかかる。判定を大きく速くする方法として、最も適切なものを1つ選べ。
- A
除外リストを昇順に並べ替えてから、同じようにinで判定する。
- B
除外リストをset型に変換してから、同じようにinで判定する。
- C
除外リストをtuple型に変換してから、同じようにinで判定する。
- D
for文をwhile文に書き換えて、購買ログを1件ずつ判定する。
正解と解説を見る
正解:B
list型やtuple型のinは要素数に比例した時間がかかるが、set型や辞書型のinはハッシュにより平均で一定の時間で済む。大量の照合では型の選び方が処理時間を大きく左右する。
- A
誤り。list型のinは並べ替えても先頭から順に調べるため、速くならない。並びを生かすには二分探索を自分で使う必要がある。
- B
正しい。set型はハッシュを使うため、要素が含まれるかを平均して一定の時間で判定でき、先頭から順に調べるlist型より大幅に速い。
- C
誤り。tuple型のinもlist型と同じく先頭から順に調べるため、計算量は変わらない。
- D
誤り。繰り返しの書き方を変えても、1回ごとの判定にかかる時間は変わらない。
このサイトの問題は、各試験の公開されている出題範囲に沿って作ったオリジナルの模擬問題です。本試験の問題ではありません。一般社団法人データサイエンティスト協会・一般財団法人統計質保証推進協会の公式サービスではありません。