Python: ¿por qué este código tarda una eternidad (bucle infinito?)

Question

Estoy desarrollando una aplicación en Google App Engine. Uno de mis métodos es tomar nunca completar, lo que me hace pensar que está atrapado en un ciclo infinito. Lo he mirado fijamente, pero no puedo entenderlo.

Descargo de responsabilidad: Estoy usando http://code.google.com/p/gaeunitlink text para ejecutar mis pruebas. Tal vez está actuando de manera extraña?

Ésta es la función problemática:

def _traverseForwards(course, c_levels): 
    ''' Looks forwards in the dependency graph ''' 
    result = {'nodes': [], 'arcs': []} 

    if c_levels == 0: 
     return result 

    model_arc_tails_with_course = set(_getListArcTailsWithCourse(course)) 
    q_arc_heads = DependencyArcHead.all() 

    for model_arc_head in q_arc_heads: 
     for model_arc_tail in model_arc_tails_with_course: 
      if model_arc_tail.key() in model_arc_head.tails: 
       result['nodes'].append(model_arc_head.sink) 
       result['arcs'].append(_makeArc(course, model_arc_head.sink)) 

       # rec_result = _traverseForwards(model_arc_head.sink, c_levels - 1) 

       # _extendResult(result, rec_result) 

    return result 

Originalmente, pensé que podría ser un error de la recursividad, pero me comentaron la recursividad y el problema persiste. Si se llama a esta función con c_levels = 0, funciona bien.

Los modelos se hace referencia a: funciones

class Course(db.Model): 
    dept_code = db.StringProperty() 
    number = db.IntegerProperty() 
    title = db.StringProperty() 
    raw_pre_reqs = db.StringProperty(multiline=True) 
    original_description = db.StringProperty() 

    def getPreReqs(self): 
     return pickle.loads(str(self.raw_pre_reqs)) 

    def __repr__(self): 
     return "%s %s: %s" % (self.dept_code, self.number, self.title) 

class DependencyArcTail(db.Model): 
    ''' A list of courses that is a pre-req for something else ''' 
    courses = db.ListProperty(db.Key) 

    def equals(self, arcTail): 
     for this_course in self.courses: 
      if not (this_course in arcTail.courses): 
       return False 

     for other_course in arcTail.courses: 
      if not (other_course in self.courses): 
       return False 

     return True 

class DependencyArcHead(db.Model): 
    ''' Maintains a course, and a list of tails with that course as their sink ''' 
    sink = db.ReferenceProperty() 
    tails = db.ListProperty(db.Key) 

Utilitarios hace referencia a:

def _makeArc(source, sink): 
    return {'source': source, 'sink': sink} 

def _getListArcTailsWithCourse(course): 
    ''' returns a LIST, not SET 
     there may be duplicate entries 
    ''' 
    q_arc_heads = DependencyArcHead.all() 
    result = [] 
    for arc_head in q_arc_heads: 
     for key_arc_tail in arc_head.tails: 
      model_arc_tail = db.get(key_arc_tail) 
      if course.key() in model_arc_tail.courses: 
       result.append(model_arc_tail) 

    return result 

Me estoy perdiendo algo bastante obvio aquí, o se GAEUnit actuar para arriba?

Además, la prueba que está haciendo que esta ejecución sea lenta no tiene más de 5 modelos de ningún tipo en el almacén de datos. Sé que esto es potencialmente lento, pero mi aplicación solo hace esto una vez y luego lo almacena en la memoria caché.

Answer 1

Haciendo caso omiso de la recursión comentada, no creo que esto deba ser un ciclo infinito; solo estás haciendo algunos bucles para conjuntos de resultados finitos.

Sin embargo, parece que esto sería realmente lento. Estás recorriendo tablas completas y luego haciendo más consultas en el almacén de datos en cada ciclo anidado. Parece poco probable que este tipo de solicitud se complete de manera oportuna en GAE a menos que sus tablas sean muy, muy pequeñas.

---

Algunos ásperas números:

Si H = nº de entidades en DepedencyArcHead y T = promedio # de colas en cada DependencyArcHead a continuación:

• _getListArcTailsWithCourse está haciendo aproximadamente H*T consultas (infraestimación). En el "peor" caso, el result devuelto desde esta función tendrá H*T elementos.
• _traverseForwards repite todos estos resultados H veces, y así hace otras consultas H * (H * T).
• Incluso si H y T son solo del orden de 10s, podría estar haciendo miles de consultas. Si son más grandes, entonces ... (y esto ignora cualquier consulta adicional que harías si descomentaras la llamada recursiva).

En resumen, creo que es posible que desee tratar de organizar sus datos de una manera un tanto diferente si es posible. Haría una sugerencia específica, pero lo que estás tratando de hacer no está claro para mí.