Clojure递归函数执行时间

Question

我正在使用clojure编写一个Web爬虫程序,它会花费不变的时间,而不依赖于我给函数的深度.这是功能本身.(它使用的是clojure汤,但我认为这是无关紧要的)

(defn crawl [source current-depth max-depth]
    (if (= current-depth 0) (write-to-hf "{" false))
    (let [targets (get-links source)]
        (write-to-hf (str ":" source " " (seq targets) "\n") true)
        (if (< current-depth max-depth)
            (map crawl targets (repeat (inc current-depth)) (repeat max-depth))
            (if (= current-depth 0)
                (do (write-to-hf "}" true)
                 targets)
                targets))))

(写入-hf是将数据写入文件的功能,所以它也与问题无关,我想.)

当我在REPL中测试我的函数时,写道:

(crawl "http://bg.wikipedia.org" 0 1)

打印所有链接大约需要一个小时,但如果我将结果放入var,则需要少于几秒.

(def a (crawl "http://bg.wikipedia.org" 0 1))

这看起来很正常,因为I/O操作是最耗时的,但是我试着测试将结果放入var中需要花费多少时间来使用更多的递归深度层,看起来它是不变的.甚至做:

((crawl "http://bg.wikipedia.org" 0 100000000000))

需要同样的时间.

有人可以解释为什么这是一个常数吗？我无法想象如何从维基百科(这是一个每页都有数百个链接的巨大网站)中获取数十亿甚至更多页面的链接,可以在不到一秒的时间内完成.

Answer 1

这一行产生了一系列懒惰的链接:

(map crawl targets (repeat (inc current-depth)) (repeat max-depth))

在打印链接时会发生实际抓取(在本例中为REPL),因此当您将它们保存到var并且不要查看它们时,不会进行任何工作.什么都不做需要大约一个时间.在调用中包裹该行doall以使其非延迟