Ускорение выборки на графике

Question

Я недавно работал с выборкой графиков в Python.Мой рабочий пример выглядит так:

for enx, wlen in enumerate(wlen_dist):
    for j in range(wlen):
        node_container = queue.Queue(maxsize=200000000)
        node_container.put(node_name)
        tmp_walk = [] # [node_name]
        while not node_container.empty():
            nod = node_container.get()
            neighs = list(network.neighbors(nod))
            tar = random.choice(neighs)
            node_container.put(tar)
            if len(tmp_walk) > enx+1:
                break
            tmp_walk.append(tar)
       some_container.append(tmp_walk)

, где wlen - количество выборок пути длины enx, и я просто сохраняю прогулки в some_container (здесь это не очень важно).Например, wlen_dist:

[1000,500,100]

, и здесь получается 1000 образцов шага длины два, 500 длины 3 и 100 длины 4.Networkx представляет собой график networkX.Мне было интересно, как можно ускорить такой код, как этот (я новичок в этой части).

Мои идеи:

1. Используйте Numba и оберните отдельные прогулки вметод

2. Как-нибудь использовать Cython

3. Переписать его полностью в C ++ и назвать его как-то

IБуду рад любым идеям и отзывам, спасибо!

Answer 1

Одной идеей, часто используемой при встраивании графа, является идея повторного использования частей случайных блужданий:

Если у вас есть случайное блуждание, посещающее узлы a_1, a_2, a_3, вы можете рассматривать это как одно случайное блуждание длины 3и 2 случайных блуждания длиной 2 (a_1, a_2 и a_2, a_3).

Это можно обобщить для более длительных прогулок, так что ваши случайные обходы длины 4 содержат 2 случайных обхода длины 3 и 3 случайных обхода длины 2.