在数组中确定重复值

Question

假设我有一个数组

a = np.array([1, 2, 1, 3, 3, 3, 0])

我如何（高效、Python式地）找到数组a中的重复元素（即非唯一值）？ 在这种情况下，结果将是array([1, 3, 3])或者如果更高效，则可能是array([1, 3])。

我想出了几种方法似乎可以解决问题：

屏蔽

m = np.zeros_like(a, dtype=bool)
m[np.unique(a, return_index=True)[1]] = True
a[~m]

Set 操作

a[~np.in1d(np.arange(len(a)), np.unique(a, return_index=True)[1], assume_unique=True)]

这个例子很可爱，但很可能是非法的（因为 a 实际上并不是唯一的）：

np.setxor1d(a, np.unique(a), assume_unique=True)

直方图

u, i = np.unique(a, return_inverse=True)
u[np.bincount(i) > 1]

排序

s = np.sort(a, axis=None)
s[:-1][s[1:] == s[:-1]]

Pandas

s = pd.Series(a)
s[s.duplicated()]

我有什么遗漏的吗？我不一定要求使用仅限于numpy的解决方案，但它必须能够处理numpy数据类型并且在中等大小的数据集（最多1000万）上具有高效性。

---

结论

在一个1000万大小的数据集上进行测试（在2.8GHz Xeon上）：

a = np.random.randint(10**7, size=10**7)

最快的方法是排序，只需1.1秒。第二是可疑的xor1d，需要2.6秒，接下来是掩码和Pandas的Series.duplicated，需要3.1秒；bincount需要5.6秒，而in1d和senderle的setdiff1d都需要7.3秒。Steven的Counter稍微慢一点，需要10.5秒；Burhan的Counter.most_common需要110秒，而DSM的Counter减法则需要360秒。

我将使用排序以获得更好的性能，但我选择接受Steven的答案，因为它看起来更加清晰和符合Pythonic风格。

编辑：发现了Pandas的解决方案。如果有Pandas可用，则该解决方案效果明显且性能良好。

- ecatmur

---

你能解释一下为什么这个排序解决方案有效吗？我尝试了一下，但出于某种原因，我真的不太明白。 - Markus

@Markus 如果你对一个数组进行排序，任何重复的值都会相邻。然后你可以使用布尔掩码来仅选择与前一个项目相等的项。 - ecatmur

难道不应该是s[:-1][ s[1:] == s[:-1] ]吗？否则我会得到一个IndexError，因为布尔掩码比s数组少一个元素... - snake_charmer

@snake_charmer 我认为早期版本的numpy在这方面更加宽容。我会修复它，谢谢。 - ecatmur

pandas似乎已经改进了一些底层方法的性能。在我的机器上，pandas仅比排序方法慢29％。Mad Physicist提出的方法比排序慢17％。 - JE_Muc

FYI：我刚试过对一个普通列表进行排序，但是无效。然而，如果使用已排序的 numpy array，则可以起作用。 - Godrebh

Answer 1

从numpy版本1.9.0开始，np.unique有一个参数return_counts，它极大地简化了您的任务：

u, c = np.unique(a, return_counts=True)
dup = u[c > 1]

这类似于使用Counter，但您会得到一对数组而不是映射。我很想知道它们相对于彼此的表现如何。

值得注意的是，即使np.unique在实践中非常快速，因为它是numpy的特性，但其算法复杂度比Counter解决方案差。 np.unique基于排序，因此以O(n log n)的时间渐近运行。 Counter是基于哈希的，因此具有O(n)的复杂度。这只对最大的数据集才会有很大影响。

- Mad Physicist

---

简单的解决方案。谢谢。 - dmrobotix

在非常大的数据集上，计数器每个对象的空间开销可能会成为限制因素。 - TLW

@MadPhysicist - 你应该查看Python对象的大小。每个对象的开销可能会让你感到惊讶。 - TLW

NumPy数组没有所谓的开销，因为它们直接存储数据。这是NumPy数组使用起来可能有些古怪的原因之一，但也意味着例如10亿个uint8元素的数组只需要占用约1GB的空间，而不是如果元素是Python对象则需要占用约8B的空间。 - TLW

@TLW。明白了，将打包的NumPy数组转换确实会很昂贵。我完全忘记这个问题是关于NumPy的，而且假设数据预先存储在内存中作为Python对象。我熟悉Python整数格式和内联。 - Mad Physicist

Answer 2

我认为这最好在 numpy 之外完成。如果你关心速度，你需要与你的 numpy 解决方案进行比较计时。

