相关疑难解决方法(0)

抽象问题:我有一个大约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" % …

在由具有指向父级、兄弟级和第一个/最后一个子级的指针的节点表示的通用树中，如下所示：

class Tnode {

    def data
    Tnode parent = null
    Tnode first_child = null, last_child = null 
    Tnode prev_sibling = null, next_sibling = null 

    Tnode(data=null) {
        this.data = data
    }
}

是否可以在不使用任何其他辅助结构（例如队列）的情况下进行迭代（非递归）广度优先（级别顺序）遍历。

所以基本上：我们可以使用单节点引用进行回溯，但不能保存节点集合。到底能不能做到是理论上的部分，但更实际的问题是，在大段上不回溯的情况下，能否高效地做到。