MapReduce, Python и NetworkX

Question

Я внедрил функцию невзвешенного случайного блуждания для графика, который я построил на Python, используя NetworkX. Ниже приведен фрагмент моей программы, касающейся случайного блуждания. В другом месте моей программы у меня есть метод, который создает граф, и у меня есть метод, который имитирует различные пользовательские методы тестирования графа, которые я написал. Один из этих методов тестирования графов выбирает два узла случайно из графика и выполняет произвольное блуждание между ними. Две вещи, которые вычисляются из этой случайной ходьбы, достигают времени (количество ссылок, которые пересекаются от начала до конечной точки) и время коммутации (количество пройденных линий от начала до конца и обратно до начальной точки).

def unweighted_random_walk(starting_point,ending_point, graph): 
    ''' 
    starting_point: String that represents the starting point in the graph 
    ending_point: String that represents the ending point in the graph 
    graph: A NetworkX Graph object 
    ''' 
    ##Begin the random walk 
    current_point=starting_point 
    #current_node=graph[current_point] 
    current_point_neighors=graph.neighbors(current_point) 
    hitting_time=0 

    #Determine the hitting time to get to an arbitrary neighbor of the 
    #starting point 
    while current_point!=ending_point: 
     #pick one of the edges out of the starting_node with equal probs 
     possible_destination=current_point_neighbors[random.randint(0,current_point_neighors)] 
     current_point=possible_destination 
     current_point_neighbors=graph.neighbors(current_point) 
     hitting_time+=1 
    return hitting_time 

Мой код для случайного блуждания является довольно прямо вперед, потому что я просто собирание случайных узлов, пока конечная точка не будет достигнута. Тем не менее, эта текущая реализация очень медленная, когда я пытаюсь запустить несколько случайных блужданий (я думаю, что мне нужно запустить миллион в какой-то момент).

Мой вопрос: есть ли способ, которым я могу использовать Hadoop MapReduce, чтобы распараллелить некоторые из операций, которые происходят здесь для этой случайной ходьбы? Есть ли лучший способ сделать мою случайную прогулку?

Answer 1

Чтобы Ваш вопрос:

1. Вам нужно обратиться комментарий Неда. Он избил меня, чтобы сказать это. Объясните свой код; об этом позже.

2. Я не могу понять алгоритм ходьбы, который можно запустить параллельно. По своей природе каждый из них является линейным процессом; каждый шаг зависит от предыдущего. Вы не можете знать, к какому следующему узлу перейти, не зная предыдущего узла (за исключением стартового узла). Если ваш код действительно представляет собой случайную прогулку, где выбор не зависит от предыдущих, вы должны объяснить это в своем вопросе.

3. Предполагая, что каждое случайное блуждание является независимым, вы, однако, можете может запускать множество случайных блужданий одновременно. Мы называем этот сценарий embarassingly parallel, и это очень удачная вещь.

4. Я понятия не имею, почему вы хотите использовать Hadoop, в частности, здесь. Первым шагом должно быть: «Могу ли я просто написать это как базовую программу и использовать сценарий qsub (или эквивалентный), чтобы обработать кучу прогонов этой программы на сервере?» Если ответ отрицательный, следующий шаг: «Могу ли я использовать multiprocessing module?» Если вы перейдете к многопроцессорной обработке, вы можете взглянуть на Jesse Noller's multiprocessing presentation from PyCon 2009.

Теперь касаемо вашего конкретного кода ...

1. Вы должны объяснить, что узлы в вашем графике есть.Я смущен, почему вы относитесь к ним, как к словарю (называя .keys()). Если они словари, расскажите нам, какие ключи и ценности есть. Я надеюсь, что вы не храните соседей в качестве ключей там, потому что NetworkX уже дает вам это, используя метод Graph.neighbors(). Если вы храните соседей узлов в самих узлах, у вас возникает непонимание библиотеки NetworkX. Пусть график выполнит вашу работу.

2. У вас есть одна и та же логика дважды в unweighted_random_walk(), один раз для поездки от стартового узла к целевому узлу, а затем для целевого узла к стартовому узлу. Зачем? Все, что вам нужно, это логика для одного направления. Вызовите эту функцию дважды. Вызовите его с начальным и целевым узлами в качестве аргументов, чтобы получить направление в одну сторону, а затем поменяйте порядок аргументов в пункт назначения, а затем начните движение в другом направлении. Затем у вас есть два независимых вызова, и теперь они могут запускаться параллельно.

3. Не используйте while True: — не только здесь, но и в целом. Вы всегда должны указывать фактическое состояние, в котором следует продолжать. например,

   while current_point != ending_point: 
       ... 
   

4. Не возвращает строку информации, возвращает информацию непосредственно. например,

   return hitting_time 
   

   Обратите внимание, что, следуя моим советам в пункте 2 непосредственно выше, у вас есть только вернуть время удара, и просуммировать раз ударяя по там-вызова и обратного вызова, чтобы получить общее коммутируют время. Удобно, правда?

Смотрите также

• Disco project для реализации Python доступен MapReduce
• Jesse Noller's presentation on concurrency and distributed computing от PyCon 2009

EDIT: Включенные ссылки на презентации Джесси Ноллер и на дискотеке.

Answer 2

Я не вижу, как может помочь карта-сокращение. Он используется там, где у вас есть операция из двух частей: первая часть - это расчет, который может выполняться независимо на разных элементах данных, а вторая часть каким-то образом объединяет все эти результаты. Возможно, есть умный способ использовать map-reduce, чтобы помочь в этом случайном ходу, но я этого не вижу.

Ваша случайная прогулка абсолютно случайна: она может закончиться множеством циклов, даже прыгая назад и вперед между этими же двумя узлами, прежде чем продолжить. Возможно, вы хотите каким-то образом ограничить его, чтобы у вас не было такого большого пространства для поиска?

Answer 3

Вам не нужно выполнять случайную прогулку, если вы используете формулу, указанную в this paper.