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

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

5 голосов
/ 07 июня 2010

Я занимаюсь разработкой приложения в 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 моделей любого типа в хранилище данных. Я знаю, что это потенциально медленно, но мое приложение делает это только один раз, а затем кеширует.

1 Ответ

3 голосов
/ 07 июня 2010

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

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

Некоторые грубые номера:

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

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

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

...