Numpy - Как убрать конечные N * 8 нулей

Question

У меня есть 1d массив, мне нужно удалить все конечные блоки из 8 нулей.

[0,1,1,0,1,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0]
->
[0,1,1,0,1,0,0,0]

a.shape[0] % 8 == 0 всегда, так что не беспокойтесь об этом.

Есть ли лучший способсделать это?

import numpy as np
P = 8
arr1 = np.random.randint(2,size=np.random.randint(5,10) * P)
arr2 = np.random.randint(1,size=np.random.randint(5,10) * P)
arr = np.concatenate((arr1, arr2))

indexes = []
arr = np.flip(arr).reshape(arr.shape[0] // P, P)

for i, f in enumerate(arr):
    if (f == 0).all():
        indexes.append(i)
    else:
        break

arr = np.delete(arr, indexes, axis=0)
arr = np.flip(arr.reshape(arr.shape[0] * P))

Answer 1

Есть функция numpy, которая делает почти то, что вы хотите np.trim_zerosМы можем использовать это:

import numpy as np

def trim_mod(a, m=8):
    t = np.trim_zeros(a, 'b')
    return a[:len(a)-(len(a)-len(t))//m*m]

def test(a, t, m=8):
    assert (len(a) - len(t)) % m == 0
    assert len(t) < m or np.any(t[-m:])
    assert not np.any(a[len(t):])

for _ in range(1000):
    a = (np.random.random(np.random.randint(10, 100000))<0.002).astype(int)
    m = np.random.randint(4, 20)
    t = trim_mod(a, m)
    test(a, t, m)

print("Looks correct")

Отпечатки:

Looks correct

По-видимому, линейно масштабируется в количестве конечных нулей:

Но чувствует себя довольно медленно в абсолютном выражении (единицы измерения - мс на пробу), поэтому, возможно, np.trim_zeros - это просто цикл Python.

Код для рисунка:

from timeit import timeit

A = (np.random.random(1000000)<0.02).astype(int)
m = 8
T = []
for last in range(1, 1000, 9):
    A[-last:] = 0
    A[-last] = 1
    T.append(timeit(lambda: trim_mod(A, m), number=100)*10)

import pylab
pylab.plot(range(1, 1000, 9), T)
pylab.show()

Answer 2

Низкоуровневый подход:

import numba
@numba.njit
def trim8(a):
    n=a.size-1
    while n>=0 and a[n]==0 : n-=1
    c= (n//8+1)*8
    return a[:c]

Некоторые тесты:

In [194]: A[-1]=1  # best case

In [196]: %timeit trim_mod(A,8)
5.7 µs ± 323 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [197]: %timeit trim8(A)
714 ns ± 33.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [198]: %timeit A[:(A.size - np.argmax(A[::-1]) // 8) * 8]
4.83 ms ± 479 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [202]: A[:]=0 #worst case

In [203]: %timeit trim_mod(A,8)
2.5 s ± 49.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [204]: %timeit trim8(A)
1.14 ms ± 71.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [205]: %timeit A[:(A.size - np.argmax(A[::-1]) // 8) * 8]
5.5 ms ± 950 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Он имеет механизм короткого замыкания, такой как trim_zeros, но намного быстрее.

Answer 3

Вы можете сделать это, не выделяя больше места, используя представления и np.argmax, чтобы получить последний ненулевой элемент:

index = arr.size - np.argmax(arr[::-1])

Округление до ближайшего кратного восьми легко:

index = np.ceil(index / 8) * 8

Теперь отрубите все остальное:

arr = arr[:index]

Или в виде одной строки:

arr = arr[:(arr.size - np.argmax(arr[::-1])) / 8) * 8]

Эта версия O(n) по времени иO(1) в пространстве, потому что он использует одни и те же буферы для всего (включая вывод).

Это дает дополнительное преимущество, заключающееся в том, что он будет работать правильно, даже если нет завершающих нулей.Использование argmax предполагает, что все элементы одинаковы.Если это не так, вам нужно сначала вычислить маску, например, с помощью arr.astype(bool).

Если вы хотите использовать свой оригинальный подход, вы можете также векторизовать его, хотя будет немного большенакладные расходы:

view = arr.reshape(-1, 8)
mask = view.any(axis = 1)
index = view.shape[0] - np.argmax(mask[::-1])
arr = arr[:index * 8]