I'm desperately searching for an efficient way to check if two 2D numpy Arrays intersect.
So what I have is two arrays with an arbitrary amount of 2D arrays like:
All I need is a True if there is at least one vector intersecting with another one of the other array, otherwise a false. So it should give results like this:
f(A,B) -> True
f(A,C) -> False
I'm kind of new to python and at first I wrote my program with Python lists, which works but of course is very inefficient. The Program takes days to finish so I am working on a
numpy.array solution now, but these arrays really are not so easy to handle.
Here's Some Context about my Program and the Python List Solution:
What i'm doing is something like a self-avoiding random walk in 3 Dimensions. http://en.wikipedia.org/wiki/Self-avoiding_walk. But instead of doing a Random walk and hoping that it will reach a desirable length (e.g. i want chains build up of 1000 beads) without reaching a dead end i do the following:
I create a "flat" Chain with the desired length N:
for i in range(0,N+1):
Now i fold this flat chain:
Steps 1.-6. have to be done a large amount of times (e.g. for a chain of length 1000, ~5000 Times) so these steps have to be done efficiently. My List-based solution for this is the following:
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
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
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
for j in range (randPiv,N+1):
for j in range (randPiv,N+1):
if intersect==False: # return C if there was no intersection in C
The Function PivotFold(chain) will be used on the initially flat chain X a large amount of times. it's pretty naivly written so maybe you have some protips to improve this ^^ I thought that numpyarrays would be good because i can efficiently shift and rotate entire chains without looping over all the elements ...
This should do it:
In : def f(arrA, arrB): return not set(map(tuple, arrA)).isdisjoint(map(tuple, arrB)) In : f(A, B) Out: True In : f(A, C) Out: False In : f(B, C) Out: False
To find intersection? OK,
set sounds like a logical choice.
list are not hashable? OK, convert them to
That is the idea.
numpy way of doing involves very unreadable boardcasting:
In : (A[...,np.newaxis]==B[...,np.newaxis].T).all(1) Out: array([[False, False], [ True, False], [False, False]], dtype=bool) In : (A[...,np.newaxis]==B[...,np.newaxis].T).all(1).any() Out: True
Some timeit result:
In : #Dan's method %timeit set_comp(A,B) 10000 loops, best of 3: 34.1 µs per loop In : #Avoiding lambda will speed things up %timeit f(A,B) 10000 loops, best of 3: 23.8 µs per loop In : #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
numpy method will be RAM hungry, as
A[...,np.newaxis]==B[...,np.newaxis].T step creates a 3D array.
Using the same idea outlined here, you could do the following:
def make_1d_view(a): a = np.ascontiguousarray(a) dt = np.dtype((np.void, a.dtype.itemsize * a.shape)) 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
This doesn't work for floating point types (it will not consider +0.0 and -0.0 the same value), and
np.intersect1d uses sorting, so it is has linearithmic, not linear, performance. You may be able to squeeze some performance by replicating the source of
np.intersect1d in your code, and instead of checking the length of the return array, calling
np.any on the boolean indexing array.
This should be much faster it is not O(n^2) like the for-loop solution, but it isn't fully numpythonic. Not sure how better to leverage numpy here
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)
You can also get the job done with some
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) ) Y = np.swapaxes(Y[:,:,None], 0, 2) Y = np.tile(Y, (X.shape, 1, 1)) eq = np.all(np.equal(X, Y), axis = 1) eq = np.any(eq, axis = 1) return np.nonzero(eq)
To answer the question more specifically, you'd only need to check if the returned array is empty.
i think you want true if tow arrays have subarray set ! you can use this :
def(A,B): for i in A: for j in B: if i==j return True return False