numpy 1D array: маскировать элементы, которые повторяются более n раз

18

учитывая массив целых чисел, таких как

[1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5]

Мне нужно замаскировать элементы, которые повторяются больше, чем Nраз. Чтобы уточнить: основная цель состоит в том, чтобы получить массив логических масок, чтобы использовать его позже для вычисления биннинга.

Я придумал довольно сложное решение

import numpy as np

bins = np.array([1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5])

N = 3
splits = np.split(bins, np.where(np.diff(bins) != 0)[0]+1)
mask = []
for s in splits:
    if s.shape[0] <= N:
        mask.append(np.ones(s.shape[0]).astype(np.bool_))
    else:
        mask.append(np.append(np.ones(N), np.zeros(s.shape[0]-N)).astype(np.bool_)) 

mask = np.concatenate(mask)

например,

bins[mask]
Out[90]: array([1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5])

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

РЕДАКТИРОВАТЬ, № 2

Большое спасибо за ответы! Вот тонкая версия эталонного сюжета MSeifert. Спасибо за указание на меня simple_benchmark. Показаны только 4 самых быстрых варианта: введите описание изображения здесь

Вывод

Идея, предложенная Флорианом Н и модифицированная Полом Панцером, кажется отличным способом решения этой проблемы, поскольку она довольно прямолинейна и numpyединственна. Однако, если вы в порядке с использованием numba, решение MSeifert превосходит другие.

Я решил принять ответ MSeifert в качестве решения, так как это более общий ответ: он правильно обрабатывает произвольные массивы с (неуникальными) блоками последовательных повторяющихся элементов. В случае numba, если нет, ответ Divakar также стоит посмотреть!

MrFuppes
источник
1
Гарантируется ли, что вход будет отсортирован?
user2357112 поддерживает Monica
1
в моем конкретном случае да. в общем, я бы сказал, что было бы хорошо рассмотреть случай несортированного ввода (и неуникальных блоков повторяющихся элементов).
MrFuppes

Ответы:

4

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

import numpy as np
import numba as nb

@nb.njit
def mask_more_n(arr, n):
    mask = np.ones(arr.shape, np.bool_)

    current = arr[0]
    count = 0
    for idx, item in enumerate(arr):
        if item == current:
            count += 1
        else:
            current = item
            count = 1
        mask[idx] = count <= n
    return mask

Например:

>>> bins = np.array([1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5])
>>> bins[mask_more_n(bins, 3)]
array([1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5])
>>> bins[mask_more_n(bins, 2)]
array([1, 1, 2, 2, 3, 3, 4, 4, 5, 5])

Представление:

Использование simple_benchmark- однако я не включил все подходы. Это логарифмическая шкала:

введите описание изображения здесь

Кажется, что решение numba не может превзойти решение от Paul Panzer, которое кажется немного быстрее для больших массивов (и не требует дополнительной зависимости).

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

import numpy as np
import numba as nb
from simple_benchmark import BenchmarkBuilder, MultiArgument

b = BenchmarkBuilder()

bins = np.array([1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5])

@nb.njit
def mask_more_n(arr, n):
    mask = np.ones(arr.shape, np.bool_)

    current = arr[0]
    count = 0
    for idx, item in enumerate(arr):
        if item == current:
            count += 1
        else:
            current = item
            count = 1
        mask[idx] = count <= n
    return mask

@b.add_function(warmups=True)
def MSeifert(arr, n):
    return mask_more_n(arr, n)

from scipy.ndimage.morphology import binary_dilation

