python - フラットリストに重複があるかどうかを確認するにはどうすればよいですか？

Question

たとえば、リストが与えられた['one', 'two', 'one']場合、アルゴリズムはを返す必要がありますがTrue、与えられ['one', 'two', 'three']た場合はを返す必要がありFalseます。

Answer 1

set()すべての値がハッシュ可能である場合に重複を削除するために使用します。

>>> your_list = ['one', 'two', 'one']
>>> len(your_list) != len(set(your_list))
True

Answer 2

短いリストにのみ推奨：

any(thelist.count(x) > 1 for x in thelist)

長いリストでは使用しないでください。リスト内のアイテム数の2乗に比例して時間がかかる場合があります。

ハッシュ可能なアイテム（文字列、数値、＆c）を含む長いリストの場合：

def anydup(thelist):
  seen = set()
  for x in thelist:
    if x in seen: return True
    seen.add(x)
  return False

アイテムがハッシュ可能でない場合（サブリスト、dictなど）、ヘアリーになりますが、少なくとも同等であればO（N logN）を取得できる可能性があります。ただし、最高のパフォーマンスを得るには、アイテムの特性（ハッシュ可能かどうか、比較可能かどうか）を知るかテストする必要があります。ハッシュ可能の場合はO（N）、ハッシュ不可能な比較の場合はO（N log N）、それ以外の場合。それはO（Nの2乗）までであり、それについて誰もできることはありません:-(。

Answer 3

これは古いですが、ここでの回答により、少し異なる解決策が得られました。理解を乱用するつもりなら、この方法でショートサーキットを取得できます。

xs = [1, 2, 1]
s = set()
any(x in s or s.add(x) for x in xs)
# You can use a similar approach to actually retrieve the duplicates.
s = set()
duplicates = set(x for x in xs if x in s or s.add(x))

Answer 4

関数型プログラミング スタイルが好きな場合は、便利な関数、自己文書化およびdoctestを使用したテスト済みのコードを次に示します。

def decompose(a_list):
    """Turns a list into a set of all elements and a set of duplicated elements.

    Returns a pair of sets. The first one contains elements
    that are found at least once in the list. The second one
    contains elements that appear more than once.

    >>> decompose([1,2,3,5,3,2,6])
    (set([1, 2, 3, 5, 6]), set([2, 3]))
    """
    return reduce(
        lambda (u, d), o : (u.union([o]), d.union(u.intersection([o]))),
        a_list,
        (set(), set()))

if __name__ == "__main__":
    import doctest
    doctest.testmod()

そこから、返されたペアの 2 番目の要素が空かどうかをチェックすることで、単一性をテストできます。

def is_set(l):
    """Test if there is no duplicate element in l.

    >>> is_set([1,2,3])
    True
    >>> is_set([1,2,1])
    False
    >>> is_set([])
    True
    """
    return not decompose(l)[1]

分解を明示的に構築しているため、これは効率的ではないことに注意してください。しかし、reduce を使用する方法に沿って、5 に答えるのと同等の (ただし効率はわずかに劣る) ものにたどり着くことができます。

def is_set(l):
    try:
        def func(s, o):
            if o in s:
                raise Exception
            return s.union([o])
        reduce(func, l, set())
        return True
    except:
        return False