Лучший способ (желательно numpythoni c) подсчитать длину до изменения значения и количество переходов в массиве numpy?

Question

Извините, если название немного сбивает с толку, но здесь я объясню подробнее. Скажем, у меня есть большой массив с небольшим количеством уникальных элементов, который выглядит следующим образом:

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

В этом случае массив имеет размер 5x6, например, для целей, но на самом деле я мог бы работать с чем-то как размером 10000x10000 (все еще с небольшим количеством уникальных элементов).

Мне было интересно, как перебирать каждую строку и «подсчитывать» количество раз, когда элемент массива изменяется при перемещении справа налево, а также количество постоянных элементов между переходами.

Например, в приведенном выше массиве первая строка имеет 1 переход и длины 2 и 5 для значений 0 и 1 соответственно. В предпоследней строке есть 3 перехода длиной 1, 1, 2 и 2 для значений 0, 2, 1 и 0 соответственно.

В идеале, некоторая функция transition_count возьмет arr выше и вернет что-то вроде:

row0: [1, (0,2), (1,5)]
row1: [3, (0,1), (2,1), (0,2), (1,3)]
row2: ...

и т. Д.

Я считаю, что нужно перебирать каждую строку массива, arr[i,:] , и проанализировать его отдельно (может быть, в виде списка?). Но даже для одной строки я не знаю, как «подсчитать» количество переходов и получить длину каждого постоянного элемента.

Любая помощь будет принята с благодарностью, спасибо!

Answer 1

Это работает для каждой строки. Не уверен, что мы можем легко векторизовать дальше, учитывая неровный характер вывода.

for row in arr:
    d = np.diff(row) != 0
    idx = np.concatenate(([0], np.flatnonzero(d) + 1))
    c = np.diff(np.concatenate((idx, [len(row)])))
    print(len(c))
    print('v', row[idx])
    print('c', c)

Вот полностью векторизованное решение, если вы готовы принять немного другой формат вывода:

d = np.diff(arr, axis=1) != 0
t = np.ones(shape=arr.shape, dtype=np.bool)
t[:, 1:] = d
e = np.ones(shape=arr.shape, dtype=np.bool)
e[:, :-1] = d
sr, sc = np.nonzero(t)
er, ec = np.nonzero(e)
v = arr[sr, sc]

print(sr)
print(sc)
print(v)
print(ec-sc + 1)

Примечание: вы можете группировать и разбивать эти выходные данные по sr, чтобы получить исходный заявленный формат; но обычно лучше всего держаться подальше от массивов с зазубринами, если вы можете (а вы почти всегда можете!), в том числе и при любой последующей обработке.

Answer 2

Вот векторизованный способ получить все значения и подсчеты -

# Look for interval changes and pad with bool 1s on either sides to set the
# first interval for each row and for setting boundary wrt the next row
p = np.ones((len(a),1), dtype=bool)
m = np.hstack((p, a[:,:-1]!=a[:,1:], p))

# Look for interval change indices in flattened array version
intv = m.sum(1).cumsum()-1

# Get index and counts
idx = np.diff(np.flatnonzero(m.ravel()))  
count = np.delete(idx, intv[:-1])
val = a[m[:,:-1]]

Чтобы перейти к последним разделенным, разбитым на основе строк -

# Get couples and setup offsetted interval change indices
grps = np.c_[val,count]
intvo = np.r_[0,intv-np.arange(len(intv))]

# Finally slice and get output
out = [grps[i:j] for (i,j) in zip(intvo[:-1], intvo[1:])]

Бенчмаркинг

Решение для получения счетчиков и значений в виде функций:

# @Eelco Hoogendoorn's soln
def eh(arr):
    d = np.diff(arr, axis=1) != 0
    t = np.ones(shape=arr.shape, dtype=np.bool)
    t[:, 1:] = d
    e = np.ones(shape=arr.shape, dtype=np.bool)
    e[:, :-1] = d
    sr, sc = np.nonzero(t)
    er, ec = np.nonzero(e)
    v = arr[sr, sc]
    return ec-sc + 1,v

# Function form of proposed solution from this post
def grouped_info(a):
    p = np.ones((len(a),1), dtype=bool)
    m = np.hstack((p, a[:,:-1]!=a[:,1:], p))
    intv = m.sum(1).cumsum()-1
    idx = np.diff(np.flatnonzero(m.ravel()))  
    count = np.delete(idx, intv[:-1])
    val = a[m[:,:-1]]
    return count,val

Мы постараемся приблизиться к вашему фактическому сценарию использования 10000x10000, расположив данный образец мозаикой по двум осям и рассчитав время предлагаемых решений .

In [48]: a
Out[48]: 
array([[0, 0, 1, 1, 1, 1, 1],
       [0, 2, 0, 0, 1, 1, 1],
       [0, 2, 0, 0, 1, 1, 1],
       [0, 2, 1, 1, 1, 0, 0],
       [0, 3, 2, 2, 0, 2, 1]])

In [49]: a = np.repeat(np.repeat(a,1000,axis=0),1000,axis=1)

In [50]: %timeit grouped_info(a)
126 ms ± 7.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [52]: %timeit eh(a)
389 ms ± 41.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)