[解決済み] リスト一覧から重複を削除する

質問

Pythonでリストのリストを持っています。

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

そして、そこから重複する要素を削除したいのです。リストでない普通のリストなら set . しかし、残念なことに、リストはハッシュ化できないので、リストの集合を作ることができません。タプルのみ。そこで、すべてのリストをタプルに変換して、setを使ってリストに戻すことができます。しかし、これは高速ではありません。

どうすれば一番効率よくできるのでしょうか？

上記のリストの結果は、次のようになるはずです。

k = [[5, 6, 2], [1, 2], [3], [4]]

保存順は気にしない。

注 この質問 は似ていますが、私が必要としているものとは全く違います。SOで検索してみましたが、完全な複製は見つかりませんでした。

ベンチマークを行う。

import itertools, time


class Timer(object):
    def __init__(self, name=None):
        self.name = name

    def __enter__(self):
        self.tstart = time.time()

    def __exit__(self, type, value, traceback):
        if self.name:
            print '[%s]' % self.name,
        print 'Elapsed: %s' % (time.time() - self.tstart)


k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [5, 2], [6], [8], [9]] * 5
N = 100000

print len(k)

with Timer('set'):
    for i in xrange(N):
        kt = [tuple(i) for i in k]
        skt = set(kt)
        kk = [list(i) for i in skt]


with Timer('sort'):
    for i in xrange(N):
        ks = sorted(k)
        dedup = [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]]


with Timer('groupby'):
    for i in xrange(N):
        k = sorted(k)
        dedup = list(k for k, _ in itertools.groupby(k))

with Timer('loop in'):
    for i in xrange(N):
        new_k = []
        for elem in k:
            if elem not in new_k:
                new_k.append(elem)

短いリストでは "loop in" (quadratic method) が最も速いです。長いリストでは、groupbyメソッド以外のすべてのメソッドよりも高速です。これって意味があるんでしょうか？

短いリスト（コード内のもの）については、100000回の繰り返しです。

[set] Elapsed: 1.3900001049
[sort] Elapsed: 0.891000032425
[groupby] Elapsed: 0.780999898911
[loop in] Elapsed: 0.578000068665

より長いリスト（コード内のものが5回重複している）の場合。

[set] Elapsed: 3.68700003624
[sort] Elapsed: 3.43799996376
[groupby] Elapsed: 1.03099989891
[loop in] Elapsed: 1.85900020599

解決方法は？

>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
>>> import itertools
>>> k.sort()
>>> list(k for k,_ in itertools.groupby(k))
[[1, 2], [3], [4], [5, 6, 2]]

itertools この種の問題に対して、しばしば最も迅速かつ強力な解決策を提供し さて を使いこなす価値がありますね！)

編集 コメントにも書きましたが、通常の最適化作業は大きな入力に集中します（ビッグ・オー・アプローチ）。しかし、時には（基本的には、性能限界の限界に挑戦しているコードの深い内部ループの、悲劇的に重要なボトルネックについて）、確率分布を提供し、最適化する性能指標を決定し（アプリによっては、平均や中央値よりも、上限や90%セントが重要かもしれません）、入力データの特性に応じて異なるアルゴリズムを選ぶために開始時におそらく発見的チェックを実行するなど、より詳細に行う必要があるかもしれません。

ポイントパフォーマンス（特定の入力に対するコードA対コードB）の入念な測定は、この非常にコストのかかるプロセスの一部であり、標準ライブラリモジュール timeit ここで役立つのが しかし、シェルのプロンプトで使う方が簡単です。 例えば、この問題に対する一般的なアプローチを紹介するための短いモジュールがここにあります。 nodup.py :

import itertools

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

def doset(k, map=map, list=list, set=set, tuple=tuple):
  return map(list, set(map(tuple, k)))

def dosort(k, sorted=sorted, xrange=xrange, len=len):
  ks = sorted(k)
  return [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]]

def dogroupby(k, sorted=sorted, groupby=itertools.groupby, list=list):
  ks = sorted(k)
  return [i for i, _ in itertools.groupby(ks)]

def donewk(k):
  newk = []
  for i in k:
    if i not in newk:
      newk.append(i)
  return newk

# sanity check that all functions compute the same result and don't alter k
if __name__ == '__main__':
  savek = list(k)
  for f in doset, dosort, dogroupby, donewk:
    resk = f(k)
    assert k == savek
    print '%10s %s' % (f.__name__, sorted(resk))

サニティチェックに注意してください（単に python nodup.py という基本的なテクニック（スピードアップのためにグローバルな定数名を各関数にローカルにする）を使って、対等な立場で物事を進めています。

これで、小さな例のリストに対してチェックを実行することができます。

$ python -mtimeit -s'import nodup' 'nodup.doset(nodup.k)'
100000 loops, best of 3: 11.7 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dosort(nodup.k)'
100000 loops, best of 3: 9.68 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dogroupby(nodup.k)'
100000 loops, best of 3: 8.74 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.donewk(nodup.k)'
100000 loops, best of 3: 4.44 usec per loop

2 次アプローチは定数が小さいので、重複する値の少ない小さなリストでは魅力的であることが確認できました。 重複のない短いリストで

$ python -mtimeit -s'import nodup' 'nodup.donewk([[i] for i in range(12)])'
10000 loops, best of 3: 25.4 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dogroupby([[i] for i in range(12)])'
10000 loops, best of 3: 23.7 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.doset([[i] for i in range(12)])'
10000 loops, best of 3: 31.3 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dosort([[i] for i in range(12)])'
10000 loops, best of 3: 25 usec per loop

二次的なアプローチも悪くないけど、sortやgroupbyの方が良いよ。 などなど。

もし（パフォーマンスへのこだわりが示唆するように）この操作が境界を押し広げるアプリケーションのコアな内部ループにあるならば、他の代表的な入力サンプルで同じテストのセットを試してみる価値があります。おそらく、ヒューリスティックにどちらかのアプローチを選ぶことができる簡単な尺度を検出することができるでしょう（ただし、尺度は当然ながら高速でなければなりません）。

を別の表現にしておくことも十分検討に値する。 k -- そもそも、なぜタプルの集合ではなく、リストの集合でなければならないのでしょうか？ もし、重複除去のタスクが頻繁に発生し、プロファイリングでそれがプログラムのパフォーマンスのボトルネックであることがわかれば、例えば、常にタプルのセットを保持し、必要なときだけそこからリストのリストを取得する方が全体的に速くなるかもしれません。