我有许多城镇和它们的邻居。我想得到一组至少有一条路线由两条不同的边组成的城镇对。有没有矢量化的方法可以做到这一点?若否,原因为何?例如:edges[3,0], [0,4], [5,0]
有一个事件节点0,因此保证[3,4], [4,5], [3,5]
是可以通过如下路径连接的城镇对:3-0-4
、4-0-5
和3-0-5
。它们由两条边组成
输入示例:np.array([[3,0], [0,4], [5,0], [2,1], [1,4], [2,3], [5,2]])
预期输出:array([4,3], [4,5], [3,5], [4,2], [1,3], [1,5], [3,5], [0,2], [0,1], [0,2])
(如果顺序不同、任何边缘方向颠倒或存在重复,则无需担心)
到目前为止,我所做的是:
from itertools import chain, combinations
def get_incidences(roads):
roads = np.vstack([roads, roads[:,::-1]])
roads_sorted = roads[np.argsort(roads[:,0])]
marker_idx = np.flatnonzero(np.diff(roads_sorted[:,0]))+1
source = roads_sorted[np.r_[marker_idx-1,-1],0]
target = np.split(roads_sorted[:,1], marker_idx)
return source, target
def get_combinations_chain(target):
#I know this could be improved with `np.fromiter`
return np.array(list(chain(*[combinations(n,2) for n in target])))
def get_combinations_triu(target):
def combs(t):
x, y = np.triu_indices(len(t),1)
return np.transpose(np.array([t[x], t[y]]))
return np.concatenate([combs(n) for n in target])
roads = np.array([[3,0], [0,4], [5,0], [2,1], [1,4], [2,3], [5,2]])
>>> get_incidences(roads)
(array([0, 1, 2, 3, 4, 5]),
[array([4, 3, 5]),
array([4, 2]),
array([1, 3, 5]),
array([0, 2]),
array([0, 1]),
array([0, 2])])
>>> get_combinations_chain(get_incidences(roads)[1])
array([[4, 3], [4, 5], [3, 5], [4, 2], [1, 3], [1, 5], [3, 5], [0, 2], [0, 1], [0, 2]])
>>> get_combinations_triu(get_incidences(roads)[1])
array([[4, 3], [4, 5], [3, 5], [4, 2], [1, 3], [1, 5], [3, 5], [0, 2], [0, 1], [0, 2]])
最后两个给出了预期的输出,但它们需要列表理解。是否可以将此计算矢量化:
np.concatenate([combs(n) for n in target])
更新我以一种可能的矢量化方式结束,但我需要重新组织输入数据(输出get_incidences
):
INPUT:
target: [array([4, 3, 5]), array([4, 2]), array([1, 3, 5]), array([0, 2]), array([0, 1]), array([0, 2])]
stream: [4 3 5 4 2 1 3 5 0 2 0 1 0 2]
lengths: [3 2 3 2 2 2]
OUTPUT:
array([[3, 4], [4, 5], [3, 5], [2, 4], [1, 3], [1, 5], [3, 5], [0, 2], [0, 1], [0, 2]])
它似乎也比所有组合的直接串联更快:
def get_incidences(roads):
roads = np.vstack([roads, roads[:,::-1]])
roads_sorted = roads[np.argsort(roads[:,0])]
marker_idx = np.flatnonzero(np.diff(roads_sorted[:,0]))+1
lengths = np.diff(marker_idx, prepend=0, append=len(roads_sorted))
stream = roads_sorted[:,1]
target = np.split(stream, marker_idx)
return target, stream, lengths
def get_combinations_vectorized(data):
target, stream, lengths = data
idx1 = np.concatenate(np.repeat(target, lengths))
idx2 = np.repeat(stream, np.repeat(lengths, lengths))
return np.array([idx1, idx2]).T[idx1 < idx2]
def get_combinations_triu(data):
target, stream, lengths = data
def combs(t):
x, y = np.triu_indices(len(t),1)
return np.transpose(np.array([t[x], t[y]]))
return np.concatenate([combs(n) for n in target])
def get_combinations_chain(data):
target, stream, lengths = data
return np.array(list(chain(*[combinations(n,2) for n in target])))
def get_combinations_scott(data):
target, stream, lengths = data
return np.array([x for i in target for x in combinations(i,2)])
def get_combinations_index(data):
target, stream, lengths = data
index = np.fromiter(chain.from_iterable(chain.from_iterable(combinations(n,2) for n in target)),
dtype=int, count=np.sum(lengths*(lengths-1)))
return index.reshape(-1,2)
roads = np.array([[64, 53], [94, 90], [24, 60], [45, 44], [83, 17], [10, 88], [14, 6], [56, 93], [98, 93], [86, 77], [12, 85], [58, 2], [19, 80], [48, 26], [11, 51], [16, 83], [45, 96], [35, 54], [47, 23], [81, 57], [52, 34], [88, 11], [18, 4], [35, 90], [41, 45], [2, 7], [58, 68], [58, 11], [46, 38], [32, 93], [44, 41], [26, 39], [20, 58], [44, 4], [8, 96], [74, 71], [34, 35], [91, 72], [28, 58], [53, 73], [66, 5], [84, 97], [24, 29], [43, 63], [96, 63], [20, 57], [1, 74], [4, 89], [10, 89], [98, 22]])
data = get_incidences(roads)
%timeit get_combinations_vectorized(data)
%timeit get_combinations_chain(data)
%timeit get_combinations_triu(data)
%timeit get_combinations_scott(data)
%timeit get_combinations_index(data)
92 µs ± 18.3 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
123 µs ± 3.67 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
1.8 ms ± 9.44 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
126 µs ± 2.45 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
140 µs ± 4.48 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
然而,这在很大程度上取决于数据。roads = np.array(list(combinations(range(100),2)))
的计时
44.2 ms ± 4.36 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
277 ms ± 8.26 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
21.2 ms ± 1.84 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)
369 ms ± 17.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
43.2 ms ± 911 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
您可以使用networkx库:
输出:
根据评论
将此语句向量化:
np.concatenate([combs(n) for n in target])
:对于
t = get_incidences(roads)[1]
输出s2:
然后
输出s1:
和,(s1==s2)。全部()
时间:
相关问题 更多 >
编程相关推荐