Algoritmo di attraversamento grafico buono

Question

Problema astratto: ho un grafico di circa 250.000 nodi e la connettività media è di circa 10. Trovare le connessioni di un nodo è un processo lungo (diciamo 10 secondi). Anche il salvataggio di un nodo nel database richiede circa 10 secondi. Posso verificare se un nodo è già presente nel db molto rapidamente. Consentendo la concorrenza, ma senza avere più di 10 richieste lunghe alla volta, come avresti attraversato il grafico per ottenere la copertura più alta il più veloce.

Problema concreto: sto cercando di analizzare le pagine degli utenti di un sito web. Per scoprire nuovi utenti sto recuperando la lista amici da utenti già noti. Ho già importato circa il 10% del grafico, ma continuo a rimanere bloccato in cicli o usando troppa memoria ricordando troppi nodi.

mio attuale implementazione:

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* 

Problemi di implementazione attuale:

• rimane incastrato in cricche che ho già importato, sprecando così tempo e le filettature importazione sono inattivi.
• Aggiungerà più come vengono evidenziati.

Così, i miglioramenti marginali sono benvenuti, così come le riscritture complete. Grazie!

Answer 1

Per ricordare gli ID degli utenti che hai già visitato, è bisogno di una mappa di una lunghezza di 250.000 interi. Questo è ben lungi dall'essere "troppo". Basta mantenere una mappa del genere e attraversare solo i bordi che portano agli utenti già sconosciuti, aggiungendoli a quella mappa al punto di trovare tale margine.

Per quanto posso vedere, sei vicino a implementare la ricerca di ampiezza (BFS). Controlla su google i dettagli di questo algoritmo. E, naturalmente, non dimenticare di mutex - ne avrai bisogno.

Answer 2

Sono davvero confuso sul motivo per cui occorrono 10 secondi per aggiungere un nodo al DB. Sembra un problema. che database stai usando? Avete severe restrizioni della piattaforma?

Con i sistemi moderni e la loro abbondanza di memoria, consiglierei una bella cache di qualche tipo. Dovresti essere in grado di creare una cache molto veloce di informazioni utente che ti consenta di evitare il lavoro ripetuto. Quando hai già incontrato un nodo, interrompi l'elaborazione. Questo eviterà di pedalare per sempre nelle cricche.

Se è necessario consentire il rientro dei nodi esistenti dopo un po ', è possibile utilizzare un last_visit_number che sarebbe un valore globale nel dB. Se il nodo ha quel numero, allora questa scansione è quella che lo ha incontrato. Se si desidera rivedere automaticamente tutti i nodi, è necessario eseguire il bump di last_visit_number prima di avviare la scansione.

Dalla tua descrizione, non sono abbastanza sicuro di come ti blocchi.

Modifica ------ Ho appena notato che hai una domanda concreta. Per aumentare la velocità con cui inserirai nuovi dati, terrei traccia del numero di volte in cui un dato utente è stato collegato ai tuoi dati (importati o non ancora importati). Quando scelgo un utente per eseguire la scansione, selezionerei utenti con un basso numero di link. Vorrei specificatamente scegliere il numero più basso di link o una scelta casuale tra gli utenti con il numero più basso di link.

Jacob

Answer 3

Non esiste un particolare algoritmo che ti aiuti a ottimizzare la costruzione di un grafico da zero. In un modo o nell'altro, dovrai visitare ogni nodo almeno una volta. Se lo si fa, depth first o breadth first è irrilevante dal punto di vista della velocità. Theran indica correttamente in un commento di seguito che la ricerca in ampiezza, esplorando prima i nodi più vicini, può fornire immediatamente un grafico più utile, prima che l'intero grafico sia completato; questo può o non può essere un problema per te. Osserva inoltre che la versione più accurata della ricerca in profondità è implementata ricorrendo alla ricorsione, che potrebbe potenzialmente rappresentare un problema per te. Si noti che la ricorsione non è richiesta, tuttavia; puoi aggiungere nodi esplorati in modo incompleto in uno stack e elaborarli linearmente, se lo desideri.

Se si esegue una verifica semplice esistenza di nuovi nodi (O (1) se si utilizza un hash per la ricerca), quindi cicli non sarà affatto un problema. I cicli sono solo una preoccupazione se non si memorizza il grafico completo. È possibile ottimizzare le ricerche attraverso il grafico, ma il passo di costruzione stesso richiederà sempre un tempo lineare.

Concordo con altri utenti che la dimensione del grafico non dovrebbe essere un problema. 250.000 non è molto grande!

Relativamente all'esecuzione concomitante; il grafico viene aggiornato da tutti i thread, quindi deve essere una struttura dati sincronizzata. Poiché si tratta di Python, è possibile utilizzare il modulo Queue per memorizzare i nuovi collegamenti ancora da elaborare dai thread.

Answer 4

Anche se si dice che ottenere un elenco amico prende un sacco di tempo (10 secondi o più), una variante dell'algoritmo di buon vecchio di Dijkstra potrebbe funzionare:

1. ottenere qualsiasi nodo.
2. Ottenere una connessione da qualsiasi nodo già caricato.
3. Se l'altra estremità non è stata ancora caricata, aggiungere il nodo al grafico.
4. Andare al punto 2.

Il trucco è quello di selezionare la connessione che si carica al punto 2 in modo intelligente. Qualche osservazione a breve su questo:

• Si dovrebbe in qualche modo impedire la stessa connessione per essere caricati due volte o più spesso. Selezionare una connessione casuale e scartarla se è già stata caricata è molto inefficiente se si è dopo tutte le connessioni.
• Se si desidera caricare tutte le connessioni, caricare tutte le connessioni di un nodo contemporaneamente.

Per dire veramente qualcosa sull'efficienza, si prega di fornire maggiori dettagli sulla struttura dei dati.