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

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循环，这非常慢。

作为参考，我附上了1000次执行的配置文件similar_vectors(vector)：

         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连接两个ndarray：

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