python - 高效处理 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]) )。

但是，我不确定如何有效地计算 cluster_id来自大数组大小的链接信息(N > 10⁶)。

编辑:正如@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 µs。

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])