8

私は頻繁に and を使用sortedしgroupbyて、イテラブル内の重複アイテムを見つけます。今、私はそれが信頼できないことがわかります:

from itertools import groupby
data = 3 * ('x ',  (1,), u'x')
duplicates = [k for k, g in groupby(sorted(data)) if len(list(g)) > 1]
print duplicates
# [] printed - no duplicates found - like 9 unique values

上記のコードが Python 2.x で失敗する理由は、ここで説明されています。

重複を見つけるための信頼できるpythonicの方法は何ですか?

SOで同様の質問/回答を探しました。それらの最高のものは「Pythonでは、リストを取得して重複のリストに減らすにはどうすればよいですか?」ですが、受け入れられた解決策はpythonicではありません(手続き型の複数行の... if ... add ... else ... add ... return result) およびその他のソリューションは信頼できない ("<" 演算子の満たされていない推移性に依存する) か、遅い (O n*n)。

【追記】閉店しました。受け入れられた回答は、より一般的な以下の回答の結論を要約するのに役立ちました。

私は組み込み型を使用してツリー構造などを表すのが好きです。これが私が今ミックスを恐れている理由です。

4

5 に答える 5

11

注：エントリはハッシュ可能であると想定しています

>>> from collections import Counter
>>> data = 3 * ('x ',  (1,), u'x')
>>> [k for k, c in Counter(data).iteritems() if c > 1]
[u'x', 'x ', (1,)]
于 2012-04-20T14:06:18.247 に答える
1

結論：

  • すべてのアイテムがハッシュ可能で、少なくとも Python 2.7 である場合、最善の解決策は上記のcollections.Counterです。
  • 一部のアイテムがハッシュ可能でないか、Python 2.7+ が存在しない場合、ソリューションgroupby(sorted(..))は条件の下で非常に優れています
    • str と unicode を組み合わせない
    • "str" と "unicode" の間にアルファベット順で配置された名前の型は使用しないでください。(通常は「タプル」または「タイプ」)
  • データがハッシュ化できず、型が混在している場合、上記のものは使用できず、次を使用するのが最善です。
    • Counter(map(pickled.dumps, data))代わりにCounter(data)、最終的に解凍するか、
    • groupby(sorted(data, key=pickled.dumps))unpickle が望ましくない場合、または python 2.7 がない場合
  • 以下で説明する「単純な解決策」は、約 300 未満の非常に少数のアイテムの場合は酸洗よりも優れている可能性があります。

他の質問の他のすべての解決策は、現在より悪いです。

ノート：

  • クラス Counter をコピーして下位の Python バージョンに貼り付けることができるようです。
  • データ全体のすべてのアイテムを検索する「単純なソリューション」は、非常に少数のアイテムに使用できます。ハッシュ可能なデータを必要とせず、デフォルトの「<」演算子の推移性に依存しないという利点がありますが、ハッシュ可能なアイテムが 25 個を超える場合はカウンターが優れており、ハッシュできない「ワイルド」アイテムが 300 個を超える場合は、ピクルスのカウンターが優れています。アイテム。

アイテムをタイプ別に事前にソートするか、ハッシュ可能なアイテムのハッシュで拡張することを考えましたが、現在は役に立ちますが、「<」演算子のサイト内リスト、タプルなどでも同じ問題が発生するため、安全な解決策ではありません.

于 2012-04-21T10:16:53.160 に答える
1

このテーマは私にとって興味深いので、上記の解決策と他のスレッドで受け入れられた解決策の時間を計りました。

Counter メソッドは、このスレッドが非常にエレガントであることです。ただし、このスレッドで受け入れられた回答In Python, how do I take a list and reduce it to a list of duplicates? 約2倍速くなるようです。

import random as rn
import timeit
from collections import Counter

a = [rn.randint(0,100000) for i in xrange(10000)]

def counter_way(x):
    return [k for k,v in Counter(x).iteritems() if v > 1]

def accepted_way(x): #accepted answer in the linked thread
    duplicates = set()
    found = set()
    for item in x:
        if item in found:
            duplicates.add(item)
        else:         
            found.add(item)
    return duplicates


t1 = timeit.timeit('counter_way(a)', 'from __main__ import counter_way, a', number = 100)
print "counter_way: ", t1
t2 = timeit.timeit('accepted_way(a)','from __main__ import accepted_way, a', number = 100)
print "accepted_way: ", t2

結果：

counter_way:  1.15775845813
accepted_way:  0.531060022992

さまざまな仕様でこれを試しましたが、結果は常に同じです。

于 2012-04-21T19:03:21.077 に答える
0

