Résumé Problème: J'ai un graphique d'environ 250 000 nœuds et la connectivité moyenne est d'environ 10. La recherche d'un nœud est un processus long (10 secondes permettent de dire). Enregistrer un nœud à 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 DB très rapidement. Permettre la concurrence, mais ne pas avoir plus de 10 demandes de longue durée à la fois, comment traverseriez-vous le graphique pour obtenir la couverture la plus élevée le plus rapide.
Problème concret: J'essaie de gratter des pages d'utilisateur du site Web. Pour découvrir de nouveaux utilisateurs, je vis de la liste des amis à partir d'utilisateurs déjà connus. J'ai déjà importé environ 10% du graphique, mais je continue à rester coincé dans des cycles ou à utiliser trop de mémoire en vous souvenant de trop de nœuds. P>
Ma mise en œuvre actuelle: P>
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*
Ainsi, les améliorations marginales sont les bienvenues, ainsi que des réécrites complètes. Merci! P> p>
4 Réponses :
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. Quelle base de données utilisez-vous? Avez-vous des restrictions de plate-forme sévères?
avec des systèmes modernes et leurs oodules de mémoire, je recommanderais une belle cache simple d'une sorte. Vous devriez pouvoir créer un cache très rapide des informations utilisateur qui vous permettraient d'éviter les travaux répétés. Lorsque vous avez déjà rencontré un nœud, arrêtez le traitement. Cela évitera le cyclisme pour toujours dans les cliques.
Si vous devez autoriser la réhabation des nœuds existants après un certain temps, vous pouvez utiliser un last_visit_number qui serait une valeur globale dans la DB. Si le nœud a ce numéro, cette rampe est celle qui l'a rencontrée. Si vous souhaitez revenir automatiquement des nœuds, vous devez simplement baisser le last_visit_number avant de commencer le crawl.
Par votre description, je ne suis pas tout à fait sûr de savoir comment vous êtes coincé.
Edit ------ Je viens de remarquer que vous avez eu une question concrète. Afin d'augmenter la rapidité avec laquelle vous tirez dans de nouvelles données, je garderais une trace du nombre de fois qu'un utilisateur donné a été lié à vos données (importés ou non importés). Lorsque vous choisissez un utilisateur pour ramper, je choisirais des utilisateurs qui ont un faible nombre de liens. Je choisirais spécifiquement le nombre le plus bas de liens ou un choix aléatoire entre les utilisateurs avec le nombre le plus bas de liens.
jacob
Les 10 secondes proviennent de devoir gratter quelques pages d'informations sur l'utilisateur, puis de le transformer en mode de base de données. La plupart d'entre elles est la durée du réseau.
En ce qui concerne le choix des nouveaux utilisateurs, très intéressant. Je vais essayer de compter les incrustations pour les utilisateurs et seulement des spidering à partir d'utilisateurs faibles incrustés.
Pourquoi si peu de threads? Êtes-vous inquiet qu'ils vous bloqueront? J'allais suggérer un hachage pour chaque noeud (A.La Pavel). Une chose que vous pourriez faire est de créer une pièce d'identité incrémentée et d'utiliser une simple table de cartographie pour les faire référence.
Oui, je suis inquiet que le site distant me bloquera. La politesse et tout ce que (à Yahoo! Je sais que nos robots de crazoyer visent 2 recruts / hôte à tout moment). Avec le travail en mémoire de mémoire, je n'ai pas besoin d'optimiser mon chemin de crawl, mais si l'autre site pousse dans l'ordre de la magnitude, je devrai passer à votre stratégie. Merci!
Une option, légèrement tordue, l'option serait de tirer parti des résultats d'un moteur de recherche via leur API pour obtenir les données souhaitées. Si vous construisez votre base de données initiale, la page mise en cache, si disponible, vous donnerait probablement vos données dont vous avez besoin. Les moteurs de recherche fonctionnent à une vélocité énorme et ne voudraient probablement pas oublier quelques discussions supplémentaires.
Pour vous souvenir des identifiants 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 de "trop". Il suffit de maintenir une telle carte et ne traversez que les bords qui conduisent aux utilisateurs déjà non découverts, les ajoutant à cette carte au point de trouver un tel avantage.
Aussi loin que je peux voir, vous êtes proche de mettre en œuvre la première recherche de la largeur (BFS). Vérifiez Google sur les détails de cet algorithme. Et bien sûr, n'oubliez pas de mutexes - vous aurez besoin d'eux.
Les utilisateurs sont en réalité des chaînes de caractères de longueur moyenne 15. J'ai essayé d'avoir un dict avec {USERNAME1: TRUE, Nom d'utilisateur2: True}, mais qui frappe rapidement 100% Mémoire et la machine enfermée. Peut-être que c'est juste inefficace en python d'utiliser un dict?
Une solution possible serait juste pour stocker des hachages des noms d'utilisateur
En outre, un ensemble est mieux adapté à ce type de stockage qu'un dict
Dans les docs ( docs.python.org/library/stdtypes. HTML # SET-TYPES-TYPES-SET-FROZENS ET ) Il est indiqué: "Les éléments définis, comme les clés de dictionnaire, doivent être hachables" alors je suppose donc
Et la recherche est bonne, aussi :-) blog.tplus1.com/index.php/2008/03/17/...
Yup, faisant le modèle de mémoire dans un ensemble () et juste garder tout l'historique en mémoire l'a fait. J'ai traversé 23k la nuit dernière et je n'utilise que 800 Mo de mémoire. Il sera toujours proche mais je vais passer aux hachages au lieu de chaînes de personnages dans quelques jours. Merci!
Il n'y a pas d'algorithme particulier qui vous aidera à optimiser la construction d'un graphique à partir de zéro. D'une manière ou d'une autre, vous allez devoir visiter chaque noeud au moins une fois. Si vous faites ce Profond First ou La largeur d'abord n'est pas pertinente à partir d'une perspective de vitesse. Theran souligne correctement dans un commentaire ci-dessous cette première recherche de la largeur, en explorant d'abord les nœuds plus proches, peut vous donner un plus utile. graphique immédiatement avant la fin du graphique; Cela peut être ou non être une préoccupation pour vous. Il note également que la version latérale de la première recherche de profondeur-première est mise en œuvre à l'aide de la récursivité, ce qui pourrait potentiellement être un problème pour vous. Notez que la récursion n'est pas nécessaire, cependant; Vous pouvez ajouter des nœuds incomplarquement explorés à une pile et leur traiter linéairement si vous le souhaitez.
Si vous faites une simple vérification d'existence pour de nouveaux nœuds (O (1) si vous utilisez un hachage pour la recherche), les cycles ne seront pas un problème du tout. Les cycles ne concernent que si vous ne stockez pas le graphique complet. Vous pouvez optimiser les recherches via le graphique, mais l'étape de construction elle-même prendra toujours du temps linéaire.
Je suis d'accord avec d'autres affiches que la taille de votre graphique ne devrait pas être un problème. 250 000 n'est pas très grand!
concernant l'exécution simultanée; Le graphique est mis à jour par tous les threads. Il doit donc être une structure de données synchronisée. Comme il s'agit de Python, vous pouvez utiliser le Weeu Module pour stocker de nouveaux liens toujours être traité par vos threads.
BFS pourrait être meilleur car il examinera les nœuds les plus proches à la première première, ce qui est susceptible de donner un sous-ensemble utile tôt. BFS évite également le risque de récursion de 250 000 niveaux profond et pourrait conserver sa file d'attente dans le même DB que le graphique final (supposant une SGBDM).
Vous pouvez certainement faire des dfs sans le problème de la trace de pile profonde: la seule différence réelle entre DFS et BFS est dans BFS, vous ajoutez des nœuds à une file d'attente; dans dfs, une pile. Même algorithme, différente structure de données - et donc, une sémantique différente.
@Theran, Michael: +1 Merci - Réponse ajustée pour faire cette clarification.
Cela ressemble à un simple bfs (comme je l'ai) est en ordre. Je suis 100% avec vous avec les 250 000 étant petits, mais ma mise en œuvre initiale a rapidement manqué de memeory faire un dictionnaire de {username1: vrai, nom d'utilisateur2: true}. Peut-être que je devrais poster cela comme un autre problème.
Bien que vous disiez que l'obtention d'une liste d'amis prend beaucoup de temps (10 secondes ou plus), une variante d'algorithme de Dijkstra de bon vieux peut-être fonctionner:
L'astuce consiste à sélectionner la connexion que vous chargez à l'étape 2 de manière intelligente. Quelques remarques courtes à ce sujet:
Pour vraiment dire quelque chose sur l'efficacité, veuillez fournir plus de détails sur DaSTRUCTURE.
Toute relation avec Robert Tarjan, le découvreur de plusieurs algorithmes notables graphes-théoriques (!)?
:) Malheureusement, seule la ville en Hongrie que nous avons tous les deux reçu notre nom de famille. Mais nous avons tous les deux un amour d'ordinateurs et de mathématiques.
Sans rapport avec la question, mais note que SyS.StderRr.Write ("... \ n") peut être remplacé par Imprimer >> SyS.S.S.STERR, "..." (pas besoin de "\ n" et d'utilisation de la déclaration d'impression la plus habituelle).
Juste, mais je redirigeais le stdout dans un fichier (aucun moyen que vous puissiez le savoir), et je voulais toujours que les messages d'erreur montrent dans ma console.