11

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

当前实施的问题：

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

因此，欢迎进行边际改进以及完全重写。谢谢！

4

4 回答 4

7

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

据我所知，您即将实现广度优先搜索 (BFS)。检查谷歌有关此算法的详细信息。当然，不要忘记互斥体——你会需要它们。

于 2009-08-24T06:15:54.690 回答
2

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

对于现代系统及其大量内存，我建议使用某种不错的简单缓存。您应该能够创建一个非常快速的用户信息缓存，以避免重复工作。当您已经遇到一个节点时，停止处理。这将避免在派系中永远骑自行车。

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

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

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

雅各布

于 2009-08-24T06:15:06.737 回答
2

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

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

我同意其他海报的观点，即您的图表大小不应该成为问题。25万不是很大！

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

于 2009-08-24T06:30:09.933 回答
0

尽管您说获取好友列表需要很长时间（10 秒或更长时间），但古老的 Dijkstra 算法的一种变体可能会起作用：

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

诀窍是以智能的方式选择您在步骤 2 中加载的连接。关于此的一些简短评论：

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

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

于 2009-08-24T07:04:43.283 回答