home changes contents help options

102:配列から重複する要素を取り除く

(Ruby の配列に相当する Python の型はリストです。)

リストから重複する要素を取り除く

Ruby には Array#uniq という重複要素を取り除くメソッドが存在します。しかし Python リストには存在しません。

このため、何らかの関数を自作する必要があります。たとえば、次のようなものです。

def unique(seq):
    new_list = []
    new_list_add = new_list.append
    seen = set()
    seen_add = seen.add
    for item in seq:
        if item not in seen:
            seen_add(item)
            new_list_add(item)
    return new_list
>>> unique([2, 1, 2, 3, 3, 4, 4, 2, 1, 0])
[2, 1, 3, 4, 0]

上記関数の導出過程

もっとも簡単な実装は次のようなものでしょう。

def u1(seq):
    new_list = []
    for item in seq:
        if item not in new_list:
            new_list.append(item)
    return new_list

seq から要素を一つずつ取り出し、各要素が new_list にすでに入っていないことを確認します。入っていないことを確認したら、この要素を newlist に加えます。

これで、期待通りの動作はしますが、リストの長さが長くなると速度に支障が出ることがあります。この速度の問題を解決するには、重複要素を探るための補助として set を用います。

def u2(seq):
    new_list = []
    seen = set()
    for item in seq:
        if item not in seen:
            seen.add(item)
            new_list.append(item)
    return new_list

さらに seen.add や new_list.append といった属性アクセスを取り除くという微修正を加えると、先ほどの unique 関数となります。

イテレータから重複する要素を除いたイテレータを作る

上記の例では出力はリストという制限があります。より手広い対応をするためにはリストではなくジェネレータを返すようにします。

itertools のドキュメントにある例の一つ、 unique_justseen は、こうしたジェネレータの実装の一つです。

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in iterable:
            if element not in seen:
                seen_add(element)
                yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element
>>> unique_everseen([2, 1, 2, 3, 3, 4, 4, 2, 1, 0])
<generator object unique_everseen at 0x00A1A6E8>
>>> list(_)
[2, 1, 3, 4, 0]

おまけ: 直前の要素と同じ場合のみ、取り除くイテレータを作る

itertools のドキュメントを読み進めると、 unique_everseen と似た名前の unique_justseen という関数も見つかります。これは直前の要素と同じ場合のみ、取り除くジェネレータです。

from itertools import imap, groupby
from operator import itemgetter

def unique_justseen(iterable, key=None):
    "List unique elements, preserving order. Remember only the element just seen."
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
    # unique_justseen('ABBCcAD', str.lower) --> A B C A D
    return imap(next, imap(itemgetter(1), groupby(iterable, key)))
>>> unique_justseen([2, 1, 2, 3, 3, 4, 4, 2, 1, 0])
<itertools.imap object at 0x00AF6A30>
>>> list(_)
[2, 1, 2, 3, 4, 2, 1, 0]

おまけ: set について

set は集合を表現するための型で Python 2.4 より使用することができます。

ある要素を含んでいるか、いないかという状態を保持することに特化しています。このため、順序の概念はありません。また同じ要素を複数含むようなこともありません。

空の set を作るには set 関数(正確には set 型のコンストラクタ)を引数なしで呼びます。要素が含まれている set を作るには、リストなどの iterable を引数に渡して呼びます。

>>> s = set([2, 1, 2, 3, 3, 4, 4, 2, 1, 0])
>>> s
set([0, 1, 2, 3, 4])

ある set に要素を追加するには add メソッド、 取り除くには remove を用います。

>>> s.add(5)
>>> s
set([0, 1, 2, 3, 4, 5])
>>> s.remove(1)
>>> s
set([0, 2, 3, 4, 5])
>>>

ある要素がある set に存在することを確認するには in 演算子を、しないことを確認するには not in 演算子を用います。

>>> 0 in s
True
>>> 100 in s
False

set は iterable なので for 文などでリスト同様に使うことが可能です。 set には順序の概念がないため、入れた順と取り出される順との関連はありません。

>>> for i in s:
...   print i
...
0
1
2
3
4

より詳しい説明は set のドキュメントにあります。

Python 3.0 における変更

set をリテラルとして記述できるようになりました。次のようなものです。

{0, 1, 2, 3}

Python 2.3 以前の set

Python 2.3 には組み込みの set がないので、 sets.Set で代用します。

import sets
set = sets.Set

set との違いについては 組み込み set 型との比較 を参照してください。

Python 2.2 以前には sets.Set もありません。この場合の解決方法の一つは辞書で代用することです。本レシピに登場する unique 関数を辞書を用いて書くと次のようになります。

def unique(seq):
    new_list = []
    seen = {}
    for item in seq:
        if item not in seen:
            seen[item] = None
            new_list.append(item)
    return new_list