Bon graphique algorithme traversal

https://stackoverflow.com/questions/1320688

19-09-2019
|

Question

problème Résumé: J'ai un graphique d'environ 250 000 nœuds et la connectivité moyenne est d'environ 10. Trouver les connexions d'un nœud est un processus long (10 secondes permet de dire). Enregistrement d'un noeud à la base de données prend également environ 10 secondes. Je peux vérifier si un nœud est déjà présent dans la base de très rapidement. Permettre à la concurrence, mais ne pas avoir plus de 10 longues demandes à la fois, comment voulez-vous parcourir le graphique pour gagner la meilleure couverture le plus rapide.

problème concret: Je suis en train de gratter une pages utilisateur du site. Pour découvrir de nouveaux utilisateurs Je récupération de la liste d'amis des utilisateurs déjà connus. Je l'ai déjà importé environ 10% du graphique, mais je continue à rester coincé dans les cycles ou utiliser trop de mémoire se rappelant trop de nœuds.

Ma mise en œuvre actuelle:

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*

Les problèmes de mise en œuvre actuelle:

se coince dans les cliques que je l'ai déjà importé, perdre ainsi le temps et les fils d'importation sont au repos.
va ajouter plus comme ils se fait remarquer.

Alors, improvments marginales sont les bienvenus, ainsi que le plein réécritures. Merci!

La solution

Pour ne pas oublier les ID des utilisateurs que vous avez déjà visités, vous avez besoin d'une carte d'une longueur de 250.000 entiers. C'est loin d'être « trop ». Il suffit de maintenir une telle carte et seulement traverser à travers les bords qui mènent aux utilisateurs déjà inexplorées, en les ajoutant à cette carte au point de trouver ce bord.

En ce que je peux voir, vous êtes proche de mettre en œuvre la recherche en largeur d'abord (BFS). Vérifiez Google sur les détails de cet algorithme. Et, bien sûr, ne pas oublier mutex -. Vous en aurez besoin

Autres conseils

Je suis vraiment confus quant à la raison pour laquelle il faut 10 secondes pour ajouter un nœud à la DB. Cela ressemble à un problème. Qu'est-ce que la base de données utilisez-vous? Avez-vous des restrictions sévères de la plate-forme?

Avec les systèmes modernes, et leurs oodles de mémoire, je recommanderais une belle cache simple une sorte. Vous devriez être en mesure de créer un cache très rapide des informations utilisateur qui vous permettra d'éviter les travaux répétitifs. Lorsque vous avez rencontré un nœud déjà, arrêter le traitement. Cela évitera le vélo pour toujours dans les cliques.

Si vous avez besoin pour permettre ressasser des noeuds existants après un certain temps, vous pouvez utiliser un last_visit_number qui serait une valeur globale de la dB. Si le nœud a ce numéro, cette analyse est celle qui a rencontré il. Si vous souhaitez revenir automatiquement tous les nœuds, il vous suffit de remonter le last_visit_number avant de commencer l'exploration.

Par votre description, je ne suis pas tout à fait sûr comment vous rester coincé.

Modifier ------ Je viens de remarquer que vous aviez une question concrète. Afin d'augmenter la rapidité avec laquelle vous tirez dans de nouvelles données, je garder une trace du nombre de fois qu'un utilisateur donné est liée à vos données (importées ou non encore importées). Lors du choix d'un utilisateur à ramper, je choisirais les utilisateurs qui ont un faible nombre de liens. J'irais spécifiquement pour soit le plus petit nombre de liens ou un choix aléatoire parmi les utilisateurs avec le plus faible nombre de liens.

Jacob

Il n'y a pas d'algorithme particulier qui vous aidera à optimiser la construction d'un graphique à partir de zéro. D'une façon ou une autre, vous allez devoir visiter chaque nœud au moins une fois. Que vous fassiez cette première ou Theran souligne à juste titre dans un commentaire ci-dessous que la recherche en largeur, en explorant les noeuds plus proches d'abord, peut vous donner un plus utile graphe immédiatement, avant tout le graphique est terminé; cela peut ou peut ne pas être une préoccupation pour vous. Il note également que la version plus élégante de la recherche en profondeur d'abord est mis en œuvre en utilisant récursion, ce qui pourrait être un problème pour vous. Notez que la récursivité n'est pas nécessaire, cependant; vous pouvez ajouter des nœuds incomplètement explorées à une pile et de les traiter de façon linéaire si vous le souhaitez.

Si vous faites une simple vérification de l'existence de nouveaux noeuds (O (1) si vous utilisez un hachage pour la recherche), puis les cycles ne sera pas un problème du tout. Les cycles ne sont un problème si vous ne stockez pas le graphe complet. Vous pouvez optimiser les recherches dans le graphique, mais l'étape de la construction elle-même toujours prendre le temps linéaire.

Je suis d'accord avec d'autres affiches que la taille de votre graphique ne devrait pas être un problème. 250000 est pas très grand!

En ce qui concerne l'exécution simultanée; le graphique est mis à jour tous les fils, de sorte qu'il doit être une structure de données synchronisées. Comme c'est Python, vous pouvez utiliser la Queue module pour enregistrer de nouveaux liens encore à traiter par vos fils.

Bien que vous dites que l'obtention d'une liste d'amis prend beaucoup de temps (10 secondes ou plus), une variante de bon vieux algorithme de Dijkstra pourrait bien fonctionner:

Obtenir un nœud.
Obtenir une connexion de tout nœud que vous avez déjà chargé.
Si l'autre extrémité n'a pas encore été chargé, ajoutez le nœud au graphique.
Passez à l'étape 2.

L'astuce est de choisir la connexion que vous chargez à l'étape 2 de manière intelligente. Quelques brèves remarques à ce sujet:

Vous devriez en quelque sorte d'éviter la même connexion à charger deux fois ou plus. La sélection d'une connexion aléatoire et jetez-le si elle a été chargée est déjà très inefficace si vous êtes après toutes les connexions.
Si vous voulez charger toutes les connexions éventuellement, charger toutes les connexions d'un noeud en même temps.

Pour vraiment dire quelque chose sur l'efficacité, s'il vous plaît fournir plus de détails sur structure de données.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow