webentwicklung-frage-antwort-db.com.de

Ermitteln Sie die kumulative Anzahl pro 2d-Array

Ich habe allgemeine Daten, z. Saiten:

np.random.seed(343)

arr = np.sort(np.random.randint(5, size=(10, 10)), axis=1).astype(str)
print (arr)
[['0' '1' '1' '2' '2' '3' '3' '4' '4' '4']
 ['1' '2' '2' '2' '3' '3' '3' '4' '4' '4']
 ['0' '2' '2' '2' '2' '3' '3' '4' '4' '4']
 ['0' '1' '2' '2' '3' '3' '3' '4' '4' '4']
 ['0' '1' '1' '1' '2' '2' '2' '2' '4' '4']
 ['0' '0' '1' '1' '2' '3' '3' '3' '4' '4']
 ['0' '0' '2' '2' '2' '2' '2' '2' '3' '4']
 ['0' '0' '1' '1' '1' '2' '2' '2' '3' '3']
 ['0' '1' '1' '2' '2' '2' '3' '4' '4' '4']
 ['0' '1' '1' '2' '2' '2' '2' '2' '4' '4']]

Ich muss zählen mit reset wenn die Differenz zum Zähler der kumulierten Werte, also Pandas verwendet wird.

Erstellen Sie zunächst DataFrame:

df = pd.DataFrame(arr)
print (df)
   0  1  2  3  4  5  6  7  8  9
0  0  1  1  2  2  3  3  4  4  4
1  1  2  2  2  3  3  3  4  4  4
2  0  2  2  2  2  3  3  4  4  4
3  0  1  2  2  3  3  3  4  4  4
4  0  1  1  1  2  2  2  2  4  4
5  0  0  1  1  2  3  3  3  4  4
6  0  0  2  2  2  2  2  2  3  4
7  0  0  1  1  1  2  2  2  3  3
8  0  1  1  2  2  2  3  4  4  4
9  0  1  1  2  2  2  2  2  4  4

Wie es für eine Kolonne funktioniert:

Vergleichen Sie zuerst die verschobenen Daten und addieren Sie die kumulierte Summe:

a = (df[0] != df[0].shift()).cumsum()
print (a)
0    1
1    2
2    3
3    3
4    3
5    3
6    3
7    3
8    3
9    3
Name: 0, dtype: int32

Und dann rufen Sie GroupBy.cumcount an:

b = a.groupby(a).cumcount() + 1
print (b)
0    1
1    1
2    1
3    2
4    3
5    4
6    5
7    6
8    7
9    8
dtype: int64

Wenn Sie eine Lösung für alle Spalten anwenden möchten, verwenden Sie apply:

print (df.apply(lambda x: x.groupby((x != x.shift()).cumsum()).cumcount() + 1))
   0  1  2  3  4  5  6  7  8  9
0  1  1  1  1  1  1  1  1  1  1
1  1  1  1  2  1  2  2  2  2  2
2  1  2  2  3  1  3  3  3  3  3
3  2  1  3  4  1  4  4  4  4  4
4  3  2  1  1  1  1  1  1  5  5
5  4  1  2  2  2  1  1  1  6  6
6  5  2  1  1  3  1  1  1  1  7
7  6  3  1  1  1  2  2  2  2  1
8  7  1  2  1  1  3  1  1  1  1
9  8  2  3  2  2  4  1  1  2  2

Aber es ist langsam, weil große Datenmengen. Ist es möglich, eine schnelle numpy-Lösung zu erstellen?

Ich finde solutions , das nur für 1d-Arrays funktioniert.

7
jezrael

Und die numba-Lösung. Bei solch einem kniffligen Problem gewinnt es immer, hier um einen Faktor 7 gegen Numpy, da nur ein Durchlauf auf res erfolgt.

from numba import njit 
@njit
def thefunc(arrc):
    m,n=arrc.shape
    res=np.empty((m+1,n),np.uint32)
    res[0]=1
    for i in range(1,m+1):
        for j in range(n):
            if arrc[i-1,j]:
                res[i,j]=res[i-1,j]+1
            else : res[i,j]=1
    return res 

def numbering(arr):return thefunc(arr[1:]==arr[:-1])

