MapReduce, Python e NetworkX

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

Domanda

Ho implementato una funzione random walk non ponderata per un grafico che ho costruito in Python utilizzando NetworkX. Qui di seguito è un frammento del mio programma che si occupa del random walk. Altrove nel mio programma, ho un metodo che crea il grafico, e ho un metodo che simula vari metodi di prova grafico personalizzato che ho scritto. Uno di questi metodi di prova grafico raccoglie due nodi a caso dal grafico e gestisce un random walk tra ciascuno di essi. Le due cose che vengono calcolati da questo Random Walk stanno colpendo tempo (il numero di collegamenti che sono attraversati dalla partenza per il punto finale) e il tempo di pendolarismo (il numero di link attraversati da iniziare a finire e tornare al punto di partenza ). 

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

Il mio codice per la passeggiata casuale è abbastanza straight-forward, perché io sono solo raccogliendo i nodi casuali fino a raggiungere il punto finale. Tuttavia, questa implementazione corrente è molto lento quando provo in esecuzione diverse passeggiate aleatorie (Penso di aver bisogno di eseguire un milione a un certo punto).

La mia domanda è: C'è un modo che posso usare Hadoop MapReduce per parallelizzare alcune delle operazioni che sono in corso qui per questa passeggiata a caso? C'è un modo migliore per me di fare il mio cammino casuale?

È stato utile?

Soluzione

Per rispondere alla tua domanda:

  1. È necessario affrontare il commento di Ned. Mi ha battuto per dirlo. Spiega il codice; ne riparleremo più avanti.

  2. Non riesco a capire un algoritmo a piedi che potrebbe essere eseguito in parallelo. Per loro natura, sono ciascuno un processo lineare; ogni passaggio dipende dalla precedente. Non puoi sapere quale nodo successivo per passare senza conoscere il nodo precedente (con l'eccezione del nodo di partenza). Se il Codice rappresenta infatti un random walk, dove le scelte sono tutti indipendenti di quelli precedenti, è necessario spiegare che nella sua domanda.

  3. Supponendo che ogni random walk è indipendente, tuttavia, è può eseguire molti casuale passeggiate contemporaneamente. Noi chiamiamo questo scenario embarassingly paralleli , e questa è una cosa molto fortunato.

  4. Non ho idea del motivo per cui si desidera utilizzare Hadoop, in particolare, qui. Il primo passo dovrebbe essere: "Posso solo scrivere questo come un programma di base e utilizzare un QSUB (o equivalente) script per coltivare un mazzo di piste di questo programma al server?" Se la risposta è no, il passo successivo è, "Posso usare il modulo multiprocessing ?" Se si va con il multiprocessing, si potrebbe desiderare di dare un'occhiata a multiprocessing di Jesse Noller presentazione da PyCon 2009 .

Ora, per quanto riguarda il codice particolare ...

  1. È necessario spiegare che cosa i nodi nel grafico sono. Sono confuso il motivo per cui li stai trattando come un dizionario (.keys() chiamata) su di loro. Se sono dizionari, ci dicono che le chiavi ei valori sono. Spero che non stanno memorizzando i vicini come chiavi lì, perché NetworkX ti dà già che, tramite il metodo Graph.neighbors() . Se sei memorizzare i vicini dei nodi nei nodi stessi, si dispone di un malinteso della biblioteca NetworkX. Lasciate che il grafico fare il lavoro per voi.

  2. Hai la stessa logica per due volte in unweighted_random_walk(), una volta per il viaggio dal nodo di partenza al nodo di destinazione, poi di nuovo per il nodo di destinazione al nodo di partenza. Perché? Tutto ciò che serve è la logica per una sola direzione. Chiamare questa funzione due volte. Chiamatelo con i nodi di partenza e di destinazione come argomenti per ottenere il modo in direzione uno, poi scambiare l'ordine degli argomenti per essere destinazione quindi iniziare a ottenere la passeggiata nella direzione opposta. Devi quindi due chiamate indipendenti, ed è ora possibile eseguire questi in parallelo.

  3. Non utilizzare while True:-non solo qui, ma in generale. Si dovrebbe sempre indicare la reale condizione in cui continuare. per es., 

    while current_point != ending_point:
    ...

  4. Non restituire una stringa di informazioni, tornare direttamente le informazioni. per es., 

    return hitting_time

    Si noti che, seguendo il mio consiglio al punto 2 direttamente al di sopra, è sufficiente restituire il tempo di colpire, e somma i tempi che colpiscono per la non-chiamata e il back-chiamata per ottenere il tempo totale di pendolari. Comodo, no?

Si veda anche

EDIT:. link incluso per le presentazioni di Jesse Noller e alla disco

Altri suggerimenti

Non vedo come mappa-ridurre ti può aiutare. E 'utilizzato dove si ha un'operazione in due parti: la prima parte è un calcolo che può essere eseguita indipendentemente su molti elementi di dati diversi, e la seconda parte è in qualche modo unisce tutti questi risultati. Forse c'è un modo intelligente di usare carta-ridurre per aiutare con questo percorso casuale, ma io non lo vedo.

La vostra passeggiata aleatoria è del tutto casuale: si potrebbe finire con molti loop, anche saltellando avanti e indietro tra gli stessi due nodi prima di proseguire. Forse si desidera vincolare in qualche modo non si dispone di così grande uno spazio per la ricerca?

Non è necessario eseguire in realtà la passeggiata casuale se si utilizza la formula dettagliato in questo documento .

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top