Подсчет значений в перекрывающихся скользящих окнах в python

Question

Учитывая массив a из отсортированных значений и массив диапазонов bins, какой самый эффективный способ подсчитать, сколько значений в a попадает в каждый диапазон , rng, в bins?

В настоящее время я делаю следующее:

def sliding_count(a, end, window, start=0, step=1):
    bins = [(x, x + window) for x in range(start, (end + 1) - window, step)]
    counts = np.zeros(len(bins))
    for i, rng in enumerate(bins):
        count = len(a[np.where(np.logical_and(a>=rng[0], a<=rng[1]))])
        counts[i] = count
    return counts

a = np.array([1, 5, 8, 11, 14, 19])
end = 20
window = 10
sliding_count(a, end, window)

, который возвращает ожидаемый массив

array([3., 4., 3., 3., 4., 4., 3., 3., 3., 3., 3.])

Но я чувствую, что должен быть более эффективный способ сделать это?

Answer 1

import numpy as np

def alt(a, end, window, start=0, step=1):
    bin_starts = np.arange(start, end+1-window, step)
    bin_ends = bin_starts + window
    last_index = np.searchsorted(a, bin_ends, side='right')
    first_index = np.searchsorted(a, bin_starts, side='left')
    return  last_index - first_index

def sliding_count(a, end, window, start=0, step=1):
    bins = [(x, x + window) for x in range(start, (end + 1) - window, step)]
    counts = np.zeros(len(bins))
    for i, rng in enumerate(bins):
        count = len(a[np.where(np.logical_and(a>=rng[0], a<=rng[1]))])
        counts[i] = count
    return counts

a = np.array([1, 5, 8, 11, 14, 19])
end = 20
window = 10

print(sliding_count(a, end, window))
# [3. 4. 3. 3. 4. 4. 3. 3. 3. 3. 3.]

print(alt(a, end, window))
# [3 4 3 3 4 4 3 3 3 3 3]

---

Как работает alt:

Генерация начальных и конечных значений бинов:

In [73]: bin_starts = np.arange(start, end+1-window, step); bin_starts
Out[73]: array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10])

In [74]: bin_ends = bin_starts + window; bin_ends
Out[74]: array([10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20])

Поскольку a находится в отсортированном порядке, вы можете использовать np.searchsorted, чтобы найти первый и последний индекс в bin_starts и bin_ends, где подходит каждое значение в a:

In [75]: last_index = np.searchsorted(a, bin_ends, side='right'); last_index
Out[75]: array([3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6])

In [76]: first_index = np.searchsorted(a, bin_starts, side='left'); first_index
Out[76]: array([0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3])

count - это просто разница в индексах:

In [77]: last_index - first_index
Out[77]: array([3, 4, 3, 3, 4, 4, 3, 3, 3, 3, 3])

---

Вот perfplot , сравнивающий производительность alt с sliding_count как функцию длины a:

import perfplot

def make_array(N):
    a = np.random.randint(10, size=N)
    a = a.cumsum()
    return a

def using_sliding(a):
    return sliding_count(a, end, window)

def using_alt(a):
    return alt(a, end, window)

perfplot.show(
    setup=make_array,
    kernels=[using_sliding, using_alt],
    n_range=[2**k for k in range(22)],
    logx=True,
    logy=True,
    xlabel='len(a)')

Perfplot также проверяет, что значение, возвращаемое using_sliding, равно значению, возвращенному using_alt.

Идея Мэтта Тиммерманса , " вычитать position_in_a из числа для этого бункера " вызвала это решение.

Answer 2

Как то так (?):

def sliding_count(a, nx0, nx1, window):
    bin0 = np.arange(nx0,nx1,1)
    bin1 = bin0 + window 
    count = np.zeros((nx1-nx0), dtype=int)

    for j in range(nx1-nx0):
        count[j] = np.sum(a<=bin1[j]) - np.sum(a<bin0[j])
    return count

#---- main ---------------  
nx0, nx1, window = 0, 11, 10
a = np.array([1, 5, 8, 11, 14, 19])
sliding_count(a, nx0, nx1, window)

array([3, 4, 3, 3, 4, 4, 3, 3, 3, 3, 3])

Я не проверял код для nx0> 0 и step> 1 in bin0 = np.arange (nx0, nx1,1) . Поэтому длина цикла for должна быть изменена для таких случаев.

Answer 3

Количество элементов в корзине b - это количество элементов <= b.end минус количество элементов < b.start.

Таким образом, вы можете создать starts массив корзин, отсортированных по началу, и ends массив корзин, отсортированных по концу. Затем пройдитесь по всем 3 массивам в шаге. Когда вы проходите мимо каждого x в a, проходите мимо стартов с x < b.start и вычитаете position_in_a из числа для этого бина. Затем продвиньтесь до конца с помощью x <= b.end и и добавьте position_in_a к счету для этого бина.

Общая сложность составляет O (N log N), где преобладает сортировка начального и конечного массивов. Пройдя по 3 массивам и отрегулировав количество, вы получите O (N).

В вашем коде вы генерируете массив уже отсортированных бинов, так что если вы можете сделать это, то можете пропустить этап сортировки, и общая сложность равна O (a.length + bin_count). Я бы не стал даже создавать этот массив, поскольку вы можете легко рассчитать начальное и конечное значения из индекса.