良好的图遍历算法

Question

抽象问题：我有一个包含大约 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*

当前实现的问题：

• 陷入我已经导入的派系中，从而浪费时间并且导入线程处于空闲状态。
• 当他们指出时会添加更多内容。

因此，边际改进以及全面重写都是受欢迎的。谢谢！

Answer 1

要记住您已经访问过的用户的 ID，您需要一个长度为 250,000 个整数的映射。这距离“太多”还很远。只需维护这样一个地图，并仅遍历通向尚未发现的用户的边缘，在找到此类边缘时将它们添加到该地图中。

据我所知，您已经接近实现广度优先搜索（BFS）了。检查谷歌有关该算法的详细信息。当然，不要忘记互斥体——您将需要它们。

Answer 2

我真的很困惑为什么需要 10 秒才能将节点添加到数据库。这听起来像是一个问题。你使用什么数据库？你们有严格的平台限制吗？

对于现代系统及其大量内存，我会推荐某种简单的缓存。您应该能够创建非常快速的用户信息缓存，从而避免重复工作。当您已经遇到一个节点时，停止处理。这将避免永远在派系中循环。

如果您需要在一段时间后重新散列现有节点，您可以使用last_visit_number，它是 dB 中的全局值。如果该节点具有该编号，则该爬网就是遇到该编号的节点。如果你想自动重新访问任何节点，你只需要在开始抓取之前增加last_visit_number。

根据你的描述，我不太确定你是如何陷入困境的。

编辑 - - -
我刚刚注意到你有一个具体的问题。为了提高提取新数据的速度，我会跟踪给定用户在数据中链接的次数（已导入或尚未导入）。在选择要抓取的用户时，我会选择链接数量较少的用户。我会特别选择链接数量最少的用户，或者在链接数量最少的用户中随机选择。

雅各布

Answer 3

没有特定的算法可以帮助您从头开始优化图的构造。不管怎样，您必须至少访问每个节点一次。无论您是深度优先还是广度优先 从速度角度来看是无关紧要的。 Theran 在下面的评论中正确指出，通过首先探索较近的节点，广度优先搜索可能会给您带来更有用的结果在整个图表完成之前立即绘制图表；这可能是也可能不是您关心的问题。他还指出，深度优先搜索的最简洁版本是使用递归实现的，这对您来说可能是一个问题。但请注意，递归不是必需的；如果您愿意，您可以将未完全探索的节点添加到堆栈中并线性处理它们。

如果您对新节点进行简单的存在性检查（如果您使用哈希进行查找，则为 O(1)），那么循环根本不会成为问题。如果您不存储完整的图表，则仅需要考虑循环。您可以通过图表优化搜索，但构建步骤本身始终需要线性时间。

我同意其他发帖者的观点，即图表的大小不应该成为问题。 25万并不是很大！

关于并发执行；该图由所有线程更新，因此它需要是同步的数据结构。由于这是Python，您可以使用 Queue 模块来存储新链接由您的线程处理。

Answer 4

尽管您说获取朋友列表需要花费大量时间（10 秒或更多），但古老的 Dijkstra 算法的一个变体可能会起作用：

1. 获取任何节点。
2. 从您已加载的任何节点获取连接。
3. 如果另一端尚未加载，则将该节点添加到图中。
4. 转到步骤 2。

技巧是以智能方式选择在步骤 2 中加载的连接。关于这一点的一些简短评论：

• 您应该以某种方式防止相同的连接被加载两次或更频繁。如果您需要所有连接，则选择随机连接并在已加载的情况下将其丢弃是非常低效的。
• 如果要最终加载所有连接，请同时加载某个节点的所有连接。

为了真正说明效率，请提供有关数据结构的更多详细信息。