@b.add_function()
def Divakar_1(a, N):
    k = np.ones(N,dtype=bool)
    m = np.r_[True,a[:-1]!=a[1:]]
    return a[binary_dilation(m,k,origin=-(N//2))]

@b.add_function()
def Divakar_2(a, N):
    k = np.ones(N,dtype=bool)
    return a[binary_dilation(np.ediff1d(a,to_begin=a[0])!=0,k,origin=-(N//2))]

@b.add_function()
def Divakar_3(a, N):
    m = np.r_[True,a[:-1]!=a[1:],True]
    idx = np.flatnonzero(m)
    c = np.diff(idx)
    return np.repeat(a[idx[:-1]],np.minimum(c,N))

from skimage.util import view_as_windows

@b.add_function()
def Divakar_4(a, N):
    m = np.r_[True,a[:-1]!=a[1:]]
    w = view_as_windows(m,N)
    idx = np.flatnonzero(m)
    v = idx<len(w)
    w[idx[v]] = 1
    if v.all()==0:
        m[idx[v.argmin()]:] = 1
    return a[m]

@b.add_function()
def Divakar_5(a, N):
    m = np.r_[True,a[:-1]!=a[1:]]
    w = view_as_windows(m,N)
    last_idx = len(a)-m[::-1].argmax()-1
    w[m[:-N+1]] = 1
    m[last_idx:last_idx+N] = 1
    return a[m]

@b.add_function()
def PaulPanzer(a,N):
    mask = np.empty(a.size,bool)
    mask[:N] = True
    np.not_equal(a[N:],a[:-N],out=mask[N:])
    return mask

import random

@b.add_arguments('array size')
def argument_provider():
    for exp in range(2, 20):
        size = 2**exp
        yield size, MultiArgument([np.array([random.randint(0, 5) for _ in range(size)]), 3])

r = b.run()
import matplotlib.pyplot as plt

plt.figure(figsize=[10, 8])
r.plot()
MSeifert
источник
«Кажется, что решение numba не может превзойти решение от Пола Панцера», возможно, оно быстрее для приличного диапазона размеров. И это мощнее. Я не мог заставить мою (ну, @ FlorianH's) работать для неуникальных значений блоков, не делая это намного медленнее. Интересно, что даже реплицируя метод Florians с pythran (который обычно работает аналогично numba), я не смог сравниться с простой реализацией для больших массивов. Pythran не нравится outаргумент (или, возможно, функциональная форма оператора), поэтому я не смог сохранить эту копию. Кстати мне очень нравится simple_benchmark.
Пол Панцер
отличный намек там, чтобы использовать simple_benchmark! спасибо за это и спасибо, конечно, за ответ. Так как я использую и numbaдля других вещей, я склонен также использовать это здесь и сделать это решением. между камнем и наковальней ...
MrFuppes
7

Отказ от ответственности: это только более надежная реализация идеи @ FlorianH:

def f(a,N):
    mask = np.empty(a.size,bool)
    mask[:N] = True
    np.not_equal(a[N:],a[:-N],out=mask[N:])
    return mask

Для больших массивов это имеет огромное значение:

a = np.arange(1000).repeat(np.random.randint(0,10,1000))
N = 3

print(timeit(lambda:f(a,N),number=1000)*1000,"us")
# 5.443050000394578 us

# compare to
print(timeit(lambda:[True for _ in range(N)] + list(bins[:-N] != bins[N:]),number=1000)*1000,"us")
# 76.18969900067896 us
Пол Панцер
источник
Я не думаю, что это работает правильно для произвольных массивов: например, с [1,1,1,1,2,2,1,1,2,2].
MSeifert
@MSeifert Из примера OP я предположил, что такого рода вещи не могут произойти, но вы правы в том, что действительный код OP может обработать ваш пример. Ну, наверное, только ОП может сказать.
Пол Панцер
как я ответил на комментарий user2357112, в моем конкретном случае вход сортируется, и блоки последовательных повторяющихся элементов являются уникальными. Однако, с более общей точки зрения, было бы очень полезно, если бы можно было обрабатывать произвольные массивы.
MrFuppes
4

Подход № 1: Вот векторизованный способ -

from scipy.ndimage.morphology import binary_dilation

def keep_N_per_group(a, N):
    k = np.ones(N,dtype=bool)
    m = np.r_[True,a[:-1]!=a[1:]]
    return a[binary_dilation(m,k,origin=-(N//2))]

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

In [42]: a
Out[42]: array([1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5])

In [43]: keep_N_per_group(a, N=3)
Out[43]: array([1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5])

Подход № 2: немного более компактная версия -

def keep_N_per_group_v2(a, N):
    k = np.ones(N,dtype=bool)
    return a[binary_dilation(np.ediff1d(a,to_begin=a[0])!=0,k,origin=-(N//2))]

Подход № 3: Использование сгруппированных подсчетов и np.repeat(хотя не даст нам маску) -

def keep_N_per_group_v3(a, N):
    m = np.r_[True,a[:-1]!=a[1:],True]
    idx = np.flatnonzero(m)
    c = np.diff(idx)
    return np.repeat(a[idx[:-1]],np.minimum(c,N))

Подход № 4: С помощью view-basedметода -

from skimage.util import view_as_windows

def keep_N_per_group_v4(a, N):
    m = np.r_[True,a[:-1]!=a[1:]]
    w = view_as_windows(m,N)
    idx = np.flatnonzero(m)
    v = idx<len(w)
    w[idx[v]] = 1
    if v.all()==0:
        m[idx[v.argmin()]:] = 1
    return a[m]

Подход № 5. С помощью view-basedметода без индексов из flatnonzero-

def keep_N_per_group_v5(a, N):
    m = np.r_[True,a[:-1]!=a[1:]]
    w = view_as_windows(m,N)
    last_idx = len(a)-m[::-1].argmax()-1
    w[m[:-N+1]] = 1
    m[last_idx:last_idx+N] = 1
    return a[m]
Divakar
источник
2

Вы можете сделать это с помощью индексации. Для любого N код будет:

N = 3
bins = np.array([1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5,6])

mask = [True for _ in range(N)] + list(bins[:-N] != bins[N:])
bins[mask]

вывод:

array([1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6]
Флориан Н
источник
очень нравится, потому что это просто! должен быть довольно быстрым, проверим с некоторыми timeitпрогонами.
MrFuppes
1

Гораздо приятнее было бы использовать numpys unique()-функцию. Вы получите уникальные записи в вашем массиве, а также количество их появления:

bins = np.array([1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5])
N = 3

unique, index,count = np.unique(bins, return_index=True, return_counts=True)
mask = np.full(bins.shape, True, dtype=bool)
for i,c in zip(index,count):
    if c>N:
        mask[i+N:i+c] = False

bins[mask]

вывод:

array([1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5])
Саймон Финк
источник
1

Вы можете использовать цикл while, который проверяет, равен ли элемент массива N позициям назад текущему. Обратите внимание, что это решение предполагает, что массив упорядочен.

import numpy as np

bins = [1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5]
N = 3
counter = N

while counter < len(bins):
    drop_condition = (bins[counter] == bins[counter - N])
    if drop_condition:
        bins = np.delete(bins, counter)
    else:
        # move on to next element
        counter += 1
dodgytricycle
источник
Возможно, вы захотите изменить len(question)наlen(bins)
Florian H
извините, если мой вопрос там неясен; Я не собираюсь удалять элементы, мне просто нужна маска, которую я смогу использовать позже (например, маскирование зависимой переменной, чтобы получить равное количество выборок на одну ячейку).
MrFuppes
0

Вы можете использовать grouby общих элементов группы и список фильтров, которые больше чем N .

import numpy as np
from itertools import groupby, chain

def ifElse(condition, exec1, exec2):

    if condition : return exec1 
    else         : return exec2


def solve(bins, N = None):

    xss = groupby(bins)
    xss = map(lambda xs : list(xs[1]), xss)
    xss = map(lambda xs : ifElse(len(xs) > N, xs[:N], xs), xss)
    xs  = chain.from_iterable(xss)
    return list(xs)

bins = np.array([1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5])
solve(bins, N = 3)
Youngseok Jeon
источник
0

Решение

Вы могли бы использовать numpy.unique. Переменная final_maskможет использоваться для извлечения элементов traget из массива bins.

import numpy as np

bins = np.array([1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5])
repeat_max = 3

unique, counts = np.unique(bins, return_counts=True)
mod_counts = np.array([x if x<=repeat_max else repeat_max for x in counts])
mask = np.arange(bins.size)
#final_values = np.hstack([bins[bins==value][:count] for value, count in zip(unique, mod_counts)])
final_mask = np.hstack([mask[bins==value][:count] for value, count in zip(unique, mod_counts)])
bins[final_mask]

Выход :

array([1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5])
CypherX
источник
для этого потребуется дополнительный шаг, чтобы получить маску той же формы, что binsи верно?
MrFuppes
Верно: только если вы заинтересованы в получении маски в первую очередь. Если вы хотите, чтобы final_valuesнепосредственно, вы можете раскомментировать единственным комментировала линию в растворе и в этом случае вы можете отказаться три линии: mask = ..., final_mask = ...и bins[final_mask].
CypherX