例如,给定列表['one', 'two', 'one'],算法应该返回True,而给定['one', 'two', 'three']则应该返回False。
当前回答
这是老问题了,但这里的答案让我找到了一个略有不同的解决方案。如果您准备滥用推导式,您可能会以这种方式短路。
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))
其他回答
如果所有值都是可哈希的,使用set()删除重复项:
>>> your_list = ['one', 'two', 'one']
>>> len(your_list) != len(set(your_list))
True
这是老问题了,但这里的答案让我找到了一个略有不同的解决方案。如果您准备滥用推导式,您可能会以这种方式短路。
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))
我最近回答了一个相关的问题,使用生成器在一个列表中建立所有的副本。它的优点是,如果只是用来确定“是否有重复”,那么你只需要获取第一项,其余的可以忽略,这是终极捷径。
这是一个有趣的基于集合的方法,我直接改编自moooeeeep:
def getDupes(l):
seen = set()
seen_add = seen.add
for x in l:
if x in seen or seen_add(x):
yield x
因此,完整的dupes列表将是list(getDupes(etc))。为了简单地测试“是否”存在欺骗,它应该被包装如下:
def hasDupes(l):
try:
if getDupes(l).next(): return True # Found a dupe
except StopIteration:
pass
return False
这可以很好地扩展,并且在列表中提供一致的操作时间——我测试了多达1m个条目的列表。如果您对数据有所了解,特别是,被欺骗者可能会在前半段出现,或者其他让您偏离需求的事情,比如需要获得实际的被欺骗者,那么有几个真正的替代dupe定位器可能会表现更好。我推荐的两个是……
简单的基于字典的方法,非常易读:
def getDupes(c):
d = {}
for i in c:
if i in d:
if d[i]:
yield i
d[i] = False
else:
d[i] = True
利用itertools(本质上是一个过滤器/izip/tee)在排序列表上,如果你得到所有的dupes,非常有效,但没有那么快得到第一个:
def getDupes(c):
a, b = itertools.tee(sorted(c))
next(b, None)
r = None
for k, g in itertools.ifilter(lambda x: x[0]==x[1], itertools.izip(a, b)):
if k != r:
yield k
r = k
这些是我为完整的欺骗列表所尝试的方法中表现最好的,第一次欺骗发生在1m元素列表中从开始到中间的任何地方。令人惊讶的是,排序步骤增加的开销很少。你的里程可能会有所不同,但以下是我的具体计时结果:
Finding FIRST duplicate, single dupe places "n" elements in to 1m element array
Test set len change : 50 - . . . . . -- 0.002
Test in dict : 50 - . . . . . -- 0.002
Test in set : 50 - . . . . . -- 0.002
Test sort/adjacent : 50 - . . . . . -- 0.023
Test sort/groupby : 50 - . . . . . -- 0.026
Test sort/zip : 50 - . . . . . -- 1.102
Test sort/izip : 50 - . . . . . -- 0.035
Test sort/tee/izip : 50 - . . . . . -- 0.024
Test moooeeeep : 50 - . . . . . -- 0.001 *
Test iter*/sorted : 50 - . . . . . -- 0.027
Test set len change : 5000 - . . . . . -- 0.017
Test in dict : 5000 - . . . . . -- 0.003 *
Test in set : 5000 - . . . . . -- 0.004
Test sort/adjacent : 5000 - . . . . . -- 0.031
Test sort/groupby : 5000 - . . . . . -- 0.035
Test sort/zip : 5000 - . . . . . -- 1.080
Test sort/izip : 5000 - . . . . . -- 0.043
Test sort/tee/izip : 5000 - . . . . . -- 0.031
Test moooeeeep : 5000 - . . . . . -- 0.003 *
Test iter*/sorted : 5000 - . . . . . -- 0.031
Test set len change : 50000 - . . . . . -- 0.035
Test in dict : 50000 - . . . . . -- 0.023
Test in set : 50000 - . . . . . -- 0.023
Test sort/adjacent : 50000 - . . . . . -- 0.036
Test sort/groupby : 50000 - . . . . . -- 0.134
Test sort/zip : 50000 - . . . . . -- 1.121
Test sort/izip : 50000 - . . . . . -- 0.054
Test sort/tee/izip : 50000 - . . . . . -- 0.045
Test moooeeeep : 50000 - . . . . . -- 0.019 *
Test iter*/sorted : 50000 - . . . . . -- 0.055
Test set len change : 500000 - . . . . . -- 0.249
Test in dict : 500000 - . . . . . -- 0.145
Test in set : 500000 - . . . . . -- 0.165
Test sort/adjacent : 500000 - . . . . . -- 0.139
Test sort/groupby : 500000 - . . . . . -- 1.138
Test sort/zip : 500000 - . . . . . -- 1.159
Test sort/izip : 500000 - . . . . . -- 0.126
Test sort/tee/izip : 500000 - . . . . . -- 0.120 *
Test moooeeeep : 500000 - . . . . . -- 0.131
Test iter*/sorted : 500000 - . . . . . -- 0.157
一个更简单的解决方案如下。只需用pandas . replicated()方法检查True/False,然后取sum。请参阅pandas. series . replicated - pandas 0.24.1文档
import pandas as pd
def has_duplicated(l):
return pd.Series(l).duplicated().sum() > 0
print(has_duplicated(['one', 'two', 'one']))
# True
print(has_duplicated(['one', 'two', 'three']))
# False
如果列表包含不可哈希的项,您可以使用Alex Martelli的解决方案,但使用列表而不是集合,尽管它对于较大的输入较慢:O(N^2)。
def has_duplicates(iterable):
seen = []
for x in iterable:
if x in seen:
return True
seen.append(x)
return False
推荐文章
- Numpy Max vs amax vs maximum
- 我应该如何从字符串中删除所有的前导空格?- - - - - -斯威夫特
- 我应该在.gitignore文件中添加Django迁移文件吗?
- 每n行有熊猫
- 实例属性attribute_name定义在__init__之外
- 如何获取在Python中捕获的异常的名称?
- 第一次出现的值大于现有值的Numpy
- 如何从Python函数中返回两个值?
- 前一个月的Python日期
- Python中方括号括起来的列表和圆括号括起来的列表有什么区别?
- 将整数转换为字符串,以逗号表示千
- Python日志记录不输出任何东西
- 将JavaScript字符串中的多个空格替换为单个空格
- 每n秒运行特定代码
- SQLAlchemy是否有与Django的get_or_create等价的函数?