MapReduce, Python e NetworkX

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

Pergunta

Implementei uma função de passeio aleatório não ponderado para um gráfico que construí em Python usando NetworkX.Abaixo está um trecho do meu programa que trata do passeio aleatório.Em outras partes do meu programa, tenho um método que cria o gráfico e um método que simula vários métodos de teste de gráfico personalizado que escrevi.Um desses métodos de teste de gráfico escolhe dois nós aleatoriamente do gráfico e executa um passeio aleatório entre ambos.As duas coisas que estão sendo calculadas a partir deste passeio aleatório são o tempo de acerto (o número de links que são percorridos do ponto inicial ao ponto final) e o tempo de deslocamento (o número de links percorridos do início ao fim e de volta ao ponto inicial ). 

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

Meu código para o passeio aleatório é bastante simples porque estou apenas escolhendo nós aleatórios até que o ponto final seja alcançado.No entanto, esta implementação atual é muito lenta quando tento executar vários passeios aleatórios (acho que preciso executar um milhão em algum momento).

Minha pergunta é:Existe alguma maneira de usar o Hadoop MapReduce para paralelizar algumas das operações que estão acontecendo aqui neste passeio aleatório?Existe uma maneira melhor de fazer minha caminhada aleatória?

Foi útil?

Solução

Para responder à sua pergunta:

  1. Você precisa abordar o comentário de Ned.Ele me venceu ao dizer isso.Explique seu código;mais sobre isso mais tarde.

  2. Não consigo imaginar um algoritmo ambulante que possa ser executado em paralelo.Pela sua própria natureza, cada um deles é um processo linear;cada etapa depende da anterior.Você não pode saber para qual próximo nó pular sem conhecer o nó anterior (com exceção do nó inicial).Se o seu código realmente representa um passeio aleatório onde as escolhas são todas independentes das anteriores, você precisa explicar isso na sua pergunta.

  3. Supondo que cada passeio aleatório seja independente, no entanto, você pode execute muitas caminhadas aleatórias simultaneamente.Chamamos esse cenário embaraçosamente paralelo, e isso é uma coisa de muita sorte.

  4. Não tenho ideia de por que você deseja usar o Hadoop, especificamente, aqui.O primeiro passo deve ser: "Posso apenas escrever isso como um programa básico e usar um script QSUB (ou equivalente) para cultivar várias corridas deste programa para o servidor?" Se a resposta for não, o próximo passo é: "Posso usar o módulo de multiprocessamento?" Se você optar pelo multiprocessamento, talvez queira dar uma olhada em Apresentação de multiprocessamento de Jesse Noller na PyCon 2009.

Agora, com relação ao seu código específico...

  1. Você precisa explicar quais são os nós do seu gráfico.Estou confuso por que você os está tratando como um dicionário (ligando para .keys()) neles.Se forem dicionários, diga-nos quais são as chaves e os valores.Espero que você não esteja armazenando os vizinhos como chaves aí, porque o NetworkX já te dá isso, através do Graph.neighbors() método.Se você estiver armazenando os vizinhos dos nós nos próprios nós, você não entendeu a biblioteca NetworkX.Deixe o gráfico fazer o trabalho para você.

  2. Você tem a mesma lógica duas vezes em unweighted_random_walk(), uma vez para a viagem do nó inicial ao nó de destino e, novamente, do nó de destino ao nó inicial.Por que?Tudo que você precisa é a lógica para uma direção.Chame esta função duas vezes.Chame-o com os nós de início e destino como argumentos para obter a direção em uma direção, depois troque a ordem dos argumentos para ser o destino e comece a caminhar na outra direção.Você terá então duas chamadas independentes e agora poderá executá-las em paralelo.

  3. Não use while True:– não apenas aqui, mas em geral.Você deve sempre indicar a condição real sob a qual deseja continuar.por exemplo.,

    while current_point != ending_point:
    ...

  4. Não retorne uma sequência de informações, retorne as informações diretamente.por exemplo.,

    return hitting_time

    Observe que, seguindo meu conselho no ponto 2 diretamente acima, você só precisa retornar o tempo de acerto e somar os tempos de acerto da chamada e da chamada de retorno para obter o tempo total de deslocamento.Conveniente, certo?

Veja também

EDITAR: Links incluídos para apresentações de Jesse Noller e para Disco.

Outras dicas

Não vejo como a redução de mapa pode ajudá-lo.É usado quando você tem uma operação em duas partes:a primeira parte é um cálculo que pode ser realizado de forma independente em muitos elementos de dados diferentes, e a segunda parte combina de alguma forma todos esses resultados.Talvez haja uma maneira inteligente de usar a redução de mapa para ajudar nesse passeio aleatório, mas não vejo isso.

Seu passeio aleatório é completamente aleatório:poderia acabar com muitos loops, até mesmo alternando entre os mesmos dois nós antes de continuar.Talvez você queira restringi-lo de alguma forma para não ter um espaço tão grande para pesquisar?

Você não precisa realmente realizar o passeio aleatório se usar a fórmula detalhada em este papel.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top