Найти последовательные повторы Specifi c Длина в NumPy

Question

Скажите, что у меня есть массив NumPy:

a = np.array([0, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9, 9, 10, 11, 12, 13, 13, 13, 14, 15])

И у меня есть длина m = 2, которую пользователь указывает, чтобы увидеть, есть ли какие-либо повторы этой длины в пределах временного ряда , В этом случае повторы длины m = 2:

[2, 2]
[5, 5]
[9, 9]
[9, 9]
[13, 13]

И пользователь может изменить это значение на m = 3, а повторы длины m = 3:

[9, 9, 9]
[13, 13, 13]

Мне нужна функция, которая либо возвращает индекс, где найдено повторение, либо None. Так, для m = 3 функция вернет следующий NumPy массив начальных индексов:

[11, 17]

А для m = 4 функция вернет None. Какой самый простой и быстрый способ выполнить sh это?

Обновление Обратите внимание, что массив не нужно сортировать, и мы не интересует результат после сортировки. Нам нужен только результат из несортированного массива. Ваш результат для m = 2 должен быть таким же для этого массива:

b = np.array([0, 11, 2, 2, 3, 40, 5, 5, 16, 7, 80, 9, 9, 9, 1, 11, 12, 13, 13, 13, 4, 5])

Answer 1

Подход № 1

Мы могли бы использовать 1D convolution для векторизованного решения -

def consec_repeat_starts(a, n):
    N = n-1
    m = a[:-1]==a[1:]
    return np.flatnonzero(np.convolve(m,np.ones(N, dtype=int))==N)-N+1

Пробные прогоны -

In [286]: a
Out[286]: 
array([ 0,  1,  2,  2,  3,  4,  5,  5,  6,  7,  8,  9,  9,  9, 10, 11, 12,
       13, 13, 13, 14, 15])

In [287]: consec_repeat_starts(a, 2)
Out[287]: array([ 2,  6, 11, 12, 17, 18])

In [288]: consec_repeat_starts(a, 3)
Out[288]: array([11, 17])

In [289]: consec_repeat_starts(a, 4)
Out[289]: array([], dtype=int64)

Подход № 2

Мы также могли бы использовать binary-erosion -

from scipy.ndimage.morphology import binary_erosion

def consec_repeat_starts_v2(a, n):
    N = n-1
    m = a[:-1]==a[1:]
    return np.flatnonzero(binary_erosion(m,[1]*N))-(N//2)

Answer 2

a numba njit'ed опция для полноты:

import numpy as np
import numba as nb

@nb.njit
def find_repeats(arr, n):
    indices = []
    current = arr[0]
    count = 0
    for idx, item in enumerate(arr[1:]):
        if item == current:
            count += 1
            if count >= n-1:
                indices.append(idx)
        else:
            count = 0
            current = item
    return indices if indices else None

b = np.array([0, 11, 2, 2, 3, 40, 5, 5, 16, 7, 80, 9, 9, 9, 1, 11, 12, 13, 13, 13, 4, 5])

print(find_repeats(b, 2))
# [2, 6, 11, 12, 17, 18]

print(find_repeats(b, 3))
# [12, 18]

Менее элегантный и O(n), но быстрый - simple_benchmark сравнение с Функции Дивакара :

Answer 3

Мы также можем использовать рекурсивную функцию:

def recursive_repeat(arr, k):
    if k == 1:
        return np.flatnonzero(arr)
    else:
        new_arr = np.zeros(arr.size - 1)
        mask = arr[1:] == arr[:-1]
        new_arr[mask] = arr[:-1][mask]
        return recursive_repeat(new_arr, k-1)


recursive_repeat(a, 2)
Out[]: array([ 2,  6, 11, 12, 17, 18], dtype=int64)

recursive_repeat(a, 3)
Out[]: array([11, 17], dtype=int64)

Answer 4

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

import numpy as np

nums = np.array([11, 0, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9, 9, 10, 11, 12, 13, 13, 13, 14, 15])

m = 3

equals = []

for ii in range(len(nums)):
    if ii >= m:
        sliced = nums[ii-m:ii]
        if np.unique(sliced).size == 1:
             equals.append(sliced)

print(np.array(equals))

Это даст вывод для m = 2:

[[ 2  2]
[ 5  5]
[ 9  9]
[ 9  9]
[13 13]
[13 13]]

Это даст выход для m = 3:

[[ 9  9  9]
[13 13 13]]

Answer 5

Я нашел этот, очень похожий на другой, но он должен работать. Это работает, только если массив отсортирован

def find(a,m):
    index=[]
    prev=0
    n =1
    for i in range(1,len(a)):
        if a[prev] == a[i]:
            n+=1
            if(m==n):
                index.append(i-m+1)
                n=1
        else:
            n=1
        prev=i
    return index if len(index)>0 else None
find(a,3)

Answer 6

Я придумала это решение, возможно, оно не самое чистое.

Я использую обычный массив вместо numpy, но он должен работать так же.

a = [0, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9, 9, 10, 11, 12, 13, 13, 13, 14, 15]
m = 2


def index_repeated_length( list, length ) :
    previous = None
    count = 1
    for i, element in enumerate(list) :
        if element == previous :
            count += 1
        else :
            previous = element
            count = 1

        if count >= length :
            yield i - length + 1

print( list( index_repeated_length(a, m) ) )

Вывод:

[2, 6, 11, 12, 17, 18]

Так как он никогда не сортируется, вы должны выполнять его итерацию, поэтому сложность должна быть линейной O (n)