algoritmo de passagem boa gráfico

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

Pergunta

problema Resumo: Eu tenho um gráfico de cerca de 250.000 nós ea conectividade média é de cerca de 10. Encontrando conexões de um nó é um processo longo (10 segundos permite dizer). Salvando um nó para o banco de dados também leva cerca de 10 segundos. Posso verificar se um nó já está presente no db muito rapidamente. Permitindo a simultaneidade, mas não ter mais de 10 longas pedidos de uma só vez, como você atravessar o gráfico para obter a maior cobertura o mais rápido.

problema concreto: Eu estou tentando raspar um site páginas de usuário. Para descobrir novos usuários Estou ao obter a lista amigo dos usuários já conhecidos. Eu já importou cerca de 10% do gráfico, mas eu continuo recebendo presos em ciclos ou usando muita memória lembrando muitos nós.

Meu atual implementação: 

def run() :
    import_pool = ThreadPool(10)
    user_pool = ThreadPool(1)
    do_user("arcaneCoder", import_pool, user_pool)

def do_user(user, import_pool, user_pool) :
    id = user
    alias = models.Alias.get(id)

    # if its been updates in the last 7 days
    if alias and alias.modified + datetime.timedelta(days=7) > datetime.datetime.now() :
        sys.stderr.write("Skipping: %s\n" % user)
    else :
        sys.stderr.write("Importing: %s\n" % user)
        while import_pool.num_jobs() > 20 :
            print "Too many queued jobs, sleeping"
            time.sleep(15)

        import_pool.add_job(alias_view.import_id, [id], lambda rv : sys.stderr.write("Done Importing %s\n" % user))

    sys.stderr.write("Crawling: %s\n" % user)
    users = crawl(id, 5)
    if len(users) >= 2 :
        for user in random.sample(users, 2) :
            if (user_pool.num_jobs() < 100) :
                user_pool.add_job(do_user, [user, import_pool, user_pool])

def crawl(id, limit=50) :
    '''returns the first 'limit' friends of a user'''
    *not relevant*

Os problemas de implementação atual:

  • fica preso em panelinhas que eu já importados, desperdiçando assim tempo e os fios importadores estão ociosos.
  • irá adicionar mais à medida que se destacou.

Assim, melhoramentos marginais são bem-vindos, bem como regravações completos. Obrigado!

Foi útil?

Solução

Para lembrar IDs dos usuários que você já visitou, você precisa de um mapa de um comprimento de 250.000 inteiros. Isso está longe de ser "demasiado". Apenas manter um tal mapa e só atravessar as arestas que levam aos usuários já descoberto, adicionando-os ao que o mapa no ponto de encontrar tais borda.

Como até onde posso ver, você está perto de implementar em largura de pesquisa (BFS). Verifique google sobre os detalhes deste algoritmo. E, claro, não se esqueça sobre mutexes -. Você vai precisar deles

Outras dicas

Estou realmente confuso sobre o porquê ele leva 10 segundos para adicionar um nó para o DB. Isso soa como um problema. O banco de dados você está usando? Você tem restrições de plataforma graves?

Com os sistemas modernos, e seus grande quantidade de memória, eu recomendaria um cache simples agradável de algum tipo. Você deve ser capaz de criar um cache muito rápido de informações do usuário que lhe permitiria evitar o trabalho repetido. Quando você encontrou um já nó, processamento stop. Isso irá evitar ciclismo para sempre em cliques.

Se você precisa para permitir a requentar nós existentes depois de um tempo, você pode usar um last_visit_number que seria um valor global no dB. Se o nó tem esse número, então este rastreamento é aquele que encontrou-lo. Se você quiser rever automaticamente todos os nós, você só precisa bater o last_visit_number antes de iniciar o rastreamento.

Por sua descrição, não estou muito certo como você está ficando preso.

Editar ------ Eu só percebi que você tinha uma pergunta concreta. A fim de aumentar a rapidez com que você puxar em novos dados, gostaria de manter o controle do número de vezes que um determinado usuário foi vinculado a em seus dados (importado ou ainda não importado). Ao escolher um usuário para rastreamento, eu iria pegar os usuários que têm um baixo número de links. Eu especificamente ir para qualquer o menor número de ligações ou uma escolha aleatória entre os usuários com o menor número de ligações.

Jacob

Não há algoritmo especial que irá ajudá-lo a otimizar a construção de um gráfico a partir do zero. De uma forma ou de outra, você vai ter de visitar cada nó, pelo menos uma vez. Se você fizer isso profundidade primeiro ou amplitude primeiro é irrelevante a partir de uma perspectiva de velocidade. Theran corretamente aponta em um comentário abaixo que busca em largura primeiro, explorando os nós mais próximos primeiro, pode dar-lhe uma mais útil gráfico imediatamente, antes que o gráfico inteiro é concluída; este pode ou não pode ser uma preocupação para você. Ele também observa que a versão mais puro de busca em profundidade é implementado usando recursão, o que poderia ser um problema para você. Note-se que a recursividade não é necessário, no entanto; você pode adicionar nós incompletamente exploradas a uma pilha e processá-los de forma linear, se desejar.

Se você fazer uma verificação de existência simples para novos nós (O (1) se você usar um hash para lookup), então ciclos não será um problema de todos. Os ciclos são apenas uma preocupação se você não armazenar o gráfico completo. Você pode otimizar pesquisas através do gráfico, mas o próprio passo construção vai sempre ter tempo linear.

Eu concordo com outras cartazes que o tamanho de seu gráfico não deve ser um problema. 250.000 não é muito grande!

No que diz respeito a execução simultânea; o gráfico é actualizado por todos os fios, por isso, necessita de ser uma estrutura de dados sincronizados. Uma vez que este é Python, você pode fazer uso do Queue módulo para armazenar novos links ainda para ser processado por suas linhas.

Apesar de dizer que a obtenção de uma lista de amigos tem um monte de tempo (10 segundos ou mais), uma variante do algoritmo bom e velho de Dijkstra só poderia funcionar:

  1. Obter qualquer nó.
  2. Obter uma conexão a partir de qualquer nó que você já carregado.
  3. Se a outra extremidade ainda não foi carregado, adicione o nó para o gráfico.
  4. Vá para o passo 2.

O truque é escolher a conexão que você carregar no passo 2 de uma forma inteligente. Algumas observações curtas sobre este:

  • Você deve de alguma forma impedir que a mesma conexão para ser carregado duas ou mais vezes. Seleção de uma conexão aleatória e descartá-lo se ele foi já carregado é muito ineficiente se você estiver após todas as conexões.
  • Se você deseja carregar todas as ligações, eventualmente, carregar todas as conexões de um nó ao mesmo tempo.

A fim de realmente dizer algo sobre a eficiência, forneça mais detalhes sobre estrutura de dados.

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