Buen algoritmo transversal gráfico

Question

Problema abstracto: Tengo un gráfico de aproximadamente 250,000 nodos y la conectividad promedio es de alrededor de 10. Encontrar las conexiones de un nodo es un proceso largo (10 segundos, por ejemplo). Guardar un nodo en la base de datos también toma alrededor de 10 segundos. Puedo verificar si un nodo ya está presente en el DB muy rápidamente. Permitiendo la concurrencia, pero no teniendo más de 10 solicitudes largas a la vez, ¿cómo atravesarías el gráfico para obtener la mayor cobertura más rápido?

Problema concreto: Estoy tratando de raspar las páginas de un usuario de un sitio web. Para descubrir nuevos usuarios, voy a buscar la lista de amigos de usuarios ya conocidos. Ya he importado aproximadamente el 10% del gráfico, pero sigo atorado en ciclos o usando demasiada memoria recordando demasiados nodos.

Mi implementación actual:

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* 

problemas de implementación actual:

• se queda atascado en camarillas que ya he importado, perdiendo así tiempo y los hilos son importadores de inactividad.
• Se agregarán más a medida que se señalen.

Por lo tanto, las mejoras marginales son bienvenidas, así como las reescrituras completas. ¡Gracias!

Answer 1

Para recordar ID de los usuarios que ya ha visitado, se necesita un mapa de una longitud de 250.000 números enteros. Eso está lejos de ser "demasiado". Simplemente mantén ese mapa y solo recorre los bordes que conducen a los usuarios ya no descubiertos, agregándolos a ese mapa en el momento de encontrar ese borde.

Hasta donde puedo ver, está cerca de implementar la búsqueda de primer orden (BFS). Compruebe google sobre los detalles de este algoritmo. Y, por supuesto, no te olvides de los mutexes: los necesitarás.

Answer 2

Estoy realmente confundido sobre por qué se necesitan 10 segundos para agregar un nodo a la base de datos. Eso suena como un problema. ¿Qué base de datos estas usando? ¿Tiene severas restricciones de plataforma?

Con los sistemas modernos, y sus montones de memoria, recomendaría un buen caché simple de algún tipo. Debería poder crear un caché muy rápido de información de usuario que le permita evitar el trabajo repetido. Cuando ya haya encontrado un nodo, detenga el procesamiento. Esto evitará andar en bicicleta para siempre en camarillas.

Si necesita permitir el reajuste de nodos existentes después de un tiempo, puede utilizar un last_visit_number que sería un valor global en los dB. Si el nodo tiene ese número, este rastreo es el que lo encontró. Si desea volver a visitar automáticamente los nodos, solo debe aumentar el último_nombre_de_visita antes de comenzar el rastreo.

Según su descripción, no estoy muy seguro de cómo se va a estancar.

Editar ------ Acabo de notar que tenía una pregunta concreta. Para aumentar la rapidez con la que ingresas datos nuevos, realizaría un seguimiento de la cantidad de veces que un usuario determinado estuvo vinculado a tus datos (importados o no importados). Al elegir un usuario para rastrear, elegiría usuarios que tienen una baja cantidad de enlaces. Específicamente buscaría la menor cantidad de enlaces o una elección aleatoria entre los usuarios con el menor número de enlaces.

Jacob

Answer 3

No hay ningún algoritmo en particular que lo ayude a optimizar la construcción de un gráfico desde cero. De una forma u otra, tendrá que visitar cada nodo al menos una vez. Si lo hace depth first o breadth first es irrelevante desde una perspectiva de velocidad. Theran señala correctamente en un comentario a continuación que la búsqueda de amplitud, al explorar primero los nodos más cercanos, puede brindarle un gráfico más útil de inmediato, antes de que se complete todo el gráfico; esto puede o no ser una preocupación para usted. También señala que la mejor versión de búsqueda en profundidad se implementa mediante recursión, lo que podría ser un problema para usted. Tenga en cuenta que la recursión no es necesaria, sin embargo; puede agregar nodos explorados incompletamente a una pila y procesarlos linealmente si lo desea.

Si realiza una comprobación de existencia simple para nodos nuevos (O (1) si utiliza un hash para buscar), entonces los ciclos no serán un problema en absoluto. Los ciclos son solo una preocupación si no almacena el gráfico completo. Puede optimizar las búsquedas a través del gráfico, pero el paso de construcción en sí siempre llevará tiempo lineal.

Estoy de acuerdo con otros carteles que el tamaño de su gráfico no debería ser un problema. ¡250,000 no es muy grande!

En cuanto a la ejecución simultánea; el gráfico es actualizado por todos los hilos, por lo que debe ser una estructura de datos sincronizada. Dado que se trata de Python, puede utilizar el módulo Queue para almacenar los nuevos enlaces que aún serán procesados ​​por sus hilos.

Answer 4

Aunque se dice que obtener una lista de amigos toma mucho tiempo (10 segundos o más), una variante del algoritmo de buena de edad, de Dijkstra podría funcionar:

1. conseguir cualquier nodo.
2. Obtén una conexión desde cualquier nodo que ya hayas cargado.
3. Si el otro extremo no se ha cargado aún, agregue el nodo al gráfico.
4. Vaya al paso 2.

El truco es seleccionar la conexión se carga en el paso 2 de una manera inteligente. Algunas breves observaciones acerca de esto:

• De alguna manera debe evitar que la misma conexión se cargue dos o más veces. Seleccionar una conexión aleatoria y descartarla si ya se ha cargado es muy ineficiente si buscas todas las conexiones.
• Si desea cargar todas las conexiones eventualmente, cargue todas las conexiones de un nodo al mismo tiempo.

Para decir algo acerca de la eficiencia, proporcione más detalles sobre la estructura de datos.