Ich muss arr[1:]==arr[:-1] externalisieren, da numba keine Zeichenketten unterstützt.

In [75]: %timeit numbering(arr)
13.7 µs ± 373 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [76]: %timeit grp_range_2dcol(arr)
111 µs ± 18.3 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Bei größeren Arrays (100 000 Zeilen x 100 Cols) ist die Lücke nicht so groß:

In [168]: %timeit a=grp_range_2dcol(arr)
1.54 s ± 11.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [169]: %timeit a=numbering(arr)
625 ms ± 43.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Wenn arr in 'S8' konvertiert werden kann, können wir viel Zeit gewinnen:

In [398]: %timeit arr[1:]==arr[:-1]
584 ms ± 12.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [399]: %timeit arr.view(np.uint64)[1:]==arr.view(np.uint64)[:-1]
196 ms ± 18.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
6
B. M.

Grund Idee

Betrachten wir den generischen Fall, in dem wir diese kumulative Zählung durchführen oder wenn Sie sie als Bereiche betrachten, können wir sie als "Gruppierte Bereiche" bezeichnen.

Nun beginnt die Idee einfach: Vergleichen Sie einmalige Scheiben entlang der jeweiligen Achse, um nach Ungleichheiten zu suchen. Füllen Sie am Anfang jeder Zeile/Spalte mit True (abhängig von der Zählachse). 

Dann wird es kompliziert - Richten Sie ein ID-Array ein, mit dem Ziel, ein abschließendes Cumum zu erstellen, dessen Ausgabe in der abgeflachten Reihenfolge gewünscht wäre. Das Setup beginnt also mit der Initialisierung eines 1s-Arrays mit derselben Form wie das Eingangsarray. Versetzen Sie das ID-Array bei jeder eingegebenen Gruppe mit den vorherigen Gruppenlängen. Folgen Sie dem Code (sollte mehr Einblick geben), wie wir dies für jede Zeile tun würden.

def grp_range_2drow(a, start=0):
    # Get grouped ranges along each row with resetting at places where
    # consecutive elements differ

    # Input(s) : a is 2D input array

    # Store shape info
    m,n = a.shape

    # Compare one-off slices for each row and pad with True's at starts
    # Those True's indicate start of each group
    p = np.ones((m,1),dtype=bool)
    a1 = np.concatenate((p, a[:,:-1] != a[:,1:]),axis=1)

    # Get indices of group starts in flattened version
    d = np.flatnonzero(a1)

    # Setup ID array to be cumsumed finally for desired o/p 
    # Assign into starts with previous group lengths. 
    # Thus, when cumsumed on flattened version would give us flattened desired
    # output. Finally reshape back to 2D  
    c = np.ones(m*n,dtype=int)
    c[d[1:]] = d[:-1]-d[1:]+1
    c[0] = start
    return c.cumsum().reshape(m,n)

Wir würden dies erweitern, um einen generischen Fall von Zeilen und Spalten zu lösen. Für den Spaltenfall würden wir einfach transponieren, zu früheren Zeilenlösungen führen und schließlich zurücksetzen, wie so -

def grp_range_2d(a, start=0, axis=1):
    # Get grouped ranges along specified axis with resetting at places where
    # consecutive elements differ

    # Input(s) : a is 2D input array

    if axis not in [0,1]:
        raise Exception("Invalid axis")

    if axis==1:
        return grp_range_2drow(a, start=start)
    else:
        return grp_range_2drow(a.T, start=start).T

Probelauf

Betrachten wir einen Beispiellauf, als würden gruppierte Bereiche entlang jeder Spalte gefunden, wobei jede Gruppe mit 1 beginnt.

In [330]: np.random.seed(0)

In [331]: a = np.random.randint(1,3,(10,10))

In [333]: a
Out[333]: 
array([[1, 2, 2, 1, 2, 2, 2, 2, 2, 2],
       [2, 1, 1, 2, 1, 1, 1, 1, 1, 2],
       [1, 2, 2, 1, 1, 2, 2, 2, 2, 1],
       [2, 1, 2, 1, 2, 2, 1, 2, 2, 1],
       [1, 2, 1, 2, 2, 2, 2, 2, 1, 2],
       [1, 2, 2, 2, 2, 1, 2, 1, 1, 2],
       [2, 1, 2, 1, 2, 1, 1, 1, 1, 1],
       [2, 2, 1, 1, 1, 2, 2, 1, 2, 1],
       [1, 2, 1, 2, 2, 2, 2, 2, 2, 1],
       [2, 2, 1, 1, 2, 1, 1, 2, 2, 1]])

