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!


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

„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

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]

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]

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

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

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)

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

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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.