Python – Intersección de Arrays Numpy 2D

Estoy buscando desesperadamente una manera eficiente de verificar si dos Arrays de números 2D se intersecan.

Entonces, lo que tengo son dos matrices con una cantidad arbitraria de matrices 2D como:

A=np.array([[2,3,4],[5,6,7],[8,9,10]]) B=np.array([[5,6,7],[1,3,4]]) C=np.array([[1,2,3],[6,6,7],[10,8,9]]) 

Todo lo que necesito es un Verdadero si hay al menos un vector que se interseca con otro de la otra matriz, de lo contrario es falso. Entonces debería dar resultados como este:

 f(A,B) -> True f(A,C) -> False 

Soy un poco nuevo en Python y al principio escribí mi progtwig con listas de Python, lo cual funciona pero, por supuesto, es muy ineficiente. El progtwig tarda días en terminarse, así que estoy trabajando en una solución numpy.array ahora, pero estos arreglos realmente no son tan fáciles de manejar.

Aquí hay un poco de contexto sobre mi progtwig y la solución de la lista de Python:

Lo que estoy haciendo es algo así como un paseo aleatorio auto-evitado en 3 Dimensiones. http://en.wikipedia.org/wiki/Self-avoiding_walk . Pero en lugar de hacer una caminata aleatoria y esperar que scope una longitud deseable (por ejemplo, quiero que se formen cadenas de 1000 cuentas) sin llegar a un callejón sin salida, hago lo siguiente:

Creo una cadena “plana” con la longitud deseada N:

 X=[] for i in range(0,N+1): X.append((i,0,0)) 

Ahora doblo esta cadena plana:

  1. elegir al azar uno de los elementos (“pivotelement”)
  2. elija al azar una dirección (ya sea todos los elementos a la izquierda o a la derecha del pivotelment)
  3. elija al azar una de las 9 posibles rotaciones en el espacio (3 ejes * 3 posibles rotaciones 90 °, 180 °, 270 °)
  4. Gire todos los elementos de la dirección elegida con la rotación elegida.
  5. Compruebe si los nuevos elementos de la dirección elegida se intersecan con la otra dirección
  6. No hay intersección -> acepte la nueva configuración, de lo contrario -> mantenga la cadena antigua.

Pasos 1.-6. se debe realizar una gran cantidad de veces (por ejemplo, para una cadena de longitud 1000, ~ 5000 veces), por lo que estos pasos deben realizarse de manera eficiente. Mi solución basada en la lista para esto es la siguiente:

 def PivotFold(chain): randPiv=random.randint(1,N) #Chooses a random pivotelement, N is the Chainlength Pivot=chain[randPiv] #get that pivotelement C=[] #C is going to be a shifted copy of the chain intersect=False for j in range (0,N+1): # Here i shift the hole chain to get the pivotelement to the origin, so i can use simple rotations around the origin C.append((chain[j][0]-Pivot[0],chain[j][1]-Pivot[1],chain[j][2]-Pivot[2])) rotRand=random.randint(1,18) # rotRand is used to choose a direction and a Rotation (2 possible direction * 9 rotations = 18 possibilitys) #Rotations around Z-Axis if rotRand==1: for j in range (randPiv,N+1): C[j]=(-C[j][1],C[j][0],C[j][2]) if C[0:randPiv].__contains__(C[j])==True: intersect=True break elif rotRand==2: for j in range (randPiv,N+1): C[j]=(C[j][1],-C[j][0],C[j][2]) if C[0:randPiv].__contains__(C[j])==True: intersect=True break ...etc if intersect==False: # return C if there was no intersection in C Shizz=C else: Shizz=chain return Shizz 

La función PivotFold (cadena) se usará en la cadena inicialmente plana X una gran cantidad de veces. está bastante ingenuamente escrito, así que quizás tengas algunos protips para mejorar esto ^^ Pensé que sería bueno numpyarrays porque puedo desplazar y rotar eficientemente cadenas enteras sin hacer un bucle sobre todos los elementos …

