MapReduce, Python и NetworkX

StackOverflow https://stackoverflow.com/questions/1694237

Вопрос

Я реализовал невзвешенную функцию случайного блуждания для графика, который построил на 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 для распараллеливания некоторых операций, которые происходят здесь для этого случайного обхода?Есть ли лучший способ совершить случайное блуждание?

Это было полезно?

Решение

Чтобы ответить на ваш вопрос:

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

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

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

  4. Я понятия не имею, почему вы хотите использовать Hadoop именно здесь.Первым шагом должен быть: «Могу ли я просто написать это в качестве базовой программы и использовать сценарий QSUB (или эквивалент), чтобы вывести кучу прогонов этой программы на сервер?» Если ответ нет, следующим шагом является: «Могу ли я использовать многопроцессорный модуль?" Если вы используете многопроцессорную обработку, возможно, вам стоит взглянуть на Презентация Джесси Ноллера о многопроцессорности на 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 выше, вам нужно только вернуть время срабатывания и суммировать время срабатывания для обратного вызова и обратного вызова, чтобы получить общее время в пути.Удобно, правда?

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

РЕДАКТИРОВАТЬ: Включены ссылки на презентации Джесси Ноллера и на дискотеку.

Другие советы

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top