Pythonアルゴリズム

Pythonでリストから重複を取り除く

このレッスンでは、最初に出てきた順番を保ったまま、リストの重複した値を取り除きます。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

重複したデータはレポート、メール、件数を狂わせます。値が最初に現れた順番を保ったまま各値を1回ずつにしたいことがよくあり、長いリストでも速く動いてほしいものです。

身近なたとえ

重複の除去は、カウンターと名簿を持った入口の係員のようなものです。来た人ごとに名簿を確認し、初めての人は名前を書いて入れ、再び来た人は断ります。部屋は来た順に埋まっていきます。

入口の係員からコードへ
seen = set()📋 名簿
if value not in seen:🔎 初めての人?
seen.add(value)✍️ 名前を書き留める
result.append(value)🚪 来た順に入れる
各値を1回だけ調べ、最初の出現だけを残します。
ひと言でいうと

順番を保った重複の除去は、各値の最初の出現を残します。高速なチェックにはセットを、順番を保つにはリストを使います。

重要なポイント

  1. seen はセットなので、長いリストでも value not in seen は速く調べられます。
  2. seen.add(value) は最初に現れたときに値を記録します。
  3. result.append(value) は値を最初に現れた順に保ちます。
  4. 結果は [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. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

結果のリストで存在を調べる

value in result は毎回リスト全体を調べるので、長い入力では遅くなります。

問題
if value not in result:
    result.append(value)
修正
if value not in seen:
    seen.add(value)
    result.append(value)

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