Esto debería hacerlo:

 In [11]: def f(arrA, arrB): return not set(map(tuple, arrA)).isdisjoint(map(tuple, arrB)) In [12]: f(A, B) Out[12]: True In [13]: f(A, C) Out[13]: False In [14]: f(B, C) Out[14]: False 

¿Para encontrar la intersección? OK, set suena como una opción lógica. ¿Pero numpy.array o list no son hashable? OK, conviértelos a tuple . Esa es la idea.

Una forma de hacer muchas cosas involucra el envío de tablas muy ilegible:

 In [34]: (A[...,np.newaxis]==B[...,np.newaxis].T).all(1) Out[34]: array([[False, False], [ True, False], [False, False]], dtype=bool) In [36]: (A[...,np.newaxis]==B[...,np.newaxis].T).all(1).any() Out[36]: True 

Algún tiempo es el resultado:

 In [38]: #Dan's method %timeit set_comp(A,B) 10000 loops, best of 3: 34.1 µs per loop In [39]: #Avoiding lambda will speed things up %timeit f(A,B) 10000 loops, best of 3: 23.8 µs per loop In [40]: #numpy way probably will be slow, unless the size of the array is very big (my guess) %timeit (A[...,np.newaxis]==B[...,np.newaxis].T).all(1).any() 10000 loops, best of 3: 49.8 µs per loop 

También el método numpy tendrá memoria RAM, ya que A[...,np.newaxis]==B[...,np.newaxis].T step crea una matriz 3D.

Usando la misma idea descrita aquí , podrías hacer lo siguiente:

 def make_1d_view(a): a = np.ascontiguousarray(a) dt = np.dtype((np.void, a.dtype.itemsize * a.shape[1])) return a.view(dt).ravel() def f(a, b): return len(np.intersect1d(make_1d_view(A), make_1d_view(b))) != 0 >>> f(A, B) True >>> f(A, C) False 

Esto no funciona para los tipos de punto flotante (no considerará el mismo valor para np.intersect1d y np.intersect1d ), y np.intersect1d usa la clasificación, por lo que tiene un rendimiento lineal, no lineal. Es posible que pueda exprimir algo de rendimiento replicando la fuente de np.intersect1d en su código, y en lugar de verificar la longitud de la matriz de retorno, llame a np.any en la matriz de indexación booleana.

¡También puede hacer el trabajo con algunos negocios np.tile y np.swapaxes !

 def intersect2d(X, Y): """ Function to find intersection of two 2D arrays. Returns index of rows in X that are common to Y. """ X = np.tile(X[:,:,None], (1, 1, Y.shape[0]) ) Y = np.swapaxes(Y[:,:,None], 0, 2) Y = np.tile(Y, (X.shape[0], 1, 1)) eq = np.all(np.equal(X, Y), axis = 1) eq = np.any(eq, axis = 1) return np.nonzero(eq)[0] 

Para responder a la pregunta más específicamente, solo necesita verificar si la matriz devuelta está vacía.

Esto debería ser mucho más rápido, no es O (n ^ 2) como la solución de bucle for, pero no es completamente numpythonic. No estoy seguro de cómo aprovechar mejor numpy aquí

 def set_comp(a, b): sets_a = set(map(lambda x: frozenset(tuple(x)), a)) sets_b = set(map(lambda x: frozenset(tuple(x)), b)) return not sets_a.isdisjoint(sets_b) 

Creo que quieres verdad si los arreglos de arrastre tienen un conjunto de subarreglos! puedes usar esto:

 def(A,B): for i in A: for j in B: if i==j return True return False 

Este problema se puede resolver de manera eficiente utilizando el paquete numpy_indexed (descargo de responsabilidad: soy su autor):

 import numpy_indexed as npi len(npi.intersection(A, B)) > 0