Хороший алгоритм обхода графа

Абстрактная проблема: у меня есть график около 250 000 узлов, а средняя связь - около 10. Поиск соединений node - длительный процесс (скажем, через 10 секунд). Сохранение node в базе данных также занимает около 10 секунд. Я могу проверить, действительно ли node уже присутствует в db. Разрешая concurrency, но не имея более 10 длинных запросов за раз, как бы вы пересекли график, чтобы получить максимальный охват быстрее.

Конкретная проблема: я пытаюсь очистить страницы пользователя веб-сайта. Чтобы узнать новых пользователей, я получаю список друзей от уже известных пользователей. Я уже импортировал около 10% графика, но я постоянно зацикливаюсь или слишком много памяти запоминаю слишком много узлов.

Моя текущая реализация:

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*

Проблемы текущей реализации:

Возвращается в клики, которые я уже импортировал, тем самым теряя время, а импортирующие потоки простаивают.
Будет добавлено больше, поскольку они будут указаны.

Итак, маргинальные улучшения приветствуются, а также полные перезаписи. Спасибо!

Ответы

Ответ 1

Чтобы помнить идентификаторы пользователей, которые вы уже посетили, вам нужна карта длиной 250 000 целых чисел. Это далеко не "слишком много". Просто поддерживайте такую карту и проходите только по краям, которые ведут к уже неоткрытым пользователям, добавляя их к этой карте в точке нахождения такого края.

Насколько я могу судить, вы близки к реализации поиска Breadth-first (BFS). Проверьте google о деталях этого алгоритма. И, конечно же, не забывайте о мьютексах - они вам понадобятся.

Ответ 2

Я действительно смущен тем, почему требуется 10 секунд, чтобы добавить node в БД. Это звучит как проблема. Какую базу данных вы используете? У вас серьезные ограничения на платформу?

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

Если вам нужно разрешить повторное использование существующих узлов через некоторое время, вы можете использовать last_visit_number, который будет глобальным значением в дБ. Если node имеет это число, то этот обход - тот, который столкнулся с ним. Если вы хотите автоматически пересмотреть любые узлы, вам просто нужно нанести последний_визуальный номер перед запуском обхода.

По вашему описанию я не совсем уверен, как вы застреваете.

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

Jacob

Ответ 3

Нет конкретного алгоритма, который поможет вам оптимизировать построение графика с нуля. Так или иначе, вам придется посещать каждый node хотя бы один раз. Выполняете ли вы это глубину в начале или ширина сначала не имеет значения с точки зрения скорости. Theran правильно указывает в комментарии ниже, что поиск по ширине, сначала исследуя более близкие узлы, может дать вам более полезный график сразу, прежде чем весь граф будет завершено; это может быть или не быть проблемой для вас. Он также отмечает, что самая аккуратная версия поиска по глубине выполняется с использованием рекурсии, что потенциально может быть проблемой для вас. Обратите внимание, что рекурсия не требуется; вы можете добавить не полностью исследованные узлы в стек и обработать их линейно, если хотите.

Если вы выполняете обычную проверку наличия новых узлов (O (1), если вы используете хэш для поиска), то циклы вообще не будут проблемой. Циклы - это только проблема, если вы не храните полный график. Вы можете оптимизировать поиск по графику, но сам этап построения всегда будет занимать линейное время.

Я согласен с другими плакатами, что размер вашего графика не должен быть проблемой. 250 000 не очень большой!

Относительно одновременного выполнения; график обновляется всеми потоками, поэтому он должен быть синхронизированной структурой данных. Поскольку это Python, вы можете использовать модуль Queue для хранения новых ссылок, которые еще обрабатываются вашими потоками.

Ответ 4

Хотя вы говорите, что получение списка друзей занимает много времени (10 секунд и более), вариант доброжелательного алгоритма Дейкстры может работать:

Получить любой node.
Получить соединение с любым загруженным node.
Если другой конец еще не загружен, добавьте node.
Перейдите к шагу 2.

Фокус в том, чтобы выбрать соединение, которое вы загружаете на шаге 2, умным способом. Несколько коротких замечаний об этом:

Вы должны каким-то образом запретить загрузку одного и того же соединения дважды или чаще. Выбор случайного соединения и сброс его, если он уже загружен, очень неэффективен, если вы после всех подключений.
Если вы хотите в любой момент загрузить все соединения, загрузите все соединения node одновременно.

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