MapReduce, Python y NetworkX

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

Pregunta

He implementado una ponderada caminata aleatoria función de un gráfico en el que he construido en Python usando NetworkX.A continuación es un fragmento de mi programa que se ocupa de la caminata aleatoria.En otro lugar en mi programa, yo tengo un método que crea el gráfico, y tengo un método que simula varios personalizado gráfico métodos de ensayo que he escrito.Uno de estos gráfica de los métodos de prueba escoge dos nodos al azar de la gráfica y se ejecuta un paseo aleatorio entre ambos.Las dos cosas que se calculan a partir de este Paseo Aleatorio están golpeando el tiempo (el número de enlaces que se recorren desde la partida hasta el punto final) y el tiempo de viaje (el número de recorrido enlaces de inicio para terminar y volver al punto de partida). 

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

Mi código para la caminata aleatoria es bastante recta hacia adelante, porque estoy escoger al azar los nodos hasta el punto final se alcanza.Sin embargo, esta implementación actual es muy lento cuando trato de ejecutar varios caminos aleatorios (creo que tengo que ejecutar un millón en algún momento).

Mi pregunta es:Hay alguna manera de que yo pueda utilizar Hadoop MapReduce para paralelizar algunas de las operaciones que se van de aquí para este Paseo Aleatorio?Existe una mejor manera para mí para hacer mi caminata al azar?

¿Fue útil?

Solución

A la dirección de tu pregunta:

  1. Usted necesita la dirección de Ned comentario.Él me pegaba a decirlo.Explique su código;más sobre esto más adelante.

  2. No puedo imaginar una caminata a un algoritmo que se puede ejecutar en paralelo.Por su propia naturaleza, cada una de ellas es un proceso lineal;cada paso depende de la anterior.Usted no puede saber lo siguiente nodo a saltar sin saber el nodo anterior (con la excepción de el nodo inicial).Si su código, de hecho, representa una caminata al azar, donde las decisiones son independientes de las anteriores, es necesario explicar que en su pregunta.

  3. Suponiendo que cada paseo aleatorio es independiente, sin embargo, usted puede ejecutar muchos caminos aleatorios de forma simultánea.Llamamos a este escenario embarassingly paralelo, y eso es una gran suerte la cosa.

  4. No tengo idea de por qué usted desea utilizar Hadoop, específicamente, aquí.El primer paso debe ser, "puedo escribir esto como un programa básico y el uso de un qsub (o equivalente) de secuencia de comandos a la granja a cabo un montón de carreras de este programa en el servidor?" Si la respuesta es no, el siguiente paso es, "¿puedo usar el módulo de multiprocesamiento?" Si usted va con el multiprocesamiento, es posible que desee echar un vistazo a Jesse Noller del multiprocesamiento presentación de PyCon argentina 2009.

Ahora, con respecto a su particular código de...

  1. Usted necesita explicar lo que los nodos en el gráfico.Estoy confundido ¿por qué estás tratando como un diccionario (llamando .keys()) en ellos.Si son los diccionarios, nos dicen lo que las claves y valores.Espero que no eres el almacenamiento de los vecinos como las teclas de allí, porque NetworkX da ya que, a través de la Graph.neighbors() método.Si usted está almacenando los vecinos de los nodos en los propios nodos, usted tiene una mala interpretación de la NetworkX de la biblioteca.Deje que el gráfico de hacer el trabajo por usted.

  2. Tiene la misma lógica de dos veces en unweighted_random_walk(), una vez para el viaje desde el nodo inicial hasta el nodo de destino, a continuación, de nuevo por el nodo de destino para el nodo de inicio.Por qué?Todo lo que necesita es la lógica de una dirección.Llamar a esta función dos veces.Llamar con el inicio y el destino de los nodos como argumentos para obtener la dirección de un camino, para luego intercambiar el orden de los argumentos de destino, a continuación, empezar a tener el pie en el otro sentido.Entonces tienes dos llamadas independientes, y ahora se pueden ejecutar estos en paralelo.

  3. No uso while True:—no sólo aquí, sino en general.Siempre se debe indicar el estado real en el que se debe seguir.por ejemplo,

    while current_point != ending_point:
    ...

  4. No devolver una cadena de la información, devolver la información directamente.por ejemplo,

    return hitting_time

    Tenga en cuenta que siguiendo mis consejos en el punto 2 anterior, usted sólo tiene que devolver el golpear de tiempo, y suma el golpear de los tiempos para el no-llamada y la llamada para obtener el total de tiempo de viaje.Conveniente, ¿no?

Ver también

EDITAR: Incluye enlaces a Jesse Noller las presentaciones y a la Discoteca.

Otros consejos

No veo la manera de reducir el mapa te puede ayudar.Se utiliza cuando se tienen las dos partes de la operación:la primera parte es un cálculo que se pueden realizar de forma independiente en diferentes elementos de datos, y la segunda parte es de alguna manera la combinación de todos estos resultados.Tal vez hay una forma inteligente de utilizar reducir el mapa para ayudar con este paseo aleatorio, pero yo no lo veo.

Su paseo aleatorio es completamente al azar:se podría acabar con muchos bucles, incluso saltando de ida y vuelta entre dos nodos antes de continuar.Tal vez usted quiere de alguna manera limitan por lo que no tiene tan gran espacio para buscar?

Usted no tiene que realmente realizan la caminata al azar si usted usa la fórmula detallada en este papel.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top