将相同的词典顺序分配给二维数组的重复元素

Question

我正在尝试按字典顺序排列数组组件。下面的代码工作正常，但我想为相等的元素分配相等的等级。

import numpy as np

values = np.asarray([
    [1, 2, 3],
    [1, 1, 1],
    [2, 2, 3],
    [1, 2, 3],
    [1, 1, 2]
])
# need to flip, because for `np.lexsort` last
# element has highest priority.
values_reversed = np.fliplr(values)
# this returns the order, i.e. the order in
# which the elements should be in a sorted
# array (not the rank by index).
order = np.lexsort(values_reversed.T)
# convert order to ranks.
n = values.shape[0]
ranks = np.empty(n, dtype=int)
# use order to assign ranks.
ranks[order] = np.arange(n)

等级变量包含 [2, 0, 4, 3, 1]，但需要 [2, 0, 4, 2, 1] 的等级数组，因为元素 [1, 2, 3]（索引 0 和 3）共享相同的等级。连续的排名数字是可以的，所以 [2, 0, 3, 2, 1] 也是一个可接受的排名数组。

Answer 1

这是一种方法 -

# Get lexsorted indices and hence sorted values by those indices
lexsort_idx = np.lexsort(values.T[::-1])
lexsort_vals = values[lexsort_idx]

# Mask of steps where rows shift (there are no duplicates in subsequent rows) 
mask = np.r_[True,(lexsort_vals[1:] != lexsort_vals[:-1]).any(1)]

# Get the stepped indices (indices shift at non duplicate rows) and
# the index values are scaled corresponding to row numbers     
stepped_idx = np.maximum.accumulate(mask*np.arange(mask.size))    

# Re-arrange the stepped indices based on the original order of rows
# This is basically same as the original code does in last 4 steps,
# just in a concise manner
out_idx = stepped_idx[lexsort_idx.argsort()]

逐步中间输出示例 -

In [55]: values
Out[55]: 
array([[1, 2, 3],
       [1, 1, 1],
       [2, 2, 3],
       [1, 2, 3],
       [1, 1, 2]])

In [56]: lexsort_idx
Out[56]: array([1, 4, 0, 3, 2])

In [57]: lexsort_vals
Out[57]: 
array([[1, 1, 1],
       [1, 1, 2],
       [1, 2, 3],
       [1, 2, 3],
       [2, 2, 3]])

In [58]: mask
Out[58]: array([ True,  True,  True, False,  True], dtype=bool)

In [59]: stepped_idx
Out[59]: array([0, 1, 2, 2, 4])

In [60]: lexsort_idx.argsort()
Out[60]: array([2, 0, 4, 3, 1])

In [61]: stepped_idx[lexsort_idx.argsort()]
Out[61]: array([2, 0, 4, 2, 1])

性能提升

为了提高计算 lexsort_idx.argsort() 的性能效率，我们可以使用这与最后 4 行中的原始代码相同 -

def argsort_unique(idx):
    # Original idea :  by @Andras
    n = idx.size
    sidx = np.empty(n,dtype=int)
    sidx[idx] = np.arange(n)
    return sidx

因此，lexsort_idx.argsort() 可以用 argsort_unique(lexsort_idx) 替代计算。

运行时测试

再应用一些优化技巧，我们就会有一个像这样的版本 -

def numpy_app(values):
    lexsort_idx = np.lexsort(values.T[::-1])
    lexsort_v = values[lexsort_idx]
    mask = np.concatenate(( [False],(lexsort_v[1:] == lexsort_v[:-1]).all(1) ))

    stepped_idx = np.arange(mask.size)
    stepped_idx[mask] = 0
    np.maximum.accumulate(stepped_idx, out=stepped_idx)

    return stepped_idx[argsort_unique(lexsort_idx)]

@Warren Weckesser 基于排名数据的方法作为计时函数 -

def scipy_app(values):
    v = values.view(np.dtype(','.join([values.dtype.str]*values.shape[1])))
    return rankdata(v, method='min') - 1

计时 -

In [97]: a = np.random.randint(0,9,(10000,3))

In [98]: out1 = numpy_app(a)

In [99]: out2 = scipy_app(a)

In [100]: np.allclose(out1, out2)
Out[100]: True

In [101]: %timeit scipy_app(a)
100 loops, best of 3: 5.32 ms per loop

In [102]: %timeit numpy_app(a)
100 loops, best of 3: 1.96 ms per loop

Answer 2

这是一种使用 scipy.stats.rankdata（使用 method='min'）的方法，方法是将二维数组视为一维结构化数组：

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

In [16]: v = values.view(np.dtype(','.join([values.dtype.str]*values.shape[1])))

In [17]: rankdata(v, method='min') - 1
Out[17]: array([2, 0, 4, 2, 1])

将相同的词典顺序分配给二维数组的重复元素

Assign same lexicographic rank to duplicate elements of 2d array

python

sorting

numpy

lexicographic

lexicographic-ordering