はじめに
どんな問題を解決するか
重複したデータはレポート、メール、件数を狂わせます。値が最初に現れた順番を保ったまま各値を1回ずつにしたいことがよくあり、長いリストでも速く動いてほしいものです。
身近なたとえ
重複の除去は、カウンターと名簿を持った入口の係員のようなものです。来た人ごとに名簿を確認し、初めての人は名前を書いて入れ、再び来た人は断ります。部屋は来た順に埋まっていきます。
入口の係員からコードへ
seen = set()📋 名簿if value not in seen:🔎 初めての人?seen.add(value)✍️ 名前を書き留めるresult.append(value)🚪 来た順に入れるひと言でいうと
順番を保った重複の除去は、各値の最初の出現を残します。高速なチェックにはセットを、順番を保つにはリストを使います。
重要なポイント
seenはセットなので、長いリストでもvalue not in seenは速く調べられます。seen.add(value)は最初に現れたときに値を記録します。result.append(value)は値を最初に現れた順に保ちます。- 結果は
[3, 1, 2, 4]で、2つ目の3と2つ目の1は飛ばされます。
どんな場面で使う?
- ID、メール、タグの一覧を順番を保ったままきれいにする。
- ログから繰り返されたイベントを取り除く。
- セットとリストを組み合わせるタイミングを学ぶ。
使わなくてよいとき
- 順番が重要でない場合:
set(values)で十分です。 - リストや辞書のようにセットに入れられない値:先にタプルに変換するか、別の方法で比べます。
サンプルコード
main.py
def unique_in_order(values):
seen = set()
result = []
for value in values:
if value not in seen:
seen.add(value)
result.append(value)
return result
print(unique_in_order([3, 1, 3, 2, 1, 4]))
実行結果
[3, 1, 2, 4]
コードの解説
各値はちょうど1回ずつ調べられます。値がまだseenになければ、セットseenとリストresultの両方に追加します。2回目以降に出てきたときは無視されるので、結果は[3, 1, 2, 4]になります。セットに含まれるかの確認はO(1)なので、アルゴリズム全体はO(n)の時間で動きます。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
結果のリストで存在を調べる
value in result は毎回リスト全体を調べるので、長い入力では遅くなります。
問題
if value not in result:
result.append(value)
修正
if value not in seen:
seen.add(value)
result.append(value)
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
進み具合はこのブラウザーに保存されています ログインすると、どのデバイスでも引き継げます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