PageRank в Python: превышена максимальная глубина рекурсии

Question

У меня есть набор данных - около 30000 пользователей, и я хочу рассчитать влияние каждого пользователя на основе алгоритма UserRank, который основан на PageRank:

Для каждого пользователя У меня есть список подписчиков. Я пытался вычислить это в Python, но я получаю:

RecursionError: maximum recursion depth exceeded while calling a Python object

Вот код:

def calculate_user_rank(user_id):
    user_rank = 0
    for j in user[user_id]["followers"]:
        user_rank += (1 + (user[user_id]["followers_count"]/user[user_id]["tweets"]) * calculate_user_rank(j))/user[j]["followers_count"]
    return user_rank

Есть ли способ, как рассчитать эту меру для каждого пользователя?

Answer 1

Вы всегда можете изменить предел рекурсии по умолчанию: Какова максимальная глубина рекурсии в Python и как ее увеличить? Но в этом примере я бы предпочел итеративное решение для вашей проблемы (как здесь : https://github.com/thomasjhuang/PageRank/blob/master/run_pagerank.py) и кэш для каждого пользователя его оценка производительности.

Answer 2

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

Использование:

def calculate_user_rank(user_id, memo={}):
    user_rank = 0
    for j in user[user_id]["followers"]:
        if j not in memo:
            memo[j] = calculate_user_rank(j, memo)

        user_rank += (1 + (user[user_id]["followers_count"]/user[user_id]["tweets"]) * memo[j])/user[j]["followers_count"]
    memo[user_id] = user_rank

    return memo[user_id]