好的图遍历算法

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*

当前实现存在的问题:

• 会卡在已经导入的小团体中，浪费时间并使导入的线程空闲。
• 随着问题被指出，可能会添加更多。

因此，对于较小的改进以及全面的重写，我们表示欢迎。谢谢！

- Paul Tarjan

---

与发现几个著名的图论算法的Robert Tarjan有关系吗？ - Jim Lewis

很遗憾，我们只能从匈牙利的一个城镇得到我们的姓氏。但是我们都热爱计算机和数学。 - Paul Tarjan

与问题无关，但请注意 sys.stderr.write("...\n") 可以被替换为 print >> sys.stderr, "..."（不需要 "\n"，并使用更常见的 print 语句）。 - Eric O. Lebigot

没错，但我正在将stdout重定向到文件（你不可能知道），而仍希望错误消息显示在我的控制台中。 - Paul Tarjan

Answer 1

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

据我所见，您接近实现广度优先搜索（BFS）。请在Google上查找有关此算法的详细信息。当然，不要忘记使用互斥锁--您将需要它们。

- P Shved

---

用户实际上是平均长度为15的字符字符串。我尝试使用{username1：True，username2：True}字典，但很快就占用了100％的内存并锁定了机器。也许在Python中使用字典效率不高？ - Paul Tarjan

一个可能的解决方案是仅存储用户名的哈希值。 - cobbal

此外，对于这种类型的存储，集合比字典更适合。 - cobbal

在文档中（http://docs.python.org/library/stdtypes.html#set-types-set-frozenset）写道，“集合元素，就像字典键一样，必须是可哈希的”，因此我认为是这样。 - cobbal

查找也很好 :-) - Francesco

是的，将内存模型转换为set()，并将整个历史记录保存在内存中就可以了。昨晚我遍历了23k，只使用了800MB的内存。虽然仍然很接近，但我将在几天内改用哈希而不是字符串。谢谢！ - Paul Tarjan

Answer 2

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

对于现代系统及其大量内存，我建议使用一个简单的缓存。您应该能够创建一个非常快速的用户信息缓存，从而避免重复工作。当您遇到已经存在的节点时，请停止处理。这将避免在圈子中无休止地循环。

如果您需要允许重新哈希现有节点一段时间后，您可以使用一个“last_visit_number”，它将是dB中的全局值。如果节点有该数字，则此爬网是遇到它的一个。如果您想自动重新访问任何节点，您只需在开始爬行之前提高“last_visit_number”。

根据您的描述，我不太确定您被卡住了。

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

Jacob

- TheJacobTaylor

---

这10秒是因为需要从用户那里爬取几个页面的信息，然后将其转换为我的数据库格式。其中大部分时间都花在了网络传输上。 - Paul Tarjan

对于新用户的选择非常有趣。我将尝试计算用户的内部链接，并仅从低内部链接用户开始爬取。 - Paul Tarjan

为什么线程这么少？你担心它们会阻塞你吗？我建议为每个节点使用哈希表（类似于Pavel的方法）。你可以创建一个递增的ID，并使用简单的映射表进行交叉引用。 - TheJacobTaylor

是的，我担心远程站点会阻止我。礼貌和一切（在雅虎！我知道我们的爬虫每次目标是2个请求/主机）。有了内存集合的工作，我不需要优化我的爬取路径，但如果对方站点增长数量级，我将不得不转向您的策略。谢谢！ - Paul Tarjan

一个稍微有些扭曲的选择是通过搜索引擎的API利用它们的结果来获取所需的数据。如果您正在构建初始数据库，如果可用，缓存页面可能会为您提供所需的数据。搜索引擎以巨大的速度运行，可能不介意多几个线程。 - TheJacobTaylor

Answer 3

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

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

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

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

- ire_and_curses

---

BFS可能更好，因为它首先查看最接近初始节点的节点，这很可能会在早期给出有用的子集。 BFS还避免了递归250,000级深度的风险，并且可以将其队列保留在与最终图形相同的数据库中（假设使用关系型数据库）。 - Theran

你可以毫无问题地实现深度优先搜索（DFS）而不会出现深度堆栈跟踪的问题：DFS和广度优先搜索（BFS）之间唯一的真正区别在于，在BFS中，你将节点添加到队列中；而在DFS中，则是一个栈。相同的算法，不同的数据结构——因此，有不同的语义。 - Michael Deardeuff

@Theran, Michael：+1 感谢 - 回答已经调整以作出澄清。 - ire_and_curses

听起来需要一个简单的BFS（就像我所拥有的）。我完全同意您的观点，250,000很少，但是我的原始实现很快就用一个字典{username1：True，username2：True}耗尽了内存。也许我应该将其发布为另一个问题。 - Paul Tarjan

Answer 4

虽然你说获取好友列表需要很长时间（10秒或更多），但是一种改良版的Dijkstra算法可能会奏效：

1. 获取任何一个节点。
2. 从已经加载的任何一个节点获取连接。
3. 如果另一端还没有被加载，将该节点添加到图中。
4. 回到步骤2。

关键在于以聪明的方式选择在步骤2中加载的连接。以下是一些简短的说明：

• 你应该防止同一个连接被加载两次或多次。如果你想获取所有连接，选择随机连接并且如果它已经被加载了就丢弃它是非常低效的。
• 如果你想最终加载所有连接，请同时加载一个节点的所有连接。

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

- Martijn