Python - 二维 Numpy 数组的交集 [英] Python - Intersection of 2D Numpy Arrays

问题描述

我正在拼命寻找一种有效的方法来检查两个 2D numpy 数组是否相交.

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:

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]])

如果至少有一个向量与另一个数组中的另一个向量相交，我只需要一个 True ，否则为 false.所以它应该给出这样的结果:

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

我对 python 有点陌生，一开始我用 Python 列表编写了我的程序，这行得通，但当然效率很低.该程序需要数天才能完成，所以我现在正在研究 numpy.array 解决方案，但这些数组确实不是那么容易处理.

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.

以下是关于我的程序和 Python 列表解决方案的一些上下文:

Here's Some Context about my Program and the Python List Solution:

我正在做的事情类似于在 3 维中进行自我回避的随机游走.http://en.wikipedia.org/wiki/Self-avoiding_walk.但是，与其进行随机游走并希望它达到理想的长度(例如，我想要由 1000 个珠子组成的链)而不达到死胡同，我执行以下操作:

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:

我创建了一个具有所需长度 N 的扁平"链:

I create a "flat" Chain with the desired length N:

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

现在我折叠这条扁平链:

Now i fold this flat chain:

1. 随机选择一个元素(pivotelement")
2. 随机选择一个方向(枢轴左侧或右侧的所有元素)
3. 从空间中 9 种可能的旋转中随机选择一种(3 轴 * 3 种可能的旋转 90°、180°、270°)
4. 使用所选旋转旋转所选方向的所有元素
5. 检查所选方向的新元素是否与另一个方向相交
6. 无交集 -> 接受新配置，否则 -> 保留旧链.

步骤 1.-6.必须执行大量时间(例如，对于长度为 1000 次的链，约 5000 次)，因此必须有效地完成这些步骤.我的基于列表的解决方案如下:

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:

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

函数 PivotFold(chain) 将在最初的扁平链 X 上大量使用.它写得非常天真，所以也许你有一些技巧可以改进这个 ^^ 我认为 numpyarrays 会很好，因为我可以有效地移动和旋转整个链而无需遍历所有元素......

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 ...

推荐答案

应该这样做:

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

找交点?好的，set 听起来是一个合乎逻辑的选择.但是 numpy.array 或 list 不是可散列的吗?好的，将它们转换为 tuple.就是这个想法.

To find intersection? OK, set sounds like a logical choice. But numpy.array or list are not hashable? OK, convert them to tuple. That is the idea.

numpy 的做法涉及非常不可读的广播:

A numpy way of doing involves very unreadable boardcasting:

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

一些时间结果:

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

此外，numpy 方法将占用 RAM，如 A[...,np.newaxis]==B[...,np.newaxis].T step 创建一个 3D 数组.

Also the numpy method will be RAM hungry, as A[...,np.newaxis]==B[...,np.newaxis].T step creates a 3D array.

这篇关于Python - 二维 Numpy 数组的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！