Python: почему этот код берет навсегда (бесконечный цикл?)

Я разрабатываю приложение в Google App Engine. Один из моих методов никогда не берет завершение, которое заставляет меня думать, что это поймано в бесконечном цикле. Я уставился на него, но не могу понять его.

Отказ от ответственности: Я использую http://code.google.com/p/gaeunitтекст ссылки для запущения моих тестов. Возможно, это действует странно?

Это - проблематичная функция:

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

Первоначально, я думал, что это могла бы быть ошибка рекурсии, но я прокомментировал рекурсию, и проблема сохраняется. Если эта функция вызвана с c_levels = 0, это хорошо работает.

Модели это ссылается:

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) 

Служебные функции это ссылается:

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

Я пропускаю что-то довольно очевидное здесь, или GAEUnit капризничает?

Также - тест, который заставляет это отстать, имеет не больше, чем 5 моделей любого вида в хранилище данных. Я знаю, что это потенциально медленно, но мое приложение только делает это, после того как затем впоследствии кэширует его.

5
задан Nick Heiner 7 June 2010 в 00:29
поделиться

1 ответ

Игнорируя закомментированную рекурсию, я не думаю, что это должен быть бесконечный цикл - вы просто выполняете несколько циклов for для конечных наборов результатов.

Однако, похоже, это будет действительно медленным. Вы просматриваете целые таблицы, а затем выполняете больше запросов к хранилищу данных в каждом вложенном цикле. Кажется маловероятным, что такого рода запросы будут выполнены своевременно в GAE, если только ваши таблицы не действительно очень маленькие.


Некоторые приблизительные числа:

Если H = количество объектов в DepedencyArcHead и T = среднее # хвостов в каждом DependencyArcHead , затем:

  • _getListArcTailsWithCourse выполняет около H * T запросов (заниженная оценка). В «худшем» случае результат , возвращаемый этой функцией, будет содержать H * T элементов.
  • _traverseForwards перебирает все эти результаты H раз и, таким образом, выполняет еще один запрос H * (H * T).
  • Даже если H и T имеют порядок десятков, вы можете выполнять тысячи запросов. Если они больше, то ... (и это игнорирует любые дополнительные запросы, которые вы бы сделали, если бы раскомментировали рекурсивный вызов).

Короче говоря, я думаю, вы можете попытаться организовать свои данные немного по-другому, если это возможно. Я бы сделал конкретное предложение, но мне непонятно, что именно вы пытаетесь сделать.

3
ответ дан 15 December 2019 в 06:17
поделиться
Другие вопросы по тегам:

Похожие вопросы: