6

阅读“Clojure 编程”（第 98 页）中关于头部保留的段落，我无法弄清楚split-with示例中发生了什么。我尝试过使用 repl 进行实验，但这让我更加困惑。

(time (let [r (range 1e7) 
            a (take-while #(< % 12) r)
            b (drop-while #(< % 12) r)]
        [(count a) (count b)]))
"Elapsed time: 1910.401711 msecs"
[12 9999988]

(time (let [r (range 1e7) 
            a (take-while #(< % 12) r)
            b (drop-while #(< % 12) r)]
        [(count b) (count a)]))
"Elapsed time: 3580.473787 msecs"
[9999988 12]

(time (let [r (range 1e7) 
            a (take-while #(< % 12) r)
            b (drop-while #(< % 12) r)]
        [(count b)]))
"Elapsed time: 3516.70982 msecs"
[9999988]

正如您从上一个示例中看到的那样，如果我不计算a，则耗时会以某种方式增加。我想，我在这里错过了一些东西，但是什么？

4

5 回答 5

1

对于计数集合，该count函数是 O(1) ，其中包括向量和列表。

另一方面，序列不被计算在内，这使得count它们为 O(n)。这里重要的部分是函数take-while和drop-while返回序列。他们也是懒惰的事实并不是这里的主要因素。

于 2012-11-08T16:26:20.093 回答
1

使用 time aa benchmark 时，多次运行测试以获得准确的结果

user> (defn example2 [] (let [r (range 1e7)                                             
              a (take-while #(< % 12) r)                                     
              b (drop-while #(< % 12) r)]                        
             [(count a) (count b)]))
#'user/example2

user> (dorun (take 1000 (repeatedly example2)))
nil

user> (time (example2))
"Elapsed time: 614.4 msecs"
[12 9999988]

我将运行时的差异归咎于热点编译器尚未完全优化生成的类。我多次运行第一个和第二个示例并得到混合的相对结果：

运行示例一两次：

autotestbed.core> (time (let [r (range 1e7)                                                                
                                        a (take-while #(< % 12) r)                                     
                                                    b (drop-while #(< % 12) r)]                        
                              [(count a) (count b)]))
"Elapsed time: 929.681423 msecs"                                                                           
[12 9999988]
autotestbed.core> (time (let [r (range 1e7)                                                                
                                        a (take-while #(< % 12) r)                                     
                                                    b (drop-while #(< % 12) r)]                        
                              [(count a) (count b)]))
"Elapsed time: 887.81269 msecs"                                                                            
[12 9999988]

然后运行示例二几次：

core> (time (let [r (range 1e7)                                                                
                  a (take-while #(< % 12) r)                                     
                  b (drop-while #(< % 12) r)]                        
             [(count a) (count b)]))
"Elapsed time: 3838.751561 msecs"                                                                          
[12 9999988]
core> (time (let [r (range 1e7)                                                                
                  a (take-while #(< % 12) r)                                     
                  b (drop-while #(< % 12) r)]                        
             [(count a) (count b)]))
"Elapsed time: 970.397078 msecs"                                                                           
[12 9999988]

有时第二个例子也一样快

于 2012-11-08T18:34:52.083 回答
1

计数为 O(1)。这就是为什么您的测量不依赖于它的原因。

于 2012-11-08T09:22:43.563 回答
0

它显示的时间完全取决于系统....如果您重新执行它，它将为每次执行显示一些不同的经过时间

于 2014-01-09T06:29:01.743 回答
0

let即使我们不使用此值，也会执行表单中的绑定。

(let [x (println "Side effect")] 1)

上面的代码打印“副作用”，并返回 1。

在您的所有三个示例中，都以 let 形式使用了相同的绑定，所以我在这里看不到任何区别。顺便说一句，在我的机器上，你所有的片段都花了大约相同的时间。

当你尝试这样的事情时，真正的区别是：

(time (let [r (range 2e7) 
        a (take 100 r)
        b (drop 100 r)]
    [(count a)]))
"Elapsed time: 0.128304 msecs"
[100]

(time (let [r (range 2e7) 
        a (take 100 r)
        b (drop 100 r)]
    [(count b)]))
"Elapsed time: 3807.591342 msecs"
[19999900]

由于b和a是惰性序列，因此count可以O(n)及时工作。但是在第一个示例中，我们不计算 b 的计数，因此它几乎立即起作用。

于 2012-11-08T10:55:26.870 回答