私が興味を持っていたので、0、False、0.0などの違いを生む解決策を次に示します。これはmy_cmp、アイテムのタイプも考慮してシーケンスをソートすることに基づいています。もちろん、上記のソリューションと比較して非常に遅いです。これは並べ替えによるものです。しかし、結果を比較してください！

import sys
import timeit
from collections import Counter

def empty(x):
    return

def counter_way(x):
    return [k for k,v in Counter(x).iteritems() if v > 1]

def accepted_way(x): #accepted answer in the linked thread
    duplicates = set()
    found = set()
    for item in x:
        if item in found:
            duplicates.add(item)
        else:         
            found.add(item)
    return duplicates


def my_cmp(a, b):
    result = cmp(a, b)
    if result == 0:
        return cmp(id(type(a)), id(type(b)))
    return result    


def duplicates_via_sort_with_types(x, my_cmp=my_cmp):

    last = '*** the value that cannot be in the sequence by definition ***'
    duplicates = []
    added = False
    for e in sorted(x, cmp=my_cmp):
        if my_cmp(e, last) == 0:
            ##print 'equal:', repr(e), repr(last), added
            if not added:
                duplicates.append(e)
                ##print 'appended:', e
                added = True
        else:
            ##print 'different:', repr(e), repr(last), added
            last = e
            added = False
    return duplicates


a = [0, 1, True, 'a string', u'a string', False, 0.0, 1.0, 2, 2.0, 1000000, 1000000.0] * 1000

print 'Counter way duplicates:', counter_way(a)
print 'Accepted way duplicates:', accepted_way(a)
print 'Via enhanced sort:', duplicates_via_sort_with_types(a) 
print '-' * 50

# ... and the timing
t3 = timeit.timeit('empty(a)','from __main__ import empty, a', number = 100)
print "empty: ", t3
t1 = timeit.timeit('counter_way(a)', 'from __main__ import counter_way, a', number = 100)
print "counter_way: ", t1
t2 = timeit.timeit('accepted_way(a)','from __main__ import accepted_way, a', number = 100)
print "accepted_way: ", t2
t4 = timeit.timeit('duplicates_via_sort_with_types(a)','from __main__ import duplicates_via_sort_with_types, a', number = 100)
print "duplicates_via_sort_with_types: ", t4

それは私のコンソールに印刷されます：

c:\tmp\___python\hynekcer\so10247815>python e.py
Counter way duplicates: [0, 1, 2, 'a string', 1000000]
Accepted way duplicates: set([False, True, 2.0, u'a string', 1000000.0])
Via enhanced sort: [False, 0.0, 0, True, 1.0, 1, 2.0, 2, 1000000.0, 1000000, 'a string', u'a string']
--------------------------------------------------
empty:  2.11195471969e-05
counter_way:  0.76977053612
accepted_way:  0.496547434023
duplicates_via_sort_with_types:  11.2378848197
于 2012-04-24T07:52:44.730 に答える
0

ただし、どちらのソリューションにも落とし穴があります。その理由は、値を同じハッシュでマージするためです。したがって、使用される値が同じハッシュを持つかどうかによって異なります。Python はいくつかの値を特別な方法でハッシュするため、あなたが思うほどクレイジーなコメントではありません (私も先ほど驚きました)。試す：

from collections import Counter


def counter_way(x):
    return [k for k,v in Counter(x).iteritems() if v > 1]

def accepted_way(x): #accepted answer in the linked thread
    duplicates = set()
    found = set()
    for item in x:
        if item in found:
            duplicates.add(item)
        else:         
            found.add(item)
    return duplicates


a = ('x ',  (1,), u'x') * 2

print 'The values:', a
print 'Counter way duplicates:', counter_way(a)
print 'Accepted way duplicates:', accepted_way(a)
print '-' * 50

# Now the problematic values.
a = 2 * (0, 1, True, False, 0.0, 1.0)

print 'The values:', a
print 'Counter way duplicates:', counter_way(a)
print 'Accepted way duplicates:', accepted_way(a)

1、1.0、および True は定義により同じハッシュを持ち、同様に 0、0.0、および False を持ちます。コンソールに次のように表示されます (最後の 2 行について考えてみてください。実際にはすべての値が重複しているはずです)。

c:\tmp\___python\hynekcer\so10247815>python d.py
The values: ('x ', (1,), u'x', 'x ', (1,), u'x')
Counter way duplicates: [u'x', 'x ', (1,)]
Accepted way duplicates: set([u'x', 'x ', (1,)])
--------------------------------------------------
The values: (0, 1, True, False, 0.0, 1.0, 0, 1, True, False, 0.0, 1.0)
Counter way duplicates: [0, 1]
Accepted way duplicates: set([False, True])
于 2012-04-23T07:40:06.280 に答える