Ich muss an zwei großen Arrays arbeiten. Schauen wir uns jedoch das folgende vereinfachte Beispiel an, um die Idee zu erhalten:

Ich möchte herausfinden, ob ein Element in data1 mit einem Element in data2 übereinstimmt, und den Array-Index sowohl in data1 als auch in data2 zurückgeben, wenn eine Übereinstimmung in der Form gefunden wird eines neuen Arrays [index of data1, index of data2]. Mit dem folgenden Satz von data1 und data2 gibt das Programm beispielsweise Folgendes zurück:

data1 = [[1,1],[2,5],[623,781]] 
data2 = [[1,1], [161,74],[357,17],[1,1]]
expected_output = [[0,0],[0,3]]

Mein aktueller Code lautet wie folgt:

result = []
for index, item in enumerate(data1):
    for index2,item2 in enumerate(data2):
        if np.array_equal(item,item2):
            result.append([index,index2])
>>> result
[[0, 0], [0, 3]]

Das funktioniert gut. Die beiden Arrays, an denen ich arbeite, enthalten jedoch jeweils 0,6 Millionen Elemente. Der obige Code wäre extrem langsam. Gibt es eine Methode, um den Prozess zu beschleunigen?

1
yuk ching leung 19 Apr. 2018 im 05:48

3 Antworten

Beste Antwort

Wahrscheinlich nicht die schnellste, aber einfach und relativ schnell: Verwenden Sie KDTrees:

>>> data1 = [[1,1],[2,5],[623,781]] 
>>> data2 = [[1,1], [161,74],[357,17],[1,1]]
>>>
>>> from operator import itemgetter
>>> from scipy.spatial import cKDTree as KDTree
>>>
>>> def intersect(a, b):
...     A = KDTree(a); B = KDTree(b); X = A.query_ball_tree(B, 0.5)
...     ai, bi = zip(*filter(itemgetter(1), enumerate(X)))
...     ai = np.repeat(ai, np.fromiter(map(len, bi), int, len(ai)))
...     bi = np.concatenate(bi)
...     return ai, bi
... 
>>> intersect(data1, data2)
(array([0, 0]), array([0, 3]))

Zwei gefälschte Datensätze 1,000,000 Paare benötigen jeweils 3 Sekunden:

>>> from time import perf_counter
>>> 
>>> a = np.random.randint(0, 100000, (1000000, 2))
>>> b = np.random.randint(0, 100000, (1000000, 2))
>>> t = perf_counter(); intersect(a, b); s = perf_counter()
(array([   971,   3155,  15034,  35844,  41173,  60467,  73758,  91585,
        97136, 105296, 121005, 121658, 124142, 126111, 133593, 141889,
       150299, 165881, 167420, 174844, 179410, 192858, 222345, 227722,
       233547, 234932, 243683, 248863, 255784, 264908, 282948, 282951,
       285346, 287276, 302142, 318933, 327837, 328595, 332435, 342289,
       344780, 350286, 355322, 370691, 377459, 401086, 412310, 415688,
       442978, 461111, 469857, 491504, 493915, 502945, 506983, 507075,
       511610, 515631, 516080, 532457, 541138, 546281, 550592, 551751,
       554482, 568418, 571825, 591491, 594428, 603048, 639900, 648278,
       666410, 672724, 708500, 712873, 724467, 740297, 740640, 749559,
       752723, 761026, 777911, 790371, 791214, 793415, 795352, 801873,
       811260, 815527, 827915, 848170, 861160, 892562, 909555, 918745,
       924090, 929919, 933605, 939789, 940788, 940958, 950718, 950804,
       997947]), array([507017, 972033, 787596, 531935, 590375, 460365,  17480, 392726,
       552678, 545073, 128635, 590104, 251586, 340475, 330595, 783361,
       981598, 677225,  80580,  38991, 304132, 157839, 980986, 881068,
       308195, 162984, 618145,  68512,  58426, 190708, 123356, 568864,
       583337, 128244, 106965, 528053, 626051, 391636, 868254, 296467,
        39446, 791298, 356664, 428875, 143312, 356568, 736283, 902291,
         5607, 475178, 902339, 312950, 891330, 941489,  93635, 884057,
       329780, 270399, 633109, 106370, 626170,  54185, 103404, 658922,
       108909, 641246, 711876, 496069, 835306, 745188, 328947, 975464,
       522226, 746501, 642501, 489770, 859273, 890416,  62451, 463659,
       884001, 980820, 171523, 222668, 203244, 149955, 134192, 369508,
       905913, 839301, 758474, 114597, 534015, 381467,   7328, 447698,
       651929, 137424, 975677, 758923, 982976, 778075,  95266, 213456,
       210555]))
>>> print(s-t)
2.98617472499609
3
Paul Panzer 19 Apr. 2018 im 03:34

Da Ihre Daten alle Ganzzahlen sind, können Sie ein Wörterbuch (Hash-Tabelle) verwenden. Die Zeit beträgt 0,55 Sekunden für dieselben Daten wie in Pauls Antwort. Dadurch werden nicht unbedingt alle Kopien von Paarungen zwischen a und b gefunden (dh wenn a und b selbst Duplikate enthalten), aber es ist einfach genug, dies zu ändern das oder um danach einen zweiten Durchgang zu machen (über nur die übereinstimmenden Elemente), um nach anderen Vorkommen dieser Vektoren in den Daten zu suchen.

import numpy as np

def intersect1(a, b):
    a_d = {}
    for i, x in enumerate(a):
        a_d[x] = i
    for i, y in enumerate(b):
        if y in a_d:
            yield a_d[y], i

from time import perf_counter
a = list(tuple(x) for x in list(np.random.randint(0, 100000, (1000000, 2))))
b = list(tuple(x) for x in list(np.random.randint(0, 100000, (1000000, 2))))
t = perf_counter(); print(list(intersect1(a, b))); s = perf_counter()
print(s-t)

Zum Vergleich: Paul nimmt 2,46 Sekunden auf meiner Maschine.

1
amiller27 19 Apr. 2018 im 04:24

Hinweis Die anderen Antworten, die ein Wörterbuch (zum Überprüfen der genauen Übereinstimmungen) oder einen KDTree (für Übereinstimmungen mit Epsilon-Nähe) verwenden, sind viel besser - sowohl viel schneller als auch viel speichereffizienter .

Verwenden Sie scipy .spatial.distance.cdist. Wenn Ihre beiden Datenfelder jeweils N und M Einträge haben, wird ein paarweises Distanzarray N mal M erstellt. Wenn Sie das in den Arbeitsspeicher einpassen können, ist es einfach, die passenden Indizes zu finden:

import numpy as np
from scipy.spatial.distance import cdist

# Generate some data that's very likely to have repeats    
a = np.random.randint(0, 100, (1000, 2))
b = np.random.randint(0, 100, (1000, 2))

# `cityblock` is likely the cheapest distance to calculate (no sqrt, etc.)
c = cdist(a, b, 'cityblock')

# And the indexes of all the matches:
aidx, bidx = np.nonzero(c == 0)

# sanity check:
print([(a[i], b[j]) for i,j in zip(aidx, bidx)])

Das obige druckt aus:

[(array([ 0, 84]), array([ 0, 84])),
 (array([50, 73]), array([50, 73])),
 (array([53, 86]), array([53, 86])),
 (array([96, 85]), array([96, 85])),
 (array([95, 18]), array([95, 18])),
 (array([ 4, 59]), array([ 4, 59])), ... ]
0
Ahmed Fasih 19 Apr. 2018 im 04:05