python - 查找与给定向量相似的所有向量的快速方法

Question

通过“相似向量”，我定义了一个向量，该向量仅在一个位置与给定向量相差 -1 或 1。但是，如果给定向量的元素为零，则只能相差 1。示例:

similar_vectors(np.array([0,0,0]))

array([[ 1.,  0.,  0.],
       [ 0.,  1.,  0.],
       [ 0.,  0.,  1.]])


similar_vectors(np.array([1,0,2,3,0,0,1]))

array([[ 0.,  0.,  2.,  3.,  0.,  0.,  1.],
       [ 2.,  0.,  2.,  3.,  0.,  0.,  1.],
       [ 1.,  1.,  2.,  3.,  0.,  0.,  1.],
       [ 1.,  0.,  1.,  3.,  0.,  0.,  1.],
       [ 1.,  0.,  3.,  3.,  0.,  0.,  1.],
       [ 1.,  0.,  2.,  2.,  0.,  0.,  1.],
       [ 1.,  0.,  2.,  4.,  0.,  0.,  1.],
       [ 1.,  0.,  2.,  3.,  1.,  0.,  1.],
       [ 1.,  0.,  2.,  3.,  0.,  1.,  1.],
       [ 1.,  0.,  2.,  3.,  0.,  0.,  0.],
       [ 1.,  0.,  2.,  3.,  0.,  0.,  2.]])

我想以最快的速度实现上述similar_vectors(vector) 函数。它在我的模拟中针对长度为 ~ 几十的 vector 运行了数百万次，因此速度至关重要。我对纯 numpy 解决方案以及其他语言的一些包装器都很感兴趣。代码可以并行。

我目前的实现如下:

def singleOne(length,positionOne): #generates a vector of len length filled with zeros apart from a single one at positionOne
    arr=np.zeros(length)
    arr[positionOne]=1
    return arr

def similar_vectors(state):
    connected=[]
    for i in range(len(state)):
        if(state[i]!=0):
            connected.append(state-singleOne(state.shape[0],i))       
        connected.append(state+singleOne(state.shape[0],i))
    return np.array(connected)

由于我无法轻易摆脱的 for 循环，这非常慢。

作为引用，我附上了 similar_vectors(vector) 的 1000 次执行的配置文件:

         37003 function calls in 0.070 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.070    0.070 {built-in method builtins.exec}
        1    0.003    0.003    0.070    0.070 <string>:2(<module>)
     1000    0.035    0.000    0.064    0.000 <ipython-input-19-69431411f902>:6(similar_vectors)
    11000    0.007    0.000    0.021    0.000 <ipython-input-19-69431411f902>:1(singleOne)
    11000    0.014    0.000    0.014    0.000 {built-in method numpy.core.multiarray.zeros}
     2000    0.009    0.000    0.009    0.000 {built-in method numpy.core.multiarray.array}
    11000    0.002    0.000    0.002    0.000 {method 'append' of 'list' objects}
     1000    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Answer 1

这是一种矢量化方法。 您可以创建一个 1s 和另一个 -1s 的对角矩阵， 然后将前者添加到原始数组中，将后者单独添加到原始数组不为 0 的位置。然后使用 np.concatenate连接两个 ndarrays:

def similar_vectors(a):
    ones = np.ones(len(a))
    w = np.flatnonzero(a!=0)
    return np.concatenate([np.diag(-ones)[w]+a, np.diag(ones)+a])

---

样本运行

a = np.array([1,0,2,3,0,0,1])
similar_vectors(a)

array([[0., 0., 2., 3., 0., 0., 1.],
       [1., 0., 1., 3., 0., 0., 1.],
       [1., 0., 2., 2., 0., 0., 1.],
       [1., 0., 2., 3., 0., 0., 0.],
       [2., 0., 2., 3., 0., 0., 1.],
       [1., 1., 2., 3., 0., 0., 1.],
       [1., 0., 3., 3., 0., 0., 1.],
       [1., 0., 2., 4., 0., 0., 1.],
       [1., 0., 2., 3., 1., 0., 1.],
       [1., 0., 2., 3., 0., 1., 1.],
       [1., 0., 2., 3., 0., 0., 2.]])

a = np.array([0,0,0])
similar_vectors(a)

array([[1., 0., 0.],
       [0., 1., 0.],
       [0., 0., 1.]])