tablica numpy 1D: maskuje elementy, które powtarzają się więcej niż n razy

18

biorąc pod uwagę tablicę liczb całkowitych takich jak

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

Muszę zamaskować elementy, które powtarzają się więcej niż Nrazy. Wyjaśnienie: głównym celem jest odzyskanie tablicy maski logicznej, aby później użyć jej do obliczeń binningu.

Wymyśliłem dość skomplikowane rozwiązanie

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)

podając np

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

Czy jest na to lepszy sposób?

EDYCJA, # 2

Wielkie dzięki za odpowiedzi! Oto szczupła wersja wykresu porównawczego MSeifert. Dzięki za wskazanie mnie do simple_benchmark. Pokazuje tylko 4 najszybsze opcje: wprowadź opis zdjęcia tutaj

Wniosek

Pomysł zaproponowany przez Floriana H , zmodyfikowany przez Paula Panzera, wydaje się być świetnym sposobem na rozwiązanie tego problemu, ponieważ jest dość prosty i numpytylko. Jeśli jesteś w porządku z użyciem numbajednak rozwiązanie MSeifert za wyprzedza drugiego.

Zdecydowałem się zaakceptować odpowiedź MSeiferta jako rozwiązanie, ponieważ jest to bardziej ogólna odpowiedź: poprawnie obsługuje dowolne tablice z (nieunikalnymi) blokami kolejnych powtarzających się elementów. Na wypadek, gdyby numbabyło to niemożliwe, odpowiedź Divakara również jest warta obejrzenia!

MrFuppes
źródło
1
Czy jest pewne, że dane wejściowe zostaną posortowane?
user2357112 obsługuje Monikę
1
w moim konkretnym przypadku tak. ogólnie powiedziałbym, że dobrze byłoby rozważyć przypadek nieposortowanych danych wejściowych (i nieunikalnych bloków powtarzających się elementów).
MrFuppes

Odpowiedzi:

4

Chcę przedstawić rozwiązanie z użyciem Numby, które powinno być dość łatwe do zrozumienia. Zakładam, że chcesz „zamaskować” kolejne powtarzające się elementy:

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

Na przykład:

>>> 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])

Wydajność:

Korzystanie simple_benchmark- jednak nie uwzględniłem wszystkich podejść. Jest to skala dziennika:

wprowadź opis zdjęcia tutaj

Wygląda na to, że rozwiązanie numba nie jest w stanie pokonać rozwiązania Paula Panzera, który wydaje się być szybszy w przypadku dużych tablic (i nie wymaga dodatkowej zależności).

Jednak oba wydają się przewyższać inne rozwiązania, ale zwracają maskę zamiast „filtrowanej” tablicy.

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
źródło
„Wygląda na to, że rozwiązanie numba nie jest w stanie pokonać rozwiązania Paula Panzera”, zapewne jest szybsze dla przyzwoitego zakresu rozmiarów. I jest silniejszy. Nie mogłem zmusić mojej (cóż, @ FlorianH) do pracy z nietypowymi wartościami bloków bez spowolnienia jej działania. Co ciekawe, nawet replikacja metody Florians za pomocą pythranu (który zwykle działa podobnie do numby) Nie mogłem dopasować implementacji numpy dla dużych tablic. pythran nie lubi outargumentu (a może funkcjonalnej formy operatora), więc nie mogłem zapisać tej kopii. Przy okazji lubię simple_benchmark.
Paul Panzer
świetna wskazówka, do użycia simple_benchmark! dzięki za to i oczywiście za odpowiedź. Ponieważ używam również numbado innych rzeczy, jestem skłonny również użyć go tutaj i uczynić to rozwiązaniem. między skałą a trudnym miejscem ...
MrFuppes
7

Oświadczenie: jest to tylko realizacja pomysłu @ 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

W przypadku większych tablic robi to ogromną różnicę:

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
Paul Panzer
źródło
Nie sądzę, że działa poprawnie dla dowolnych tablic: Na przykład z [1,1,1,1,2,2,1,1,2,2].
MSeifert
@MSeifert Z przykładu OP Zakładałem, że coś takiego nie może się wydarzyć, ale masz rację, że kod OP może obsłużyć twój przykład. Przypuszczam, że tylko OP może to stwierdzić.
Paul Panzer
gdy odpowiedziałem na komentarz użytkownika2357112, w moim konkretnym przypadku dane wejściowe są sortowane, a bloki kolejnych powtarzających się elementów są unikalne. Jednak z bardziej ogólnej perspektywy byłoby bardzo przydatne, gdyby można było obsłużyć dowolne tablice.
MrFuppes
4

Podejście nr 1: Oto wektorowy sposób -

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))]

Przykładowy przebieg -

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])

Podejście nr 2: Trochę bardziej kompaktowa wersja -

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))]

Podejście nr 3: używając zgrupowanych liczników i np.repeat(nie da nam maski) -

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))

Podejście # 4: Przy view-basedmetodzie -

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]

Zbliżać # 5: Przy view-basedmetodzie bez indeksów od 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
źródło
2

Możesz to zrobić za pomocą indeksowania. Dla każdego N kod będzie:

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]

wynik:

array([1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6]
Florian H.
źródło
naprawdę podoba się to ze względu na prostotę! powinien być również dość wydajny, sprawdzi się przy niektórych timeitbiegach.
MrFuppes
1

O wiele ładniejszy sposób byłoby użyć numpy„s unique()-function. Otrzymasz unikalne wpisy w swojej tablicy oraz liczbę wyświetleń:

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]

wynik:

array([1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5])
Simon Fink
źródło
1

Możesz użyć pętli while, która sprawdza, czy element tablicy N pozycji wstecz jest równy bieżącej. Uwaga: to rozwiązanie zakłada, że ​​tablica jest uporządkowana.

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
dodgytrycykl
źródło
Możesz zmienić len(question)nalen(bins)
Florian H
przepraszam, jeśli moje pytanie jest niejasne; Nie chcę usuwać elementów, potrzebuję tylko maski, której będę mógł później użyć (np. Zamaskować zmienną zależną, aby uzyskać taką samą liczbę próbek na bin).
MrFuppes
0

Można użyć grouby do grupy wspólnych elementów i listy filtrów, które są dłuższe niż 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
źródło
0

Rozwiązanie

Możesz użyć numpy.unique. Zmiennej final_maskmożna użyć do wyodrębnienia elementów tragetu z tablicy 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]

Wyjście :

array([1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5])
CypherX
źródło
wymagałoby to dodatkowego kroku, aby uzyskać maskę tego samego kształtu co bins, prawda?
MrFuppes
To prawda: tylko jeśli jesteś zainteresowany zdobyciem maski w pierwszej kolejności. Jeśli chcesz final_valuesbezpośrednio, można odkomentowaniu jedyny skomentował linię w roztworze iw tym przypadku można wyrzucić trzy wiersze: mask = ..., final_mask = ...i bins[final_mask].
CypherX