良好的图形遍历算法(Good graph traversal algorithm)

摘要问题：我有25万左右节点的图，平均连接是在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*

目前执行的问题：

陷在我已导入拉帮结派，从而浪费时间和进口线程是空闲的。
将增加更多，因为他们得到指出。

因此，边际改进措施是值得欢迎的，以及完整的重写。谢谢！

Answer 1:

要记住你访问过的用户ID，您需要地图250,000整数的长度。这远非“太多”。只要保持这样的地图，只有通过导致已未被发现的用户边缘穿过，在找到这样的边缘点把它们添加到地图中。

据我所看到的，你接近实现广度优先搜索（BFS）。检查谷歌关于这个算法的细节。而且，当然，不要忘了互斥 - 你会需要它们。

Answer 2:

我真的很困惑，为什么需要10秒钟，将节点添加到数据库。这听起来像一个问题。您正在使用什么数据库？你有严重的平台限制？

随着现代系统，以及它们的内存不减当年，我会推荐某种类型的很好的简单缓存。你应该能够创建的用户信息非常快速高速缓存，将让你避免重复劳动。当你遇到一个节点已经，停止处理。这将避免循环永远拉帮结派。

如果您需要允许一段时间后再次提出现有节点，您可以使用这将是一个数据库中的全球价值last_visit_number。如果节点有这个数字，那么这个爬的是，遇到它的人。如果你想重温自动的任何节点，你只需要在开始爬网之前撞击last_visit_number。

通过你的描述，我不太清楚你是怎么被卡住。

编辑------我只注意到你有一个具体的问题。为了增加你在新的数据拉的速度有多快，我会跟踪给定用户被链接到你的数据（进口或尚未导入）的次数。当选择一个用户抓取，我会选有链接数量较少的用户。我会专门去针对任何最低数量的链接或具有最低数量的链接的用户中随机选择。

雅各

Answer 3:

有没有特别的算法，将帮助您优化从头图的构造。这种或那种方式，你将要访问的每个节点至少一次。无论你做深度优先或广度优先是从速度的角度无关。 Theran正确地指出在广度优先搜索下方的评论，首先探索较近的节点，可以立即给你一个更实用图表，完成整个图形之前; 这可能会或可能不会对你关心的问题。他还指出，深度优先搜索的最巧妙的版本使用递归，这有可能是你的问题来实现。注意不要求递归，但是，您可以添加不完全探索节点堆栈和线性处理他们，如果你的愿望。

如果你对新节点的简单的存在性检查（O（1，如果您使用查找哈希）），则周期会不会有问题的。循环是只有当你不存储完整的图形值得关注。您可以通过图形优化搜索，但施工步骤本身将始终以线性时间。

我同意其他海报，你图的大小不应该是一个问题。 25万不是很大！

关于并发执行; 该图由所有线程更新，因此它需要一个同步的数据结构。由于这是Python中，你可以使用的队列模块，用于存储新的链接还是被你的线程处理。