Mam tablicę numpy taką jak ta: [1 2 2 0 0 1 3 5]
Czy można uzyskać indeks elementów w postaci tablicy 2d? Na przykład odpowiedzią na powyższe dane wejściowe byłoby[[3 4], [0 5], [1 2], [6], [], [7]]
Obecnie muszę zapętlać różne wartości i wywoływać numpy.where(input == i)
każdą wartość, która ma straszną wydajność przy wystarczająco dużym wejściu.
python
numpy
numpy-ndarray
Frederico Schardong
źródło
źródło
np.argsort([1, 2, 2, 0, 0, 1, 3, 5])
dajearray([3, 4, 0, 5, 1, 2, 6, 7], dtype=int64)
. wtedy możesz po prostu porównać kolejne elementy.Odpowiedzi:
Oto podejście O (max (x) + len (x)) przy użyciu
scipy.sparse
:Działa to poprzez utworzenie rzadkiej macierzy z wpisami w pozycjach (x [0], 0), (x [1], 1), ... Przy użyciu
CSC
formatu (skompresowanej kolumny rzadkiej) jest to dość proste. Macierz jest następnie konwertowana doLIL
formatu (lista połączona). Ten format przechowuje indeksy kolumn dla każdego wiersza jako listę w swoimrows
atrybucie, więc wszystko, co musimy zrobić, to wziąć to i przekonwertować na listę.Należy zauważyć, że w przypadku
argsort
rozwiązań opartych na małych tablicach są one prawdopodobnie szybsze, ale przy niektórych, nie tak niesamowicie dużych rozmiarach, to się krzyżuje.EDYTOWAĆ:
argsort
na podstawie -numpy
tylko rozwiązanie:Jeśli kolejność indeksów w grupach nie ma znaczenia, możesz także spróbować
argpartition
(w tym małym przykładzie nie robi to różnicy, ale ogólnie nie jest to gwarantowane):EDYTOWAĆ:
@Divakar odradza korzystanie z
np.split
. Zamiast tego pętla jest prawdopodobnie szybsza:Lub możesz użyć zupełnie nowego operatora morsa (Python3.8 +):
EDYCJA (EDYCJA):
(Not pure numpy): Alternatywnie do numby (patrz post @ senderle) możemy również użyć pythran.
Połącz z
pythran -O3 <filename.py>
Tutaj
numba
wygrywa bokser pod względem wydajności:Starsze rzeczy:
Czasy vs. Numba (stary)
źródło
np.split
.Jedną z potencjalnych opcji w zależności od rozmiaru danych jest po prostu porzucenie
numpy
i użyciecollections.defaultdict
:Potem skończysz ze słownikiem
{value1: [index1, index2, ...], value2: [index3, index4, ...]}
. Skalowanie czasu jest bardzo zbliżone do liniowego z rozmiarem tablicy, więc 10 000 000 zajmuje ~ 2,7 s na moim komputerze, co wydaje się dość rozsądne.źródło
Chociaż prośba dotyczy
numpy
rozwiązania, postanowiłem sprawdzić, czy istniejenumba
rozwiązanie oparte na ciekawych rozwiązaniach. I rzeczywiście jest! Oto podejście, które reprezentuje podzieloną na partycje listę jako poszarpaną tablicę przechowywaną w pojedynczym wstępnie przydzielonym buforze. Inspiruje toargsort
podejście zaproponowane przez Paula Panzera . (W przypadku starszej wersji, która nie działała tak dobrze, ale była prostsza, patrz poniżej).Przetwarza dziesięciomilionową listę elementów w 75 ms, co stanowi prawie 50-krotne przyspieszenie w porównaniu z wersją opartą na listach napisaną w czystym języku Python.
W przypadku wolniejszej, ale nieco bardziej czytelnej wersji, oto co miałem wcześniej, w oparciu o niedawno dodane eksperymentalne wsparcie dla dynamicznie zmieniających się „list maszynowych”, które pozwalają nam szybciej zapełniać każdy pojemnik w niewłaściwym porządku.
To
numba
trochę zmaga się z silnikiem wnioskowania typu i jestem pewien, że jest lepszy sposób na poradzenie sobie z tą częścią. To również okazuje się prawie 10 razy wolniejsze niż powyższe.Przetestowałem je pod kątem następujących elementów:
Przetestowałem je również w stosunku do wstępnie skompilowanej wersji cytonu podobnej do
enum_bins_numba_buffer
(opisanej szczegółowo poniżej).Na liście dziesięciu milionów losowych liczb całkowitych (
ints = np.random.randint(0, 100, 10000000)
) otrzymuję następujące wyniki:Imponująco, ten sposób pracy z
numba
programem przewyższacython
wersję tej samej funkcji, nawet przy wyłączonym sprawdzaniu granic. Nie mam jeszcze wystarczającej znajomości,pythran
aby przetestować to podejście przy użyciu tej metody, ale chciałbym zobaczyć porównanie. Wydaje się prawdopodobne, na podstawie tego przyspieszenia, że tapythran
wersja może być nieco szybsza.Oto
cython
wersja w celach informacyjnych z kilkoma instrukcjami kompilacji. Pocython
zainstalowaniu będziesz potrzebować prostegosetup.py
pliku takiego jak ten:I moduł cytonowy
enum_bins_cython.pyx
:Z tymi dwoma plikami w katalogu roboczym uruchom następującą komendę:
Następnie możesz zaimportować funkcję za pomocą
from enum_bins_cython import enum_bins_cython
.źródło
Oto naprawdę dziwny sposób na zrobienie tego, co jest okropne, ale uznałem, że to zbyt zabawne, aby nie udostępniać - i wszystko
numpy
!EDYCJA: to najlepsza metoda, jaką mogłem znaleźć na tej ścieżce. Jest wciąż 10 razy wolniejszy niż
argsort
rozwiązanie @PaulPanzer :źródło
Możesz to zrobić, tworząc słownik liczb, kluczami byłyby liczby, a wartości powinny być indeksami, które widziały liczby, jest to jeden z najszybszych sposobów, aby to zrobić, możesz zobaczyć kod poniżej:
źródło
Pseudo kod:
uzyskaj „liczbę tablic 1d w tablicy 2d”, odejmując minimalną wartość tablicy numpy od wartości maksymalnej, a następnie plus jeden. W twoim przypadku będzie to 5-0 + 1 = 6
zainicjuj tablicę 2d liczbą zawartych w niej tablic 1d. W twoim przypadku zainicjuj tablicę 2d z tablicą 6 1d. Każda tablica 1d odpowiada unikalnemu elementowi w tablicy numpy, na przykład pierwsza tablica 1d odpowiada „0”, druga tablica 1d odpowiada „1”, ...
zapętlić pętlę przez tablicę numpy, umieścić indeks elementu w odpowiedniej odpowiedniej tablicy 1d. W twoim przypadku indeks pierwszego elementu w tablicy numpy zostanie umieszczony w drugiej tablicy 1d, indeks drugiego elementu w tablicy numpy zostanie umieszczony w trzeciej tablicy 1d ...
Uruchomienie tego pseudokodu zajmie czas liniowy, ponieważ zależy to od długości tablicy numpy.
źródło
To daje dokładnie to, czego chcesz i zajęłoby około 2,5 sekundy na 10 000 000 na moim komputerze:
źródło
Biorąc pod uwagę listę elementów, chcesz utworzyć pary (element, indeks). W czasie liniowym można to zrobić jako:
Powinno to zająć czas O (n). Nie mogę teraz wymyślić szybszego rozwiązania, ale zaktualizuję tutaj, jeśli to zrobię.
źródło