Присвоить одинаковый лексикографический ранг дублирующим элементам массива 2d

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 : http://stackru.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)]

Метод Уоррена Векессера, основанный на ранжировании данных, как функция времени

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'), рассматривая 2-й массив как 1-й структурированный массив:

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