MapReduce, Python und NetworkX

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

Frage

Ich habe eine ungewichtete Irrfahrt Funktion für einen Graphen implementiert, die ich in Python gebaut mit NetworkX. Im Folgenden ist ein Ausschnitt aus meinem Programm, das mit dem Random-Walk beschäftigt. An anderer Stelle in meinem Programm habe ich eine Methode, die das Diagramm erstellt, und ich habe eine Methode, die verschiedene benutzerdefinierte Graph Testverfahren simuliert, die ich geschrieben habe. Eine dieser Graph Testmethoden nimmt zwei Knoten zufällig aus dem Graphen und führt eine Zufallsbewegung zwischen beiden. Die beiden Dinge, die von diesem Random Walk schlagen Zeit berechnet werden (die Anzahl der Links, die von dem Start bis zum Endpunkt durchlaufen werden) und die Zeit pendeln (die Anzahl der durchquerten Links von Start zu beenden und zurück zum Ausgangspunkt ). 

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

Mein Code für die Irrfahrt ist ziemlich geradlinig, weil ich zufällig Knoten gerade bin Kommissionierung bis der Endpunkt erreicht ist. Allerdings ist diese aktuelle Implementierung sehr langsam, wenn ich mehrere Irrfahrten versuchen läuft (ich glaube, ich brauche eine Million an einem gewissen Punkt laufen).

Meine Frage ist: Gibt es eine Möglichkeit, die ich Hadoop MapReduce verwenden können einige der Operationen parallelisieren, die hier für diese Random Walk sind hier los? Gibt es einen besseren Weg für mich, meine Irrfahrt zu tun?

War es hilfreich?

Lösung

Ihre Frage zu beantworten:

  1. Sie müssen Neds Kommentar adressieren. Er schlug mich, es zu sagen. Erklären Sie Ihren Code; dazu später mehr.

  2. Ich kann keinen Fuß Algorithmus ergründen, die parallel ausgeführt werden können. Aufgrund ihrer Art, sind sie jeweils ein linearer Prozess; jeder Schritt ist abhängig von der vorherigen. Sie können nicht wissen, was als nächstes Knoten zu springen, ohne den vorherigen Knoten zu wissen (mit Ausnahme des Startknoten). Wenn in der Tat Ihr Code eine Irrfahrt darstellt, in dem die Entscheidungen, die alle unabhängig von den vorherigen sind, müssen Sie das in Ihrer Frage erklären.

  3. jede Irrfahrt Unter der Annahme, unabhängig sind, aber Sie kann läuft viele Irrfahrten gleichzeitig. Wir nennen dieses Szenario embarassingly parallel , und das ist eine sehr glückliche Sache.

  4. Ich habe keine Ahnung, warum Sie Hadoop nutzen möchten, speziell hier. Der erste Schritt soll sein: „Kann ich dies nur als ein Grundsatzprogramm schreiben und eine qsub (oder gleichwertig) Skript verwenden, um eine Reihe von Versuchen dieses Programms auf den Server Farm aus?“ Wenn die Antwort nein ist, ist der nächste Schritt, „Kann ich die Multiprocessing Modul ?“ Wenn Sie mit Multiprozessing gehen, könnten Sie einen Blick auf Jesse Noller Multiprozessing nehmen wollen Präsentation von PyCon 2009 .

Nun, in Bezug auf Ihren speziellen Code ...

  1. Sie müssen erklären, was die Knoten in Ihrem Diagramm sind. Ich bin verwirrt, warum Sie sie wie ein Wörterbuch (Aufruf .keys()) auf sie sind zu behandeln. Wenn sie Wörterbücher sind, sagen uns, was die Schlüssel und Werte sind. Ich hoffe, dass Sie nicht die Nachbarn als Schlüssel dort zu speichern, weil NetworkX bereits gibt Ihnen, dass über die Graph.neighbors() Methode. Wenn Sie die Nachbarn der Knoten in den Knoten selbst sind zu speichern, haben Sie ein Mißverständnis der NetworkX Bibliothek. Lassen Sie die Grafik tun, um die Arbeit für Sie.

  2. Sie haben die gleiche Logik zweimal in unweighted_random_walk(), einmal für die Reise vom Startknoten zum Zielknoten, dann wieder für den Zielknoten an den Startknoten. Warum? Alles, was Sie brauchen, ist die Logik für eine Richtung. Rufen Sie zweimal diese Funktion. Nennen Sie es mit den Start- und Zielknoten als Argumente die Richtung einer Art und Weise zu bekommen, tauschen dann die Reihenfolge der Argumente Ziel dann starten, die zu Fuß in die andere Richtung zu bekommen. Sie haben dann zwei unabhängige Anrufe und können nun diese parallel ausgeführt werden.

  3. Verwenden Sie keine while True:-nicht nur hier, sondern im Allgemeinen. Sie sollten immer den Ist-Zustand, unter denen zeigen fortzusetzen. z. B. 

    while current_point != ending_point:
    ...

  4. Sie keine Zeichenfolge der Informationen zurückkehren, kehren direkt die Informationen. z. B. 

    return hitting_time

    Beachten Sie, dass 2 durch folgende meinen Rat in Punkt direkt über Sie nur die hitting Zeit zurückkehren, und die Summe der Schlagzeiten für die dort-Call und dem Back-Aufruf die gesamte Zeit pendeln zu erhalten. Praktisch, nicht wahr?

Siehe auch

EDIT:. enthalten Links zu Jesse Noller Präsentationen und Disco

Andere Tipps

Ich sehe nicht, wie Karten reduzieren können Ihnen helfen. Es wird verwendet, in dem Sie einen zweiteiligen Betrieb haben: Der erste Teil eine Berechnung ist, die unabhängig voneinander auf vielen verschiedenen Datenelementen durchgeführt werden kann, und der zweite Teil ist irgendwie alle diese Ergebnisse kombiniert. Vielleicht gibt es eine clevere Art und Weise zu bedienen Karten reduzieren mit dieser Irrfahrt zu helfen, aber ich sehe es nicht.

Ihre Irrfahrt ist völlig zufällig: es mit vielen Schleifen könnte am Ende, auch hin und her zwischen den gleichen zwei Knoten, bevor es weiter Hopping. Vielleicht möchten Sie es irgendwie beschränken, so dass Sie nicht einen Raum so groß suchen?

haben Sie

Sie haben nicht wirklich um die Irrfahrt durchführen, wenn Sie die Formel verwenden detailliert in dieses Papier .

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top