Zezwól na macierz w miejscu w numpy

27

Chcę zmodyfikować gęstą kwadratową macierz przejścia w miejscu, zmieniając kolejność kilku jej wierszy i kolumn, używając biblioteki numpy Pythona. Matematycznie odpowiada to pomnożeniu macierzy przez macierz permutacji P i pomnożeniu jej przez P ^ -1 = P ^ T, ale nie jest to uzasadnione obliczeniowo rozwiązanie.

W tej chwili ręcznie zmieniam wiersze i kolumny, ale oczekiwałbym, że numpy będzie mieć fajną funkcję f (M, v), gdzie M ma n wierszy i kolumn, a v ma n wpisów, więc f (M, v) aktualizuje M zgodnie z permutacją indeksu v. Może po prostu nie udaje mi się przeszukać Internetu.

Coś takiego może być możliwe przy „zaawansowanym indeksowaniu” Numpy, ale rozumiem, że takie rozwiązanie nie byłoby na miejscu. Również w niektórych prostych sytuacjach może być wystarczające oddzielne śledzenie permutacji indeksu, ale w moim przypadku nie jest to wygodne.

Dodano:
Czasami, gdy ludzie mówią o permutacjach, mają na myśli jedynie próbkowanie permutacji losowych, na przykład jako część procedury uzyskiwania wartości pw statystyce. Lub oznaczają zliczanie lub wyliczanie wszystkich możliwych permutacji. Nie mówię o tych rzeczach.

Dodano:
Matryca jest wystarczająco mała, aby zmieściła się w RAM-ie pulpitu, ale wystarczająco duża, że nie chcę jej bezmyślnie kopiować. Właściwie chciałbym używać macierzy tak dużych, jak to możliwe, ale nie chcę uporać się z niedogodnościami związanymi z niemożnością trzymania ich w pamięci RAM i wykonuję operacje O (N ^ 3) LAPACK na macierzy, które również ograniczyć praktyczny rozmiar matrycy. Obecnie niepotrzebnie kopiuję macierze tak duże, ale mam nadzieję, że można tego łatwo uniknąć w przypadku permutacji.

linear-algebra python numpy

— Żaden
źródło

3

Byłoby dobrze, gdybyś mógł zaktualizować pytanie, aby podać rozmiar swoich matryc. „Gigantyczny” nie oznacza tego samego dla wszystkich ludzi.

— Bill Barth,

2

Masz rację, że zaawansowane (lub tak zwane fantazyjne) indeksowanie tworzy kopię. Ale jeśli zgadzasz się żyć z tym faktem, twój kod ma po prostu M[v]permutować wiersze.

— Daniel Velkov,

@ Daniel: I byłoby M [v,:] [:, v] wykonać całą permutację? Czy byłby to najlepszy sposób na uzyskanie permutacji za pomocą fantazyjnego indeksowania? I czy użyłby 3x pamięci macierzy, w tym rozmiaru oryginalnej macierzy, matrycy permutowanej wiersz + kolumna i macierzy permutowanej wiersz tymczasowy?

— brak

Zgadza się, miałbyś oryginalną matrycę i 2 kopie. Przy okazji, dlaczego musisz jednocześnie permutować zarówno wiersze, jak i kolumny?

— Daniel Velkov,

4

Co zamierzasz zrobić z matrycą permutacyjną? Może być lepiej po prostu permutować wektor podczas nakładania operatora.

— Jed Brown

9

Według dokumentów nie ma metody permutacji w miejscu w numpy, coś takiego jak ndarray.sort .

Więc masz opcje (zakładając, że Mjest to macierz i wektor permutacji) $N\times N$ p

implementacja własnego algorytmu w C jako modułu rozszerzenia (ale algorytmy lokalne są trudne, przynajmniej dla mnie!)

$N$ Narzut pamięci

for i in range(N):
    M[:,i] = M[p,i]
for i in range(N):
    M[i,:] = M[i,p]

$N^2$ Narzut pamięci
```
M[:,:] = M[p,:]
M[:,:] = M[:,p]
```

Mam nadzieję, że te nieoptymalne hacki są przydatne.

— Stefano M.
źródło

@none is hack 2. to, co nazywacie „ręczną zamianą wierszy i kolumn”?

— Stefano M

1

Chciałbym połączyć opcje 1 i 2: napisz kod C, który używa bufora rzędu N do zapisu każdej permutowanej kolumny, a następnie zapisuje ją z powrotem tam, skąd pochodzi; następnie zrób to samo dla wierszy. Jak pisze @Stefano, zajmuje to tylko dodatkową pamięć , którą już spędzasz na przechowywanie permutacji .

O (N)

$O(N)$

p

$p$

— Erik P.

@ErikP. dla implementacji C dodatkowa pamięć jest rozsądna i na pewno twoje rozproszenie zapisu w temp i kopiowanie jest rozsądne. Interesujące jest jednak pytanie, czy istnieją wydajniejsze algorytmy, biorąc pod uwagę dodatkową pamięć . Myślę, że odpowiedź jest trudna, ponieważ powinniśmy wziąć pod uwagę architekturę procesora, wzorce dostępu do pamięci, trafienia w pamięci podręcznej ... To powiedziało, że będę postępować zgodnie z twoją radą i wybrać prosty i łatwy do wdrożenia algorytm.

O (N)

$O(N)$

O (N)

$O(N)$

— Stefano M

2

To jest naprawdę dobry Canidate dla funkcji cytonów. Nie powinno być więcej niż 10 linii. . . chcesz, żebym to zrobił?

— meawoppl

Lol. Zacząłem cytować to, a potem znalazłem właściwą odpowiedź w funkcji, z której cały czas korzystam. Doh Zobacz moją opublikowaną odpowiedź.

