geht es besser als numpy in1d maske funktion: geordnete arrays?

Question

Diese Operation muss so schnell wie möglich als die tatsächlichen Arrays, die Millionen von Elementen enthalten, angewendet werden. Dies ist eine einfache Version des Problems.

Also habe ich eine zufällige Reihe von einzigartige ganze Zahlen (normalerweise Millionen von Elementen).

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

ich ein anderes Array (normalerweise ein Zehntausende) von einzigartigen ganzen Zahlen womit ich eine Maske erstellen kann.

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

kann ich numpy

Maske tun = np.in1d ​​(totalIDs, subsampleIDs, assume_unique = True)

Ich kann dann die Informationen extrahieren ich von einem anderen Array wollen benutze die Maske (zB Spalte 0 enthält die eine, die ich möchte).

variable = allvariables [Maske] [:, 0]

nun gegeben, dass die IDs in beiden Arrays eindeutig sind, gibt es eine Möglichkeit, dies deutlich zu beschleunigen. Es dauert lange, bis die Maske für einige tausend Punkte (SubsampleIDs) erstellt wurde, die mit Millionen von IDs (TotalIDs) übereinstimmen.

Ich dachte daran, einmal durchzugehen und eine Binärdatei eines Indexes zu schreiben (um zukünftige Suchen zu beschleunigen).

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

wo X ist in subsampleIDsX. Dann kann ich einfach tun:

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

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

richtig? Dies ist jedoch auch langsam, da in der Schleife eine Bedingung vorhanden ist, um zu finden, wann sie das erste Mal übereinstimmt. Gibt es einen schnelleren Weg zu finden, wenn eine Zahl zuerst in einem geordneten Array erscheint, so dass die Bedingung die Schleife nicht verlangsamt?

Answer 1

Ich schlage vor, Sie Datenrahmen in Pandas verwenden. Der Index des DataFrame ist die TotalIDs, und Sie können SubsampleIDs folgendermaßen auswählen: df.ix[subsampleIDs].

einige Testdaten erstellen zuerst:

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) 

Sie dann konvertieren Daten in einen Datenrahmen:

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

Datenrahmen eine Hash-Tabelle verwenden Sie den Index abzubilden, um seine Lage, es ist sehr schnell.

Answer 2

Oft wird diese Art der Indizierung am besten mit einem DB (mit richtiger Spaltenindexierung) durchgeführt.

Eine andere Idee ist, einmal als Vorverarbeitungsstufe totalIDs zu sortieren und Ihre eigene Version in1d zu implementieren, die alles zu sortieren vermeidet. Die numplige Implementierung von in1d (zumindest in der Version, die ich installiert habe) ist ziemlich einfach und sollte einfach zu kopieren und zu ändern sein.

EDIT:

Oder, noch besser, verwenden Bucketsort (oder Radixsort). Das sollte Ihnen O (N + M) geben, N ist die Größe von totalIDs und M die Größe von sampleIDs (mal eine Konstante, mit der Sie spielen können, indem Sie die Anzahl der Buckets ändern). Auch hier können Sie totalIDs nur einmal in Buckets aufteilen, was Ihnen einen raffinierten O (N + M1 + M2 + ...) gibt.

Leider bin ich eine numpy Implementierung nicht bewusst, aber ich dies fand: http://en.wikipedia.org/wiki/Radix_sort#Example_in_Python