良好的图遍历算法

抽象的问题：我有一个约250,000个节点的图形，平均连接约为10个。查找一个节点的连接是一个漫长的过程（10秒可以说）。将节点保存到数据库也需要大约10秒。我可以很快检查一个节点是否已经存在于db中。如果允许并发，但一次不会有超过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*

目前执行的问题：

卡在我已导入拉帮结派，从而浪费时间和进口线程是空闲的。
随着他们指出，会增加更多。

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

来源

2009-08-24 Paul Tarjan

与Robert Tarjan，几个着名的图论（！）算法的发现者有何关系？ – 2009-08-24 07:34:54

:)不幸的是，只有匈牙利的这个城市，我们都得到了我们的姓氏。但我们都喜欢电脑和数学。 – 2009-08-24 08:23:38

与这个问题无关，但请注意sys.stderr.write（“... \ n”）可以替换为print >> sys.stderr，“...”（不需要“\ n”，并且使用更平常的印刷说明）。 – EOL 2009-08-24 09:59:12

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

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

来源

2009-08-24 06:15:54

用户实际上是平均长度为15的字符串。我尝试了{username1：True，username2：True}的字典，但很快就达到100％memeory并锁定了机器。也许这只是在Python中使用字典效率低下？ – 2009-08-24 07:04:35

一种可能的解决方案是仅存储用户名 – cobbal 2009-08-24 07:07:54

的散列，一组更适合于该类型的存储比字典 – cobbal 2009-08-24 07:08:37

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

随着现代系统，以及他们的记忆，我会推荐一个很好的简单缓存的某种。你应该能够创建一个非常快速的用户信息缓存，这将允许你避免重复的工作。当您遇到节点时，请停止处理。这将避免在派系中永远循环。

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

通过您的描述，我不太清楚您是如何陷入困境的。

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

雅各

来源

2009-08-24 06:15:06 TheJacobTaylor

10秒来自于不得不刮掉用户的几页信息，然后将其转换为我的数据库格式。大部分是网络时间。 – 2009-08-24 07:06:56

至于新用户的选择，很有意思。我会尝试计算用户的链接，并且只能从低链接的用户身上搜索。 – 2009-08-24 07:07:40

为什么这么少的线程？你担心他们会阻止你吗？我将为每个节点（a.la Pavel）建议一个散列。你可以做的一件事是创建一个递增的id并使用一个简单的映射表来交叉引用它们。 – TheJacobTaylor 2009-08-24 17:44:31

没有特定的算法可以帮助您从头开始优化图形的构建。无论如何，你将不得不每次访问每个节点一次。无论你做这个depth first还是breadth first从速度角度来看都是无关紧要的。 Theran在下面的评论中正确指出了广度优先搜索，通过先探索更接近的节点，可以在整个图完成之前立即为您提供更有用的图;这可能会或可能不会成为您的担忧。他还指出，深度优先搜索的最新版本是使用递归实现的，这可能会成为您的问题。请注意，递归不是必需的，但是;您可以将不完整探索的节点添加到堆栈，并根据需要线性处理它们。

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

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

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

来源

2009-08-24 06:30:09

BFS可能会更好，因为它会首先查看最初的节点，这很可能会在早期给出一个有用的子集。 BFS还避免了递归250,000级深度的风险，并且可以将其队列保留在与最终图（假设RDBMS）相同的DB中。 – Theran 2009-08-24 06:36:34

您当然可以在不存在深堆栈跟踪问题的情况下制作DFS：DFS和BFS之间唯一真正的区别是在BFS中将节点添加到队列;在DFS中，一个堆栈。相同的算法，不同的数据结构 - 因此，不同的语义。 – 2009-08-24 06:49:14

@Theran，Michael：+1谢谢 - 答案调整后作出澄清。 – 2009-08-24 06:56:07

虽然你说，让好友列表需要花费大量的时间（10秒以上），良好的老Dijkstra算法的一种变体可能只是工作：

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

诀窍是选择在加载第二步中，通过智能的方式连接。关于此的一些简短的评论：

您应该以某种方式防止相同的连接被加载两次或更多。如果你已经连接好了，选择一个随机连接并丢弃它，如果它已经被加载，那么效率是非常低的。
如果要最终加载所有连接，请同时加载节点的所有连接。

为了真正说一下效率，请提供关于数据结构的更多细节。

来源

2009-08-24 07:04:43 Martijn

良好的图遍历算法

回答

相关问题