Для ребра e, какой самый быстрый способ в Python найти множество путей, содержащих e?

Question

Скажем, нам дан набор путей P (одинаковой длины) между источником и приемником и ребром e. В python я представляю это списком списков и парой, то есть

# source = 0, sink = 9
# Path i is giving by P[i]: P[i][j] is the node j.
# Path i is giving then by the edges (P[i][0], P[i][1]), (P[i][1], P[i][2]), (P[i][2], P[i][3]), ...

P = [[0, 1, 3, 5, 7, 9], 
     [0, 1, 4, 6, 8, 9], 
     [0, 1, 3, 6, 8, 9], 
     [0, 1, 3, 5, 8, 9],
     [0, 2, 4, 6, 8, 9]]
# The edge we are looking for is (1, 3)
e = (1, 3)

Поскольку e=(1, 3) содержится в 3 путях, P[0], P[2] и P[3], результат 3.

Вот мое решение:

def count_paths(edge, paths):
    count = 0
    for path in paths:
        edges = [(path[i], path[i + 1]) for i in range(len(path) - 1)]
        if edge in edges:
            count += 1
    return count

Когда число путей велико, эта функция дает tottime из 16.245, используя cProfile. Можем ли мы заставить его работать быстрее, используя, например, numpy?

Answer 1

Преобразовать в массив, нарезать его с одноразовыми смещениями, чтобы искать значения начала и конца приемника вдоль каждой строки, а затем просто суммировать значения для нашего желаемого выхода, все в векторизованном виде -

In [43]: P = np.array(P)

In [44]: ((P[:,:-1]==1) & (P[:,1:]==3)).sum()
Out[44]: 3

Если вам тоже нужны правильные пути, замаскируйте массив с помощью ANY уменьшенной маски строки -

In [16]: P[((P[:,:-1]==1) & (P[:,1:]==3)).any(1)]
Out[16]: 
array([[0, 1, 3, 5, 7, 9],
       [0, 1, 3, 6, 8, 9],
       [0, 1, 3, 5, 8, 9]])