Effiziente Verfahren zur Berechnung überschneidende Werte zwischen zwei numpy arrays

Ich habe einen Flaschenhals in meinem Programm, die durch Folgendes verursacht:

A = numpy.array([10,4,6,7,1,5,3,4,24,1,1,9,10,10,18])
B = numpy.array([1,4,5,6,7,8,9])

C = numpy.array([i for i in A if i in B])

Das erwartete Ergebnis für C ist folgende:

C = [4 6 7 1 5 4 1 1 9]

Ist es ein effizienter Weg, dies zu tun Betrieb?

Beachten Sie, dass array - A enthält sich wiederholende Werte und Sie müssen berücksichtigt werden. Ich war nicht in der Lage zu verwenden, setzen Kreuzung seit der Einnahme der Kreuzung wird es unterlassen, die sich wiederholenden Werte, Rückgabe nur [1,4,5,6,7,9].

Beachten Sie auch diese ist nur eine einfache demonstration. Die eigentliche array-Größen können in der Größenordnung von tausenden, die deutlich über einer Millionen.

InformationsquelleAutor user32147 | 2015-01-15
  1. 9

    Können Sie np.in1d:

    >>> A[np.in1d(A, B)]
array([4, 6, 7, 1, 5, 4, 1, 1, 9])

    np.in1d gibt einen boolean-array, der angibt, ob jeder Wert A erscheint auch in B. Dieses array kann dann verwendet werden, um index - A und Rückkehr zu den gemeinsamen Werten.

    Es ist nicht relevant zu Ihrem Beispiel, aber es ist auch erwähnenswert, dass, wenn A und B jede eindeutige Werte enthalten dann np.in1d kann beschleunigt werden, indem die Einstellung assume_unique=True:

    np.in1d(A, B, assume_unique=True)

    Könnten Sie auch interessieren np.intersect1d gibt ein array mit den einzigartigen gemeinsamen Werte der beiden arrays (sortiert nach Wert):

    >>> np.intersect1d(A, B)
array([1, 4, 5, 6, 7, 9])
    • Also unter der Annahme, dass zwei arrays sind einzigartig, wir könnten entweder np.in1d und np.intersect1d. Könnte Ihr Kommentar auf die Leistung zwischen den beiden?
    • Ich habe nicht getestet, die Leistung der beiden ausgiebig, aber np.intersect1d scheint ein bisschen schneller, wenn assume_unique eingestellt ist True bei beiden Methoden. Ich bin mir nicht sicher von den genauen Grund, warum, aber es kann sein das es da zu tun hat, weniger Vergleiche.
    InformationsquelleAutor Alex Riley
  2. 6

    Verwenden numpy.in1d:

    >>> A[np.in1d(A, B)]
array([4, 6, 7, 1, 5, 4, 1, 1, 9])
    InformationsquelleAutor Ashwini Chaudhary
  3. 2

    Wenn Sie das Kontrollkästchen nur für die Existenz in B ( if i in B ), dann Sie natürlich kann verwenden set für diese. Es spielt keine Rolle, wie viele Vieren gibt es in B solange es mindestens eine. Natürlich haben Sie Recht, dass Sie nicht verwenden können, zwei Sätze und eine Kreuzung. Aber auch eine set sollte die performance verbessern, da die Suche Komplexität ist weniger als O(n):

    A = numpy.array([10,4,6,7,1,5,3,4,24,1,1,9,10,10,18])
B = set([1,4,5,6,7,8,9])

C = numpy.array([i for i in A if i in B])
    InformationsquelleAutor BartoszKP
  4. 1

    Wir können np.searchsorted für die Leistung zu steigern, um so mehr für den Fall, wenn das lookup-array muss sortiert einzigartige Werte -

    def intersect1d_searchsorted(A,B,assume_unique=False):
    if assume_unique==0:
        B_ar = np.unique(B)
    else:
        B_ar = B
    idx = np.searchsorted(B_ar,A)
    idx[idx==len(B_ar)] = 0
    return A[B_ar[idx] == A]

    Dass assume_unique flag macht es für den Allgemeinen Fall und den speziellen Fall der B unique und sortiert.

    Probe Gefahren -

    In [89]: A = np.array([10,4,6,7,1,5,3,4,24,1,1,9,10,10,18])
    ...: B = np.array([1,4,5,6,7,8,9])

In [90]: intersect1d_searchsorted(A,B,assume_unique=True)
Out[90]: array([4, 6, 7, 1, 5, 4, 1, 1, 9])

    Timings zum Vergleich mit anderen Vektorgrafik - np.in1d basierte Lösung (aufgeführt in zwei anderen Antworten) auf große arrays für die beiden Fälle -

    In [103]: A = np.random.randint(0,10000,(1000000))

In [104]: B = np.random.randint(0,10000,(1000000))

In [105]: %timeit A[np.in1d(A, B)]
     ...: %timeit A[np.in1d(A, B, assume_unique=False)]
     ...: %timeit intersect1d_searchsorted(A,B,assume_unique=False)
1 loop, best of 3: 197 ms per loop
10 loops, best of 3: 190 ms per loop
10 loops, best of 3: 151 ms per loop

In [106]: B = np.unique(np.random.randint(0,10000,(5000)))

In [107]: %timeit A[np.in1d(A, B)]
     ...: %timeit A[np.in1d(A, B, assume_unique=True)]
     ...: %timeit intersect1d_searchsorted(A,B,assume_unique=True)
10 loops, best of 3: 130 ms per loop
1 loop, best of 3: 218 ms per loop
10 loops, best of 3: 80.2 ms per loop
    InformationsquelleAutor Divakar
Schreibe einen Kommentar