In [334]: grp_range_2d(a, start=1, axis=0)
Out[334]: 
array([[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1, 1, 1, 1, 1, 2],
       [1, 1, 1, 1, 2, 1, 1, 1, 1, 1],
       [1, 1, 2, 2, 1, 2, 1, 2, 2, 2],
       [1, 1, 1, 1, 2, 3, 1, 3, 1, 1],
       [2, 2, 1, 2, 3, 1, 2, 1, 2, 2],
       [1, 1, 2, 1, 4, 2, 1, 2, 3, 1],
       [2, 1, 1, 2, 1, 1, 1, 3, 1, 2],
       [1, 2, 2, 1, 1, 2, 2, 1, 2, 3],
       [1, 3, 3, 1, 2, 1, 1, 2, 3, 4]])

Um unseren Fall für die Datenframe-Eingabe und -Ausgabe zu lösen, wäre es also -

out = grp_range_2d(df.values, start=1,axis=0)
pd.DataFrame(out,columns=df.columns,index=df.index)
8
Divakar

Die Methode von Divakar column ist ziemlich viel schneller, obwohl es wahrscheinlich einen vollständig vektorisierten Weg gibt.

#function of Divakar
def grp_range(a):
    idx = a.cumsum()
    id_arr = np.ones(idx[-1],dtype=int)
    id_arr[0] = 0
    id_arr[idx[:-1]] = -a[:-1]+1
    return id_arr.cumsum()

#create the equivalent of (df != df.shift()).cumsum() but faster
arr_sum = np.vstack([np.ones(10), np.cumsum((arr != np.roll(arr, 1, 0))[1:],0)+1])

#use grp_range column wise on arr_sum
arr_result = np.array([grp_range(np.unique(arr_sum[:,i],return_counts=1)[1]) 
                       for i in range(arr_sum.shape[1])]).T+1

Um die Gleichheit zu prüfen:

# of the cumsum
print (((df != df.shift()).cumsum() == 
         np.vstack([np.ones(10), np.cumsum((arr != np.roll(arr, 1, 0))[1:],0)+1]))
         .all().all())
#True

print ((df.apply(lambda x: x.groupby((x != x.shift()).cumsum()).cumcount() + 1) ==
        np.array([grp_range(np.unique(arr_sum[:,i],return_counts=1)[1]) 
                  for i in range(arr_sum.shape[1])]).T+1)
        .all().all())
#True

und die Geschwindigkeit:

%timeit df.apply(lambda x: x.groupby((x != x.shift()).cumsum()).cumcount() + 1)
#19.4 ms ± 2.97 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%%timeit
arr_sum = np.vstack([np.ones(10), np.cumsum((arr != np.roll(arr, 1, 0))[1:],0)+1])
arr_res = np.array([grp_range(np.unique(arr_sum[:,i],return_counts=1)[1]) 
                    for i in range(arr_sum.shape[1])]).T+1

#562 µs ± 82.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

BEARBEITEN: Mit Numpy können Sie auch np.maximum.accumulate mit np.arange verwenden.

def accumulate(arr):
    n,m = arr.shape
    arr_arange = np.arange(1,n+1)[:,np.newaxis]
    return np.concatenate([ np.ones((1,m)), 
                           arr_arange[1:] - np.maximum.accumulate(arr_arange[:-1]*
                      (arr[:-1,:] != arr[1:,:]))],axis=0)

EinigeTIMING

arr_100 = np.sort(np.random.randint(50, size=(100000, 100)), axis=1).astype(str)

Lösung mit np.maximum.accumulate

%timeit accumulate(arr_100)
#520 ms ± 72 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Lösung von Divakar

%timeit grp_range_2drow(arr_100.T, start=1).T
#1.15 s ± 64.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Lösung mit Numba von B. M.

%timeit numbering(arr_100)
#228 ms ± 31.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
2
Ben.T