测试元组是否所有元素都不同

Question

我在寻找一种方法来检查一个元组里的元素是否都是不同的，也就是说，它是不是一个集合。最后我找到了一个简单粗暴的解决方案。

def distinct ( tup):
    n=0
    for t in tup:
        for k in tup:
            #print t,k,n
            if (t == k ):
                n = n+1
    if ( n != len(tup)):
        return False
    else :
        return True


print distinct((1,3,2,10))

print distinct((3,3,4,2,7))

这样做有没有什么思路上的错误？元组里有没有现成的功能可以用？

Answer 1

a = (1,2,3,4,5,6,7,8,9)
b = (1,2,3,4,5,6,6,7,8,9)
def unique(tup):
    i = 0
    while i < len(tup):
        if tup[i] in tup[i+1:]:
            return False
        i = i + 1    
    return True    

unique(a)
True
unique(b)
False

这个方法简单易懂，并且可以处理那些可以被哈希的东西。很多人对“while”这个词有点抵触。这种方式也能处理一些“特殊情况”，还能根据属性进行筛选。

Answer 2

关于使用 early_exit 的情况：

这样做会更快：

def distinct(tup):
    s = set()
    for x in tup:
        if x in s:
            return False
        s.add(x)
    return True

好的：这里是对 1000 个整数的测试和性能分析：

#!/usr/bin/python

def distinct1(tup):
    n=0
    for t in tup:
        for k in tup:
            if (t == k ):
                n = n+1
    if ( n != len(tup)):
        return False
    else :
        return True

def distinct2(tup):
    return len(set(tup))==len(tup)

def distinct3(tup):
    s = set()
    for x in tup:
        if x in s:
            return False
        s.add(x)
    return True

import cProfile
from faker import Faker
from timeit import Timer

s = Faker()
func = [ distinct1, distinct2, distinct3 ]
tuples = tuple([ s.random_int(min=1, max=9999) for x in range(1000) ])

for fun in func:
    t = Timer(lambda: fun(tuples))
    print fun.__name__, cProfile.run('t.timeit(number=1000)')

输出结果：distinct 2 和 distinct3 几乎是一样的。

distinct1          3011 function calls in 60.289 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   60.289   60.289 <string>:1(<module>)
     1000   60.287    0.060   60.287    0.060 compare_tuple.py:3(distinct1)
     1000    0.001    0.000   60.288    0.060 compare_tuple.py:34(<lambda>)
        1    0.000    0.000    0.000    0.000 timeit.py:143(setup)
        1    0.000    0.000   60.289   60.289 timeit.py:178(timeit)
        1    0.001    0.001   60.289   60.289 timeit.py:96(inner)
        1    0.000    0.000    0.000    0.000 {gc.disable}
        1    0.000    0.000    0.000    0.000 {gc.enable}
        1    0.000    0.000    0.000    0.000 {gc.isenabled}
        1    0.000    0.000    0.000    0.000 {globals}
     1000    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {time.time}


None
distinct2          4011 function calls in 0.053 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.053    0.053 <string>:1(<module>)
     1000    0.052    0.000    0.052    0.000 compare_tuple.py:14(distinct2)
     1000    0.000    0.000    0.053    0.000 compare_tuple.py:34(<lambda>)
        1    0.000    0.000    0.000    0.000 timeit.py:143(setup)
        1    0.000    0.000    0.053    0.053 timeit.py:178(timeit)
        1    0.000    0.000    0.053    0.053 timeit.py:96(inner)
        1    0.000    0.000    0.000    0.000 {gc.disable}
        1    0.000    0.000    0.000    0.000 {gc.enable}
        1    0.000    0.000    0.000    0.000 {gc.isenabled}
        1    0.000    0.000    0.000    0.000 {globals}
     2000    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {time.time}


None
distinct3          183011 function calls in 0.072 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.072    0.072 <string>:1(<module>)
     1000    0.051    0.000    0.070    0.000 compare_tuple.py:17(distinct3)
     1000    0.002    0.000    0.072    0.000 compare_tuple.py:34(<lambda>)
        1    0.000    0.000    0.000    0.000 timeit.py:143(setup)
        1    0.000    0.000    0.072    0.072 timeit.py:178(timeit)
        1    0.000    0.000    0.072    0.072 timeit.py:96(inner)
        1    0.000    0.000    0.000    0.000 {gc.disable}
        1    0.000    0.000    0.000    0.000 {gc.enable}
        1    0.000    0.000    0.000    0.000 {gc.isenabled}
        1    0.000    0.000    0.000    0.000 {globals}
   181000    0.019    0.000    0.019    0.000 {method 'add' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {time.time}


None

Answer 3

在大多数情况下，如果元组中的所有项目都是可哈希的，并且可以相互比较（使用 == 操作符），那么 @sshashank124的解决方案 正是你需要的：

len(set(tup))==len(tup)

对于你提供的例子，也就是一个整数的元组，这个方法是可以的。

---

如果项目不是可哈希的，但有定义的顺序（支持 '=='、'<' 操作符等），那么你能做的最好方法就是先对它们进行排序（最坏情况下是 O(NlogN)），然后查找相邻的相等元素：

sorted_tup = sorted(tup)
all( x!=y for x,y in zip(sorted_tup[:-1],sorted_tup[1:]) ) 

---

如果项目只支持相等比较（==），那么你能做的最好方法是最坏情况下 O(N^2) 的算法，也就是将每个项目与其他每个项目进行比较。

我会这样实现，使用 itertools.combinations：

def distinct(tup):
  for x,y in itertools.combinations(tup, 2):
    if x == y:
      return False
  return True

或者可以用一行代码实现：

all( x!=y for x,y in itertools.combinations(tup, 2) )

Answer 4

你可以很简单地这样做：

len(set(tup))==len(tup)

这段代码会创建一个叫做 set 的集合，里面放的是 tup 的内容，并检查这个集合的长度是否和原来的 tup 一样长。只有在 tup 中的所有元素都是独一无二的情况下，它们的长度才会相同。

示例

>>> a = (1,2,3)
>>> print len(set(a))==len(a)
True

>>> b = (1,2,2)
>>> print len(set(b))==len(b)
False

>>> c = (1,2,3,4,5,6,7,8,5)
>>> print len(set(c))==len(c)
False