假设有两个数组I和J，它们确定了相邻的配对：
I = np.array([0, 0, 1, 2, 2, 3])
J = np.array([1, 2, 0, 0, 3, 2])
0有两个邻居1和2。元素1只有0作为邻居，依此类推。I'、J'、K'的数组，使得在条件i、j和k为不同元素(i != j != k)的情况下，j是i的邻居，k是j的邻居，最有效的方法是什么？Ip = np.array([0, 0, 2, 3])
Jp = np.array([2, 2, 0, 2])
Kp = np.array([0, 3, 1, 0])
当然，一种方法是遍历每个元素。有没有更有效率的算法？（处理1000万到5亿个元素）
我会采用非常简单的方法，使用pandas（I 和 J 是您的numpy数组）：
import pandas as pd
df1 = pd.DataFrame({'I': I, 'J': J})
df2 = df1.rename(columns={'I': 'K', 'J': 'I'})
result = pd.merge(df2, df1, on='I').query('K != J')
pandas.merge 依赖于非常快速的底层数值实现。此外，您可以通过使用索引进行合并来进一步加快计算速度。df1 和 df2 的大小（例如，通过将列的 dtype 更改为适合您的需要的内容）。from timeit import timeit
import numpy as np
import pandas as pd
I = np.random.randint(0, 10000, 1000000)
J = np.random.randint(0, 10000, 1000000)
df1_64 = pd.DataFrame({'I': I, 'J': J})
df1_32 = df1_64.astype('int32')
df2_64 = df1_64.rename(columns={'I': 'K', 'J': 'I'})
df2_32 = df1_32.rename(columns={'I': 'K', 'J': 'I'})
timeit(lambda: pd.merge(df2_64, df1_64, on='I').query('K != J'), number=1)
# 18.84
timeit(lambda: pd.merge(df2_32, df1_32, on='I').query('K != J'), number=1)
# 9.28
这是使用networkx提供的初始解决方案，它是一个优化的图计算库：
import numpy as np
import networkx as nx
I = np.array([0, 0, 1, 2, 2, 3])
J = np.array([1, 2, 0, 0, 3, 2])
I_, J_, K_ = [], [], [],
num_nodes = np.max(np.concatenate([I,J])) + 1
A = np.zeros((num_nodes, num_nodes))
A[I,J] = 1
print("Adjacency Matrix:")
print(A)
G = nx.from_numpy_matrix(A)
for i in range(num_nodes):
first_neighbors = list(G.neighbors(i))
for j in first_neighbors:
second_neighbor = list(G.neighbors(j))
second_neighbor_no_circle = list(filter(lambda node: node != i, second_neighbor))
num_second_neighbors = len(second_neighbor_no_circle)
if num_second_neighbors > 0:
I_.extend(num_second_neighbors * [i])
J_.extend(num_second_neighbors * [j])
K_.extend(second_neighbor_no_circle)
I_, J_, K_ = np.array(I_), np.array(J_), np.array(K_)
print("result:")
print(I_)
print(J_)
print(K_)
####### Output #######
Adjacency Matrix:
[[0. 1. 1. 0.]
[1. 0. 0. 0.]
[1. 0. 0. 1.]
[0. 0. 1. 0.]]
result:
[0 1 2 3]
[2 0 0 2]
[3 2 1 0]
我对上面的代码使用了%%timeit而没有打印语句来检查运行时间：49 µs ± 113 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
复杂度分析： 找到所有邻居的邻居本质上是在深度优先搜索算法中进行2步。这可能需要，取决于图的拓扑结构，最多O(|V| + |E|)，其中|E|是图中的边数，|V|是顶点数。
据我所知，在一般图上没有更好的算法。 但是，如果您知道有关图的某些特殊属性，则可以更紧密地限制运行时间或者根据此知识改变当前算法。
例如，如果您知道所有顶点最多具有d条边，并且图具有一个连通组件，则此实现的界限变为O(2d)，如果d << |E|，则相当不错。
如果您有任何问题，请告诉我。
import networkx as nx
def findPaths(G,u,n):
"""Returns a list of all paths of length `n` starting at vertex `u`."""
if n==1:
return [[u]]
paths = [[u]+path for neighbor in G.neighbors(u) for path in findPaths(G,neighbor,n-1) if u not in path]
return paths
# Generating graph
vertices = np.unique(I)
edges = list(zip(I,J))
G = nx.Graph()
G.add_edges_from(edges)
# Grabbing all 3-paths
paths = [path for v in vertices for path in findPaths(G,v,3)]
paths
>>> [[0, 2, 3], [1, 0, 2], [2, 0, 1], [3, 2, 0]]
生成所有三元组的算法并没有什么特别神奇的方法。您可以通过有序搜索来避免重新获取节点的邻居，但仅限于此。
这有所帮助吗？仍然需要处理算法中的一些细节，例如避免重复生成和移动团的要点。
networkx或其他图形包。让包来处理你的效率问题。 - Prune