高效处理 Python 列表中的重复项

Question

我希望在 Python 列表/一维 numpy 数组中紧凑地表示重复项。例如，假设我们有

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

这个数组有几个重复的元素，可以用

表示

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

以便找到给定集群中的所有重复项 x[group_id==<some_id>]。

可以通过排序有效地计算重复对列表，

s_idx = np.argsort(x)
diff_idx = np.nonzero(x[s_idx[:-1]] == x[s_idx[1:]])[0]

其中 s_idx[diff_idx] <-> s_idx[diff_idx+1] 对对应于原始数组中重复的索引。（此处 array([1, 2, 3]) <-> array([2, 5, 4])）。

但是，我不确定如何根据此链接信息为大型数组 (N > 10⁶) 有效地计算 cluster_id。

编辑： 根据@Chris_Rands的建议，这确实可以用itertools.groupby,

 import numpy as np
 import itertools

 def get_group_id(x):
     group_id = np.zeros(x.shape, dtype='int')
     for i, j in  itertools.groupby(x):
         j_el = next(j)
         group_id[x==j_el] = i
     return group_id

但是缩放比例似乎是 O(n^2)，并且这不会缩放到我的用例 (N > 10⁶)，

  for N in [50000, 100000, 200000]:
      %time _ = get_group_id(np.random.randint(0, N, size=N))

  CPU times: total: 1.53 s
  CPU times: total: 5.83 s
  CPU times: total: 23.9 s

我相信使用重复的链接信息会更有效，因为相比之下计算 N=200000 的重复对只需要 6.44 微秒。

Answer 1

您可以使用 numpy.unique:

In [13]: x = np.array([1, 0, 0, 3, 3, 0])

In [14]: values, cluster_id = np.unique(x, return_inverse=True)

In [15]: values
Out[15]: array([0, 1, 3])

In [16]: cluster_id
Out[16]: array([1, 0, 0, 2, 2, 0])

（簇 ID 是按照排序的唯一值的顺序分配的，而不是按照值在输入中首次出现的顺序分配的。）

簇 0 中项目的位置：

In [22]: cid = 0

In [23]: values[cid]
Out[23]: 0

In [24]: (cluster_id == cid).nonzero()[0]
Out[24]: array([1, 2, 5])

Answer 2

这是一种使用 np.unique 根据数字的第一次出现来保持顺序的方法 -

unq, first_idx, ID = np.unique(x,return_index=1,return_inverse=1)
out = first_idx.argsort().argsort()[ID]

样本运行-

In [173]: x
Out[173]: array([1, 0, 0, 3, 3, 0, 9, 0, 2, 6, 0, 0, 4, 8])

In [174]: unq, first_idx, ID = np.unique(x,return_index=1,return_inverse=1)

In [175]: first_idx.argsort().argsort()[ID]
Out[175]: array([0, 1, 1, 2, 2, 1, 3, 1, 4, 5, 1, 1, 6, 7])

高效处理 Python 列表中的重复项

Efficiently handling duplicates in a Python list

python

algorithm

grouping

numpy

graph-algorithm