MapReduce, Python et NetworkX

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

Question

Je l'ai mis en place une fonction de marche aléatoire non pondéré pour un graphique que je construit en Python en utilisant NetworkX. Ci-dessous un extrait de mon programme qui traite de la marche aléatoire. Ailleurs dans mon programme, j'ai une méthode qui crée le graphique, et j'ai une méthode qui simule différentes méthodes d'essai de graphique personnalisé que je l'ai écrit. L'une de ces méthodes d'essai de deux noeuds graphique capte au hasard dans le graphique et exécute une marche aléatoire entre les deux d'entre eux. Les deux choses qui sont calculées à partir de cette marche aléatoire arrivent sur le temps (le nombre de liens qui sont traversées du départ au point de fin) et le temps de trajet (le nombre de liens traversés de commencer à la fin et revenir au point de départ ). 

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

Mon code pour la marche aléatoire est assez straight-forward parce que je suis juste choisir des nœuds aléatoires jusqu'à ce que le point final soit atteint. Toutefois, cette mise en œuvre actuelle est très lent lorsque je tente courir plusieurs promenades au hasard (je pense que je dois courir un million à un moment donné).

Ma question est: Est-il possible que je peux utiliser Hadoop MapReduce pour paralléliser certaines des opérations qui se déroulent ici pour cette promenade au hasard? Y at-il une meilleure façon pour moi de faire ma marche au hasard?

Était-ce utile?

La solution

Pour répondre à votre question:

  1. Vous devez répondre à la remarque de Ned. Il m'a battu à dire. Expliquez votre code; reviendrons plus tard.

  2. Je ne peux pas imaginer un algorithme de marche qui pourrait être exécuté en parallèle. De par leur nature même, ils sont chacun un processus linéaire; chaque étape dépend de la précédente. Vous ne pouvez pas savoir ce nœud suivant pour sauter sans savoir le nœud précédent (à l'exception du nœud de départ). Si votre code représente en effet une marche aléatoire où les choix sont tous indépendants des précédents, vous avez besoin d'expliquer que dans votre question.

  3. En supposant que chaque marche aléatoire est cependant indépendant, vous peut exécuter plusieurs marches aléatoires simultanément. Nous appelons ce scénario embarassingly parallèle, et c'est une chose très chanceux.

  4. Je ne sais pas pourquoi vous voulez utiliser Hadoop, en particulier, ici. La première étape devrait être, « Puis-je écrire tout cela comme un programme de base et d'utiliser un qsub (ou équivalent) script ferme un tas de pistes de ce programme sur le serveur? » Si la réponse est non, l'étape suivante est, « Puis-je utiliser le Module multitraitement ? » Si vous allez avec multitraitement, vous pouvez jeter un oeil à de multitraitement de Jesse Noller présentation de PyCon 2009 .

Maintenant, en ce qui concerne votre code particulier ...

  1. Vous devez expliquer ce que les noeuds de votre graphique sont. Je suis confus pourquoi vous les traitez comme un dictionnaire (appelant .keys()) sur eux. Si elles sont des dictionnaires, dites-nous ce que les clés et les valeurs. J'espère que vous ne stockez pas les voisins comme des clés là-bas, parce que NetworkX vous donne déjà, via méthode Graph.neighbors() . Si vous stockez les voisins des noeuds dans les nœuds eux-mêmes, vous avez une mauvaise compréhension de la bibliothèque NetworkX. Laissez le graphique faire le travail pour vous.

  2. Vous avez la même logique deux fois dans unweighted_random_walk(), une fois pour le voyage à partir du noeud de départ au noeud de destination, puis de nouveau pour le noeud de destination au noeud de départ. Pourquoi? Tout ce que vous avez besoin est la logique pour une direction. Appelez cette fonction deux fois. Appelez avec les nœuds de départ et de destination comme arguments pour obtenir la direction dans un sens, puis échanger l'ordre des arguments à destination puis commencer à se la promenade l'autre direction. alors vous avez deux appels indépendants, et peuvent maintenant exécuter ces travaux en parallèle.

  3. Ne pas utiliser while True:-pas seulement ici, mais en général. Vous devez toujours indiquer l'état réel qui permet de continuer. par ex., 

    while current_point != ending_point:
    ...

  4. Ne pas retourner une chaîne de l'information, renvoyer les informations directement. par ex., 

    return hitting_time

    Notez que, en suivant mes conseils au point 2 ci-dessus directement, il suffit de retourner le temps de frappe, et la somme des temps d'atteinte pour l'y appel et l'arrière-appel pour obtenir le temps de trajet au total. Pratique, non?

Voir aussi

EDIT:. liens inclus pour les présentations de Jesse Nöller et Disco

Autres conseils

Je ne vois pas comment la carte-réduire peut vous aider. Il est utilisé lorsque vous avez une opération en deux parties: la première partie est un calcul qui peut être effectuée indépendamment sur de nombreux éléments de données, et la deuxième partie est en quelque sorte la combinaison tous ces résultats. Peut-être il y a une façon intelligente d'utiliser la carte-reduce pour aider à cette marche aléatoire, mais je ne le vois pas.

Votre marche aléatoire est complètement aléatoire: il pourrait se retrouver avec de nombreuses boucles, sauts même et-vient entre les deux mêmes noeuds avant de continuer. Peut-être que vous voulez limiter en quelque sorte si vous n'avez pas un si grand espace pour la recherche?

Vous ne devez pas réellement effectuer la marche aléatoire si vous utilisez la formule détaillée dans ce document .

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top