— meawoppl

6

Ostrzeżenie: poniższy przykład działa poprawnie, ale użycie pełnego zestawu parametrów sugerowanych po zakończeniu ujawnia błąd lub przynajmniej „nieudokumentowaną funkcję” w funkcji numpy.take (). Szczegóły znajdują się w komentarzach poniżej. Zgłoszony raport o błędzie .

Możesz to zrobić w miejscu za pomocą funkcji take () numpy , ale wymaga to nieco przeskoku.

Oto przykład losowej permutacji wierszy macierzy tożsamości:

import numpy as np
i = np.identity(10)
rr = range(10)
np.random.shuffle(rr)
np.take(i, rr, axis=0)
array([[ 0.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.],
       [ 1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.]])

Aby to zrobić w miejscu, wystarczy podać parametr „out”, aby był taki sam jak tablica wejściowa ORAZ musisz ustawić tryb = „klip” lub tryb = „zawiń”. Jeśli nie ustawisz trybu, utworzy kopię, aby przywrócić stan tablicy w wyjątku Pythona (patrz tutaj) .

Na koniec uwaga wydaje się być metodą tablicową, więc zamiast

np.take(i, rr, axis=0)

możesz zadzwonić

i.take(rr, axis=0)

jeśli to bardziej do gustu. W sumie zadzwoń powinien wyglądać mniej więcej tak:

#Inplace Rearrange
arr = makeMyBixMatrix()
pVec0, pVec1 = calcMyPermutationVectors()
arr.take(pVec0, axis=0, out=arr, mode="clip")
arr.take(pVec1, axis=1, out=arr, mode="clip")

Aby permutować zarówno wiersze, jak i kolumny, myślę, że albo trzeba je uruchomić dwa razy, albo wyciągnąć brzydkie shenanigany za pomocą numpy.unravel_index, który boli mnie do myślenia.

— meawoppl
źródło

Jak powiedziano, algorytmy na miejscu są trudne. Twoje rozwiązanie nie działa z Numpy 1.6.2. i 1.7.1 (zduplikowane wiersze / kolumny). Nie miałem czasu sprawdzić, czy 1.8.x rozwiązuje ten problem

— Stefano M.

Hmmm. Czy możesz gdzieś opublikować kod testowy? W mojej głowie wydaje mi się, że na indeksach musi nastąpić operacja sortowania, która nastąpi najpierw przed wyrywaniem. Zbadam więcej tego PM.

— meawoppl

1

Kiedy uruchomić ten kod otrzymuję 1.6.2, test take, not overwriting: True, test not-in-place take: True, test in-place take: False, rr [3, 7, 8, 1, 4, 5, 9, 0, 2, 6], arr [30 70 80 70 40 50 90 30 80 90], ref [30 70 80 10 40 50 90 0 20 60]. Tak więc np.takeprzynajmniej dla Numpy 1.6.2 nie jest świadomy rutynowej permutacji i wszystko psuje.

— Stefano M

Tak Dobrze zademonstrowane. Prawdopodobnie kwalifikuje się to jako błąd IMHO. Przynajmniej doktorzy powinni powiedzieć, że dane wejściowe i wyjściowe nie mogą być tą samą tablicą, prawdopodobnie sprawdź, czy nie.

— meawoppl

Zgadzam się na błąd: może powinieneś dodać notatkę do swojego postu, aby ostrzec czytelników, że twoje rozwiązanie może dawać błędne wyniki.

— Stefano M

2

Jeśli masz rzadką macierz przechowywaną w COOformacie, pomocne mogą być następujące elementy

    A.row = perm[A.row];
    A.col = perm[A.col];

przy założeniu, że Azawiera COOmatrycę, oraz permjest numpy.arrayzawierający permutacji. Będzie to miało tylko narzut pamięci , gdzie jest liczbą niezerowych elementów macierzy. $m$ $m$

— Vincent Traag
źródło

ale jaki jest narzut pamięci związany z przechowywaniem macierzy o pełnej gęstości jako C00macierzy rzadkich na pierwszym miejscu?

— Federico Poloni

Ponieważ liczba elementów jest równa zarówno w reprezentacji rzadkiej, jak i (pełnej) gęstej, różnica w pamięci jest jedynie stała (2 intsi 1 floatw rzadkiej reprezentacji na element jako pojedyncza floatw gęstej reprezentacji). Ale narzut pamięci tej metody będzie w gęstym przypadku, więc prawdopodobnie lepiej byłoby trzymać się zwykłych s.

n^{2}

$n^2$ numpy.ndarray

— Vincent Traag

1

Nie mam wystarczającej reputacji, aby móc komentować, ale myślę, że następujące SO pytanie może być pomocne: /programming/4370745/view-onto-a-numpy-array

Podstawowe punkty, które można wykorzystać podstawową krojenie i że stworzy widok na do tablicy bez kopiowania, ale jeśli zaawansowanym krojenia / indeksowanie to będzie utworzyć kopię.

— dawał
źródło

OP prosi o permutację, co nie jest możliwe w przypadku podstawowego krojenia.

— Stefano M

Oczywiście masz rację. Pomyślałem, że przydałoby się OP zrozumieć, co się dzieje z krojeniem (na wypadek, gdyby nie wiedzieli), ponieważ martwili się, kiedy będą się odbywały kopie. Jeśli użyłby czegoś z twojej odpowiedzi, myślę, że dobrze byłoby wiedzieć, ponieważ używasz ich w swoich pętlach.

— miał

-1

Co powiesz na

moja_tablica [:, [0, 1]] = moja_tablica [:, [1, 0]]

— johnsankey
źródło

1

To konstruuje tymczasowe, a dokładnie tego chce uniknąć.

— Michael Grant