algoritmo de recorrido buena gráfica

StackOverflow https://stackoverflow.com/questions/1320688

Pregunta

Extracto problema: Tengo un gráfico de cerca de 250.000 nodos y el promedio de conexión es de alrededor de 10. Encontrar conexiones de un nodo es un proceso largo (10 segundos permite decir). Almacenamiento de un nodo a la base de datos también se tarda unos 10 segundos. Puedo comprobar si un nodo ya está presente en la base de datos muy rápidamente. Lo que permite la concurrencia, pero no tener más de 10 largos peticiones a la vez, ¿cómo atravesar el gráfico para obtener la cobertura más alta la más rápida.

problema concreto: Estoy tratando de arañar las páginas del Sitio Web. Para descubrir nuevos usuarios que estoy ir a buscar la lista de amigos de los usuarios ya conocidos. Yo ya he importado alrededor del 10% de la gráfica, pero me siguen dando atrapado en ciclos o el uso de demasiada memoria para recordar 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*

Los problemas de implementación actual:

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

Por lo tanto, alguna mejora marginales son bienvenidos, así como reescrituras completas. Gracias!

¿Fue útil?

Solución

Para recordar ID de los usuarios que ya ha visitado, se necesita un mapa de una longitud de 250.000 números enteros. Eso es lejos de ser "demasiado". Sólo mantener dicho mapa y sólo recorrer a través de los bordes que conducen a los usuarios ya no descubiertos, añadiéndolos a ese mapa en el punto de la búsqueda de dicho borde.

Por lo que puedo ver, estás cerca de poner en práctica la búsqueda primero en amplitud (BFS). Compruebe Google sobre los detalles de este algoritmo. Y, por supuesto, no se olvide de los mutex -. Vas a necesitar

Otros consejos

Estoy muy confundido en cuanto a por qué se tarda 10 segundos para añadir un nodo a la base de datos. Eso suena como un problema. ¿Qué base de datos está utilizando? ¿Tiene graves restricciones de plataforma?

Con los sistemas modernos, y sus montones de memoria, yo recomendaría un buen caché sencilla de algún tipo. Usted debe ser capaz de crear un caché muy rápida de la información de usuario que permitirá evitar el trabajo repetido. Cuando haya encontrado un nodo ya, detener el procesamiento. Esto evitará el ciclismo siempre en camarillas.

Si usted necesita para tener en cuenta rehashing nodos existentes después de un tiempo, se puede utilizar un last_visit_number que sería un valor global en el dB. Si el nodo tiene ese número, entonces este rastreo es la que se encontró con él. Si desea revisar automáticamente los nodos, sólo tiene que golpear la last_visit_number antes de iniciar el rastreo.

Por su descripción, no estoy muy seguro de cómo se le queda pegada.

Editar ------ Me acabo de dar cuenta que tenía una pregunta concreta. Con el fin de aumentar la rapidez con que tire de nuevos datos, me gustaría hacer un seguimiento del número de veces que un usuario determinado se vincula en sus datos (importado o todavía no importada). Al elegir un usuario a gatear, escogería a los usuarios que tienen un bajo número de enlaces. Me gustaría ir específicamente para ya sea el menor número de enlaces o una elección aleatoria entre los usuarios con el menor número de enlaces.

Jacob

No existe un algoritmo particular que le ayudará a optimizar la construcción de un gráfico a partir de cero. De una forma u otra, que van a tener que visitar cada nodo al menos una vez. Si bien lo haces primera o amplitud primero es irrelevante desde el punto de vista de velocidad. Theran correctamente señala en un comentario debajo de la búsqueda en anchura, mediante la exploración de los nodos más cercanos primero, le puede dar una mayor utilidad graficar inmediatamente, antes de que se complete toda la gráfica; esto puede o no puede ser una preocupación para usted. También señala que la versión más bonito de búsqueda en profundidad se implementa utilizando la recursividad, lo que podría ser un problema para usted. Tenga en cuenta que no se requiere la repetición, sin embargo; puede añadir nodos insuficientemente explorados, a una pila y procesarlos de forma lineal si lo desea.

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

Estoy de acuerdo con otros críticos que el tamaño de su gráfico no debería ser un problema. 250000 no es muy grande!

En cuanto a la ejecución concurrente; el gráfico se actualiza por todos los hilos de rosca, por lo que debe ser una estructura de datos sincronizado. Dado que este es Python, puede hacer uso de la cola módulo para almacenar nuevos enlaces todavía para ser procesado por sus hilos.

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

  1. Obtener cualquier nodo.
  2. Obtener una conexión desde cualquier nodo que ya se ha cargado.
  3. Si el otro extremo no se ha cargado todavía, add el nodo para el gráfico.
  4. Ir al paso 2.

El truco consiste en seleccionar la conexión se carga en el paso 2 de una manera inteligente. Unos breves comentarios acerca de esto:

  • Usted debe evitar de alguna manera la misma conexión que se debe cargar dos veces o más a menudo. Selección de una conexión aleatoria y descartarla si ha sido ya cargado es muy ineficiente si después de todas las conexiones.
  • Si desea cargar todas las conexiones con el tiempo, cargue todas las conexiones de un nodo al mismo tiempo.

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

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top