czy funkcja maskowania in1d lepsza niż numpy: uporządkowane tablice?

Question

Ta operacja musi być zastosowana tak szybko, jak to możliwe, ponieważ rzeczywiste tablice zawierają miliony elementów. Jest to prosta wersja problemu.

Tak, mam losową tablicę unikalnych liczb całkowitych (zwykle miliony elementów).

totalIDs = [5,4,3,1,2,9,7,6,8 ...]

mam inny szereg (zwykle kilkudziesięciu tysięcy) unikalnych liczb które mogę stworzyć maskę.

subsampleIDs1 = [5,1,9] 
subsampleIDs2 = [3,7,8] 
subsampleIDs3 = [2,6,9] 
... 

mogę używać numpy zrobić

maskę = np.in1d ​​(totalIDs, subsampleIDs, assume_unique = True)

można następnie wyodrębnić informacje chcę innej tablicy używając maski (na przykład kolumna 0 zawiera tę, którą chcę).

zmienna = allvariables [maska] [:, 0]

teraz ponieważ identyfikatory są unikalne w obu układach, jest jakiś sposób przyspieszyć proces istotnie. Dużo czasu zajmuje skonstruowanie maski na kilka tysięcy punktów (subsampleID) dopasowanych do milionów identyfikatorów (totalIDs).

Myślałem o przejściu przez to i napisaniu binarnego pliku indeksu (aby przyspieszyć przyszłe wyszukiwania).

for i in range(0,3): 
    mask = np.in1d(totalIDs,subsampleIDs,assume_unique=True) 
    index[mask] = i 

gdzie X jest w subsampleIDX. Wtedy mogę po prostu zrobić:

for i in range(0,3): 
    if index[i] == i: 
     rowmatch = i 
     break 

variable = allvariables[rowmatch:len(subsampleIDs),0] 

prawda? Ale jest to również powolne, ponieważ w pętli znajduje się warunek do znalezienia, kiedy pierwszy raz pasuje. Czy istnieje szybszy sposób na znalezienie, kiedy po raz pierwszy pojawia się w uporządkowanej tablicy, więc warunkowe nie spowalnia pętli?

Answer 1

Proponuję użyć DataFrame w Pand. indeksem DataFrame jest totalID, a możesz wybrać subsampleID przez: df.ix[subsampleIDs].

Tworzenie niektóre dane testowe pierwszy:

import numpy as np 
N = 2000000 
M = 5000 
totalIDs = np.random.randint(0, 10000000, N) 
totalIDs = np.unique(totalIDs) 
np.random.shuffle(totalIDs) 
v1 = np.random.rand(len(totalIDs)) 
v2 = np.random.rand(len(totalIDs)) 

subsampleIDs = np.random.choice(totalIDs, M) 
subsampleIDs = np.unique(subsampleIDs) 
np.random.shuffle(subsampleIDs) 

następnie przekonwertować Ci dane do DataFrame:

import pandas as pd 
df = pd.DataFrame(data = {"v1":v1, "v2":v2}, index=totalIDs) 
df.ix[subsampleIDs] 

DataFrame używać hashtable mapować indeks to miejsce, to bardzo szybko.

Answer 2

Często ten rodzaj indeksowania najlepiej wykonywać przy użyciu DB (z odpowiednim indeksowaniem kolumn).

Innym pomysłem jest sortowanie totalIDs raz, jako etap wstępnego przetwarzania, i wdrożenie własnej wersji in1d, co pozwala uniknąć sortowania wszystkiego. Nppy implementacja in1d (przynajmniej w wersji, którą zainstalowałem) jest dość prosta i powinna być łatwa do skopiowania i modyfikacji.

EDIT:

Albo, jeszcze lepiej, korzystanie sortowanie kubełkowe (lub sortowanie pozycyjne). To powinno dać ci O (N + M), N jest wielkości totalIDs, a M wielkości sampleIDs (razy stała możesz grać, zmieniając liczbę kubełków). Tutaj również możesz podzielić totalIDs na wiadra tylko raz, co daje ładną O (N + M1 + M2 + ...).

Niestety, nie jestem świadomy realizacji numpy, ale nie znaleźliśmy to: http://en.wikipedia.org/wiki/Radix_sort#Example_in_Python