>>> import numpy as np
>>> from collections import Counter
>>> a = np.array([1, 2, 1, 3, 3, 3, 0])
>>> [item for item, count in Counter(a).items() if count > 1]
[1, 3]

注意：这类似于Burhan Khalid的回答，但在条件中没有使用下标的items应该更快。

- Steven Rumbalski

---

注意：在Python 3中必须使用Counter(a).items()。 - Maaaaa

Answer 3

已经有人提出了 Counter 的变种，但是这里介绍一个不使用列表推导的：

>>> from collections import Counter
>>> a = [1, 2, 1, 3, 3, 3, 0]
>>> (Counter(a) - Counter(set(a))).keys()
[1, 3]

[这篇文章发布的原因并不是因为它很有效 -- 它并不是 -- 而是因为我觉得你可以从 Counter 实例中减去另一个实例，这个功能很可爱。]

- DSM

---

更加高效的方法是不要重新计算集合： c = Counter(a); result = (c - Counter(c.keys())).keys() - Mad Physicist

Answer 4

Python 2.7+版本

>>> import numpy
>>> from collections import Counter
>>> n = numpy.array([1,1,2,3,3,3,0])
>>> [x[1] for x in Counter(n).most_common() if x[0] > 1]
[3, 1]

- Burhan Khalid

---

x[0] > 1 应该改为 x[1] > 1 吗？后面的 x 表示频率。 - Green Falcon

Answer 5

这里有另一种使用集合操作的方法，我认为比你提供的更加直接：

>>> indices = np.setdiff1d(np.arange(len(a)), np.unique(a, return_index=True)[1])
>>> a[indices]
array([1, 3, 3])

我猜你是要求仅使用 numpy 来解决问题，因为如果不是这种情况，只使用 Counter 就很难进行辩论。但我认为你应该明确说明这个要求。

- senderle

---

我认为这种方法的一个缺点是3被重复了，而1没有。最好是统一一种方式。(这不是对你回答的批评，而是对原始方法的批评。) - Steven Rumbalski

@StevenRumbalski，是的，我明白你的意思。我的感觉是，如果真正需要的是掩码而不是项目列表，则重复的“3”是有意义的；如果需要的是项目列表，则我同意不要有重复的项目更好。 - senderle

我不反对使用Counter，但我关心效率和兼容性。 - ecatmur

Answer 6

如果数组是已经排序好的numpy数组，那么只需要这样做：

a = np.array([1, 2, 2, 3, 4, 5, 5, 6])
rep_el = a[np.diff(a) == 0]

- Thomas Antony

---

a[1:][np.diff(a) == 0]，不是吗？ - Mad Physicist

Answer 7

如果a由小整数组成，您可以直接使用numpy.bincount：

import numpy as np

a = np.array([3, 2, 2, 0, 4, 3])
counts = np.bincount(a)
print np.where(counts > 1)[0]
# array([2, 3])

这非常类似于你的“直方图”方法，如果a不是由小整数组成，那么我会使用它。

- Bi Rico

Answer 8

我正在为这个三年前的问题添加我的解决方案，因为没有一个解决方案符合我想要的或使用除numpy之外的libs。该方法找到重复元素的索引和不同重复集的值。

import numpy as np

A = np.array([1,2,3,4,4,4,5,6,6,7,8])

# Record the indices where each unique element occurs.
list_of_dup_inds = [np.where(a == A)[0] for a in np.unique(A)]

# Filter out non-duplicates.
list_of_dup_inds = filter(lambda inds: len(inds) > 1, list_of_dup_inds)

for inds in list_of_dup_inds: print inds, A[inds]
# >> [3 4 5] [4 4 4]
# >> [7 8] [6 6]

- Matt Hancock

---

三年后，你仍然可以使用unique函数的return_counts参数来完成这个任务。请参考我的回答。 - Mad Physicist

Answer 9

>>> import numpy as np

>>> a=np.array([1,2,2,2,2,3])

>>> uniques, uniq_idx, counts = np.unique(a,return_index=True,return_counts=True)
>>> duplicates = a[ uniq_idx[counts>=2] ]  # <--- Get duplicates

如果您也想获得孤儿节点：

>>> orphans = a[ uniq_idx[counts==1] ] 

- hydev

Answer 10

结合Pandas和Numpy（利用value_counts()函数）：

import pandas as pd
import numpy as np

arr=np.array(('a','b','b','c','a'))
pd.Series(arr).value_counts()

输出：

a    2
b    2
c    1

- DYARI MOHAMMED SHARIF