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

StackOverflow https://stackoverflow.com/questions/1320688

Вопрос

Абстрактная проблема:У меня есть граф, содержащий около 250 000 узлов, а средняя связность составляет около 10.Поиск соединений узла — длительный процесс (скажем, 10 секунд).Сохранение узла в базе данных также занимает около 10 секунд.Я могу очень быстро проверить, присутствует ли узел в базе данных.Разрешая параллелизм, но не имея более 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*

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

  • Застревает в кликах, которые я уже импортировал, тем самым теряя время и потоки импорта простаивают.
  • Буду добавлять больше, когда на них укажут.

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

Это было полезно?

Решение

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

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

Другие советы

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

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

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

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

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

Джейкоб

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top