Abstraktes Problem: Ich habe einen Graphen mit etwa 250.000 Knoten und die durchschnittliche Konnektivität liegt bei 10. Das Auffinden der Verbindungen eines Knotens ist ein langer Prozess (beispielsweise 10 Sekunden). Das Speichern eines Knotens in der Datenbank dauert ebenfalls ca. 10 Sekunden. Ich kann sehr schnell überprüfen, ob ein Knoten bereits in der Datenbank vorhanden ist. Wenn Sie die Parallelität zulassen, aber nicht mehr als 10 lange Anforderungen gleichzeitig haben, wie würden Sie das Diagramm durchlaufen, um die höchste Abdeckung am schnellsten zu erzielen.

Konkretes Problem: Ich versuche, die Seiten eines Website-Benutzers zu kratzen. Um neue Benutzer zu entdecken, rufe ich die Freundesliste von bereits bekannten Benutzern ab. Ich habe bereits ungefähr 10% des Diagramms importiert, aber ich stecke immer wieder in Zyklen fest oder benutze zu viel Speicher, um mich an zu viele Knoten zu erinnern.

Meine aktuelle Implementierung:

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*

Probleme der aktuellen Implementierung:

Bleibt in Cliquen stecken, die ich bereits importiert habe, wodurch Zeit verschwendet wird und die importierenden Threads inaktiv sind.Wird mehr hinzufügen, wenn sie darauf hingewiesen werden.

Daher sind marginale Verbesserungen ebenso willkommen wie vollständige Umschreibungen. Vielen Dank!