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

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)

rank变量包含[2, 0, 4, 3, 1]，但是[2, 0, 4, 2, 1]的rank数组是必需的，因为元素 [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 : http://stackoverflow.com/a/41242285/3293881 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