问题描述
l需要解决什么问题?
从索引列表构建二进制矩阵。 下面是l的处理方式,但l希望找到一种有效的方法来避免循环输入:
list_indices =[
[0,3,4],
[2,1,0],
[3,5]
]
预期产量:
results=[
[0,1,1,1,1,0],
[1,0,1,0,0,0],
[0,0,0,0,0,0],
[1,0,0,0,1,1],
[1,0,0,1,0,0],
[0,0,1,0,0,0],
]
结果对应于从索引列表构建的二进制邻接(对称)矩阵。结果中的1对应于属于LIST_INDEX同一行的一对索引。
LIST_INDEX中的对为:
row 1 : (0,3), (3,0), (0,4),(4,0), (3,4), (4,3)
row 2 : (0,1), (1,0), (2,0), (0,2),(1,2), (2,1)
row 3 : (3,5), (5,3)
number of column and number of rows in results = np.max(list_indices)+1=6
l尝试过什么?
results=np.zeros((np.max(list_indices)+1,np.max(list_indices)+1))
for pair in itertools.combinations(list_indices, r=2) :
results[pair[0],pair[1]]=results[pair[1],pair[0]]=1.0
构建它的有效方法是什么?(避免循环)
itertools.combinations
返回一个配对列表,然后使用该列表填充矩阵结果。因为该矩阵是对称的,所以迭代式组合提供了对应于上对角线矩阵的对的列表。对角线设置为零
推荐答案
此问题与我10天前的调查discussed密切相关,因此我将在此处发布最重要发现的摘要。
将社区存储为长度不平衡的列表会强制使用迭代或串联,这是低效的。相反,您可以使用单个数组,并按如下方式计算:
flow = [0,3,4,2,1,0,3,5]
counts = [3,3,2]
单一组合的更快方法是np.triu_indices
方法,而不是itertools.combinations
:
def combs(t):
x, y = np.triu_indices(len(t), 1)
return np.transpose([t[x], t[y]])
在我的解决方案中指出,您正在研究如何避免中的串联和列表理解:
np.concatenate([combs(n) for n in list_indices])
或者(from itertools import*
):
np.array(list(chain(*[combinations(n,2) for n in list_indices])))
我根据您的输入找到了几种将其矢量化的方法:
def repeat_blocks(a, sizes, repeats):
#Thanks @Divakar: https://stackoverflow.com/a/51156138/3044825
r1 = np.repeat(np.arange(len(sizes)), repeats)
N = (sizes*repeats).sum() # or np.dot(sizes, repeats)
id_ar = np.ones(N, dtype=int)
id_ar[0] = 0
insert_index = sizes[r1[:-1]].cumsum()
insert_val = (1-sizes)[r1[:-1]]
insert_val[r1[1:] != r1[:-1]] = 1
id_ar[insert_index] = insert_val
out = a[id_ar.cumsum()]
return out
def concat_combs1(flow, counts):
#way 1 based on repetition of blocks of consecutive items
col1 = repeat_blocks(flow, counts, counts)
col2 = np.repeat(flow, np.repeat(counts, counts))
return np.transpose([col1, col2])[col1 < col2]
def concat_combs2(targets, counts):
#way 2 based on repetition of blocks dissociated from each other
counts = list(map(len, targets))
col1 = np.concatenate(np.repeat(targets, counts, axis=0))
col2 = np.repeat(np.concatenate(targets), np.repeat(counts, counts))
return np.transpose([col1, col2])[col1 < col2]
测试:
list_indices = [np.array([0,3,4]), np.array([2,1,0]), np.array([3,5])]
flow = np.array([0,3,4,2,1,0,3,5])
counts = np.array([3, 3, 2])
# Usage:
np.concatenate([combs(n) for n in list_indices])
concat_combs1(flow, counts)
concat_combs2(list_indices)
输出:
array([[0, 3],
[0, 4],
[3, 4],
[1, 2],
[0, 2],
[0, 1],
[3, 5]])
结论
perfplot
在igraph.Graph.Barabasi(n = x, m = 3)
上有四种方法,包括itertools.combinations
和np.triu_indices
。这个图的每个顶点平均有3个邻居。总而言之,connection of repeated consecutive blocks效果最好。目前,NumPy数组的串联速度比链接组合的速度要慢,因为要串联大量的小列表。
最终解决方案
为了以最快的方式构建关联矩阵,您需要应用concat_combs1
方法的一个小变体:
flow = np.array([0,3,4,2,1,0,3,5])
counts = np.array([3,3,2])
results = np.zeros((np.max(flow)+1, np.max(flow)+1), dtype=int)
col1 = repeat_blocks(flow, counts, counts)
col2 = np.repeat(flow, np.repeat(counts, counts))
results[col1, col2] = 1
np.fill_diagonal(results, 0)
输出
[[0 1 1 1 1 0]
[1 0 1 0 0 0]
[1 1 0 0 0 0]
[1 0 0 0 1 1]
[1 0 0 1 0 0]
[0 0 0 1 0 0]]